C++ Reference: class GraphSymmetryFinder
Note: This documentation is automatically generated.
| Method | |
|---|---|
DistinguishNodeInPartition | Return type: Arguments: 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. |
FindSymmetries | Return type: Arguments: 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 that 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. |
GraphSymmetryFinder | Arguments: 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. |
IsGraphAutomorphism | Return type: Arguments: 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). |
RecursivelyRefinePartitionByAdjacency | Return type: Arguments: 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. |