dwave.graphs.algorithms.automorphism.schreier_rep#

schreier_rep(graph: Graph, graph_coloring: Mapping[Hashable, int] | None = None) → SchreierContext[source]#

Compute Schreier representatives and orbits for a graph.

Builds a depth-first search tree, iteratively performing color refinement and vertex individualization until leaf nodes are reached where all graph vertices are uniquely colored. Leaf nodes with identical adjacency matrices represent graph automorphisms. Discovered automorphisms are used to prune the search tree.

If graphs have more than one component, automorphisms are found for each individual component, and automorphisms between components are determined by considering which components are isomorphic. Since the number of automorphisms between isomorphic components scales factorially with the number of components, this is significantly faster than naively performing refinement-individualization over the whole graph. It would be possible to update u_vector directly without using enter(), which in principle should be even faster, and should be the first place to look if further performance improvements are required.

Parameters:

  • graph – A NetworkX Graph object representing the input graph containing

  • methods (the following) –

    • nodes(): iterable of all nodes

    • number_of_nodes(): total number of nodes

    • edges(): iterable of all edges

    • neighbors(): iterable of all neighbours for a given node

  • graph_coloring – Optional mapping from original vertex label to color label.