Symmetry.cpp File Reference

Symmetry-breaking constraints for counting: the pattern's automorphism orbits by individualisation-refinement, turned into Grochow-Kellis ordering constraints. More...

#include "Symmetry.h"
#include <algorithm>
#include <numeric>

Include dependency graph for Symmetry.cpp:

Classes
class	anonymous_namespace{Symmetry.cpp}::Refiner

Namespaces
namespace	anonymous_namespace{Symmetry.cpp}

Functions
bool	anonymous_namespace{Symmetry.cpp}::hasEdge (const std::vector< std::vector< int > > &adj, int a, int b)
bool	anonymous_namespace{Symmetry.cpp}::findIsomorphism (Refiner &r, const std::vector< int > &labels, std::vector< int > c1, std::vector< int > c2, std::vector< int > &sigma)
int	anonymous_namespace{Symmetry.cpp}::find (std::vector< int > &parent, int x)
SymmetryBreaking	computeSymmetryBreaking (const AppGraph &pattern, const OrbitCounts &orbits, const std::vector< int > &order, long long budget)
	Computes the constraints for pattern under the matching order order (node IDs).

Detailed Description

Symmetry-breaking constraints for counting: the pattern's automorphism orbits by individualisation-refinement, turned into Grochow-Kellis ordering constraints.

See Symmetry.h.

Function Documentation

computeSymmetryBreaking()

SymmetryBreaking computeSymmetryBreaking	(	const AppGraph &	pattern,
		const OrbitCounts &	orbits,
		const std::vector< int > &	order,
		long long	budget = 20000000
	)

Computes the constraints for pattern under the matching order order (node IDs).

Vertices are fixed one at a time in matching order; at each step the orbit of the vertex under the automorphisms that fix the earlier ones is found by individualisation-refinement, starting from a colouring by label and orbit-count vector (orbits, by internal index). budget bounds the total refinement work.