SymmetryBreaking Struct Reference

Symmetry-breaking constraints for counting embeddings (Grochow and Kellis). More...

#include <Symmetry.h>

Public Attributes
std::vector< std::vector< int > >	smaller_than
	smaller_than[w]: the pattern vertices (internal indices) whose image must have a smaller data node ID than the image of w.
uint64_t	multiplier = 1
	Number of embeddings each counted one stands for: the product of the orbit sizes used, which is |Aut(G_p)| when the computation was not truncated.
int	levels = 0
	Number of vertices whose orbit contributed constraints.
bool	truncated = false
	The work budget ran out, or the multiplier would overflow.
long long	work = 0
	Work units spent, against the budget.

Detailed Description

Symmetry-breaking constraints for counting embeddings (Grochow and Kellis).

Embeddings that differ by an automorphism of the pattern are counted once: the search enforces the constraints below, which keep exactly one embedding out of every multiplier, and multiplies its count by multiplier.

Member Data Documentation

levels

int SymmetryBreaking::levels = 0

Number of vertices whose orbit contributed constraints.

multiplier

uint64_t SymmetryBreaking::multiplier = 1

Number of embeddings each counted one stands for: the product of the orbit sizes used, which is |Aut(G_p)| when the computation was not truncated.

smaller_than

std::vector<std::vector<int> > SymmetryBreaking::smaller_than

smaller_than[w]: the pattern vertices (internal indices) whose image must have a smaller data node ID than the image of w.

truncated

bool SymmetryBreaking::truncated = false

The work budget ran out, or the multiplier would overflow.

The constraints found so far are still valid: they break a subgroup of the automorphisms, with the matching multiplier.

work

long long SymmetryBreaking::work = 0

Work units spent, against the budget.

---

The documentation for this struct was generated from the following file:

• include/Symmetry.h