operations_research::GraphSymmetryFinder Class Reference

#include <find_graph_symmetries.h>

Public Types
typedef ::util::StaticGraph	Graph

Public Member Functions
	GraphSymmetryFinder (const Graph &graph, bool is_undirected)
bool	IsGraphAutomorphism (const DynamicPermutation &permutation) const
absl::Status	FindSymmetries (std::vector< int > *node_equivalence_classes_io, std::vector< std::unique_ptr< SparsePermutation > > *generators, std::vector< int > *factorized_automorphism_group_size, TimeLimit *time_limit=nullptr)
void	RecursivelyRefinePartitionByAdjacency (int first_unrefined_part_index, DynamicPartition *partition)
void	DistinguishNodeInPartition (int node, DynamicPartition *partition, std::vector< int > *new_singletons_or_null)
	**** Methods below are public FOR TESTING ONLY. ****

Detailed Description

Definition at line 47 of file find_graph_symmetries.h.

Member Typedef Documentation

Graph

::util::StaticGraph operations_research::GraphSymmetryFinder::Graph

Definition at line 49 of file find_graph_symmetries.h.

Constructor & Destructor Documentation

GraphSymmetryFinder()

operations_research::GraphSymmetryFinder::GraphSymmetryFinder	(	const Graph &	graph,
		bool	is_undirected )

If the Graph passed to the GraphSymmetryFinder is undirected, i.e. for every arc a->b, b->a is also present, then you should set "is_undirected" to true. This will, in effect, DCHECK() that the graph is indeed undirected, and bypass the need for reverse adjacency lists.

If you don't know this in advance, you may use GraphIsSymmetric() from ortools/graph/util.h.

"graph" must not have multi-arcs.

Todo

(user): support multi-arcs.

Set up an "unlimited" time limit by default.

Compute the reverse adjacency lists. First pass: compute the total in-degree of all nodes and put it in reverse_adj_list_index (shifted by two; see below why).

Second pass: apply a cumulative sum over reverse_adj_list_index. After that, reverse_adj_list contains: [0, 0, in_degree(node0), in_degree(node0) + in_degree(node1), ...]

Third pass: populate "flattened_reverse_adj_lists", using reverse_adj_list_index[i] as a dynamic pointer to the yet-unpopulated area of the reverse adjacency list of node #i.

The last pass shifted reverse_adj_list_index, so it's now as we want it: [0, in_degree(node0), in_degree(node0) + in_degree(node1), ...]

Definition at line 173 of file find_graph_symmetries.cc.

Member Function Documentation

DistinguishNodeInPartition()

void operations_research::GraphSymmetryFinder::DistinguishNodeInPartition	(	int	node,
		DynamicPartition *	partition,
		std::vector< int > *	new_singletons_or_null )

**** Methods below are public FOR TESTING ONLY. ****

Special wrapper of the above method: assuming that partition is already fully refined, further refine it by {node}, and propagate by adjacency. Also, optionally collect all the new singletons of the partition in "new_singletons", sorted by their part number in the partition.

Explore the newly refined parts to gather all the new singletons.

We may see the same singleton parent several times, so we guard them with the tmp_node_mask_ boolean vector.

Reset tmp_node_mask_.

Definition at line 341 of file find_graph_symmetries.cc.

FindSymmetries()

absl::Status operations_research::GraphSymmetryFinder::FindSymmetries	(	std::vector< int > *	node_equivalence_classes_io,
		std::vector< std::unique_ptr< SparsePermutation > > *	generators,
		std::vector< int > *	factorized_automorphism_group_size,
		TimeLimit *	time_limit = nullptr )

Find a set of generators of the automorphism subgroup of the graph that respects the given node equivalence classes. The generators are themselves permutations of the nodes: see http://en.wikipedia.org/wiki/Automorphism. These permutations may only map a node onto a node of its equivalence class: two nodes i and j are in the same equivalence class iff node_equivalence_classes_io[i] == node_equivalence_classes_io[j];

This set of generators is not necessarily the smallest possible (neither in the number of generators, nor in the size of these generators), but it is minimal in that no generator can be removed while keeping the generated group intact.

Todo

(user): verify the minimality in unit tests.

Note

if "generators" is empty, then the graph has no symmetry: the only automorphism is the identity.

The equivalence classes are actually an input/output: they are refined according to all asymmetries found. In the end, n1 and n2 will be considered equivalent (i.e. node_equivalence_classes_io[n1] == node_equivalence_classes_io[n2]) if and only if there exists a permutation of nodes that:

• keeps the graph invariant
• maps n1 onto n2
• maps each node to a node of its original equivalence class.

This method also outputs the size of the automorphism group, expressed as a factorized product of integers (note that the size itself may be as large as N!).

DEADLINE AND PARTIAL COMPLETION: If the deadline passed as argument (via TimeLimit) is reached, this method will return quickly (within a few milliseconds of the limit). The outputs may be partially filled:

• Each element of "generators", if non-empty, will be a valid permutation.
• "node_equivalence_classes_io" will contain the equivalence classes corresponding to the orbits under all the generators in "generators".
• "factorized_automorphism_group_size" will also be incomplete, and partially valid: its last element may be undervalued. But all prior elements are valid factors of the automorphism group size.

Initialization.

Break all inherent asymmetries in the graph.

To find all permutations of the Graph that satisfy the current partition, we pick an element v that is not in a singleton part, and we split the search in two phases: 1) Find (the generators of) all permutations that keep v invariant. 2) For each w in PartOf(v) such that w != v: find one permutation that maps v to w, if it exists. if it does exists, add this to the generators.

The part 1) is recursive.

Since we can't really use true recursion because it will be too deep for the stack, we implement it iteratively. To do that, we unroll 1): the "invariant dive" is a single pass that successively refines the node base_partition with elements from non-singleton parts (the 'invariant node'), until all parts are singletons. We remember which nodes we picked as invariants, and also the successive partition sizes as we refine it, to allow us to backtrack. Then we'll perform 2) in the reverse order, backtracking the stack from 1) as using another dedicated stack for the search (see below).

Todo

(user): experiment with, and briefly describe the results of various algorithms for picking the invariant node:

• random selection
• highest/lowest degree first
• enumerate by part index; or by part size
• etc.

Now we've dived to the bottom: we're left with the identity permutation, which we don't need as a generator. We move on to phase 2).

Backtrack the last step of 1) (the invariant dive).

Now we'll try to map "root_node" to all image nodes that seem compatible and that aren't "root_node" itself.

Doing so, we're able to detect potential bad (or good) matches by refining the 'base' partition with "root_node"; and refining the 'image' partition (which represents the partition of images nodes, i.e. the nodes after applying the currently implicit permutation) with that candidate image node: if the two partitions don't match, then the candidate image isn't compatible. If the partitions do match, we might either find the underlying permutation directly, or we might need to further try and map other nodes to their image: this is a recursive search with backtracking.

The potential images of root_node are the nodes in its part. They can be pruned by the already computed equivalence classes.

Todo

(user): better elect the representative of each equivalence class in order to reduce the permutation support down the line

Todo

Todo

(user): Don't build a list; but instead use direct, inline iteration on the representatives in the while() loop below, to benefit from the incremental merging of the equivalence classes.

Try to map "root_node" to all of its potential images. For each image, we only care about finding a single compatible permutation, if it exists.

We found a permutation. We store it in the list of generators, and further prune out the remaining 'root' image candidates, taking into account the permutation we just found.

HACK(user): to make sure that we keep root_image_node as the representant of its part, we temporarily move it to the front of the vector, then move it again to the back so that it gets deleted by the pop_back() below.

Register it onto the permutations_displacing_node vector.

Move the permutation to the generator list (this also transfers ownership).

We keep track of the size of the orbit of 'root_node' under the current subgroup: this is one of the factors of the total group size.

Todo

(user): better, more complete explanation.

Definition at line 448 of file find_graph_symmetries.cc.

IsGraphAutomorphism()

bool operations_research::GraphSymmetryFinder::IsGraphAutomorphism

(

const DynamicPermutation &

permutation

)

const

Whether the given permutation is an automorphism of the graph given at construction. This costs O(sum(degree(x))) (the sum is over all nodes x that are displaced by the permutation).

The graph was not symmetric: we must also check the incoming arcs to displaced nodes.

Definition at line 220 of file find_graph_symmetries.cc.

RecursivelyRefinePartitionByAdjacency()

void operations_research::GraphSymmetryFinder::RecursivelyRefinePartitionByAdjacency	(	int	first_unrefined_part_index,
		DynamicPartition *	partition )

Fully refine the partition of nodes, using the graph as symmetry breaker. This means applying the following steps on each part P of the partition:

• Compute the aggregated in-degree of all nodes of the graph, only looking at arcs originating from nodes in P.
• For each in-degree d=1...max_in_degree, refine the partition by the set of nodes with in-degree d. And recursively applying it on all new or modified parts.

In our use cases, we may call this in a scenario where the partition was already partially refined on all parts #0...#K, then you should set "first_unrefined_part_index" to K+1.

Rename, for readability of the code below.

This function is the main bottleneck of the whole algorithm. We count the number of blocks in the inner-most loops in num_operations. At the end we will multiply it by a factor to have some deterministic time that we will append to the deterministic time counter.

Todo

(user): We are really imprecise in our counting, but it is fine. We just need a way to enforce a deterministic limit on the computation effort.

Assuming that the partition was refined based on the adjacency on parts [0 .. first_unrefined_part_index) already, we simply need to refine parts first_unrefined_part_index ... NumParts()-1, the latter bound being a moving target: When a part #p < first_unrefined_part_index gets modified, it's always split in two: itself, and a new part #p'. Since #p was already refined on, we only need to further refine on one of its two split parts. And this will be done because p' > first_unrefined_part_index.

Thus, the following loop really does the full recursive refinement as advertised.

Count the aggregated degree of all nodes, only looking at arcs that come from/to the current part.

Group the nodes by (nonzero) degree. Remember the maximum degree.

For each degree, refine the partition by the set of nodes with that degree.

We use a manually tuned factor 3 because Refine() does quite a bit of operations for each node in its argument.

The coefficient was manually tuned (only on a few instances) so that the time is roughly correlated with seconds on a fast desktop computer from

Definition at line 264 of file find_graph_symmetries.cc.

---

The documentation for this class was generated from the following files:

• ortools/algorithms/find_graph_symmetries.h
• ortools/algorithms/find_graph_symmetries.cc