Symmetry.h File Reference

Symmetry-breaking constraints for counting embeddings. More...

#include <cstdint>
#include <vector>
#include "AppGraph.h"
#include "OrbitCounter.h"

Include dependency graph for Symmetry.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

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

Functions
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).

Detailed Description

Symmetry-breaking constraints for counting embeddings.

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.