Module isomorphism 

Graph isomorphism algorithms (ALGO-ISO-*).

First entry: simplify_and_colorize (ALGO-ISO-030) — turn a graph with self-loops and multi-edges into a vertex/edge colored simple graph, the form consumed by isomorphism backends such as VF2.

Structs

LadSubisomorphism

Result of a first-solution LAD subgraph-isomorphism search (subisomorphic_lad).

SimplifyAndColorize

The colored simple graph produced by simplify_and_colorize.

Vf2Isomorphism

Result of an exact VF2 graph-isomorphism test (isomorphic_vf2).

Vf2Subisomorphism

Result of a VF2 subgraph-isomorphism test (subisomorphic_vf2).

WlHashResult

Result of Weisfeiler-Lehman hashing.

Functions

automorphism_group

Compute a generating set of the automorphism group Aut(G).

canonical_permutation

Compute a canonical vertex permutation of graph.

count_automorphisms

Count the automorphisms of graph — the order |Aut(G)| of its automorphism group.

count_isomorphisms_vf2

Count the number of VF2 isomorphic mappings between two graphs.

count_subisomorphisms_vf2

Count the number of VF2 subgraph-isomorphic embeddings of the pattern graph2 into the target graph1.

get_isomorphisms_vf2

Collect every VF2 isomorphic mapping between two graphs.

get_subisomorphisms_lad

Enumerate all subgraph isomorphisms from pattern into target with the LAD algorithm. Each returned vector maps pattern vertex i (by index) to its target vertex.

get_subisomorphisms_vf2

Collect every VF2 subgraph-isomorphic embedding of the pattern graph2 into the target graph1.

isomorphic

Decide whether two graphs are isomorphic, choosing a backend automatically.

isomorphic_bliss

Test whether two graphs are isomorphic via canonical labeling (BLISS).

isomorphic_vf2

Test whether two graphs are isomorphic using the VF2 algorithm.

simplify_and_colorize

Build a vertex- and edge-colored simple graph from graph.

subisomorphic

Decide whether graph2 is isomorphic to a subgraph of graph1.

subisomorphic_lad

Decide whether pattern is isomorphic to a subgraph of target using the LAD algorithm, returning the first embedding found.

subisomorphic_vf2

Test whether the pattern graph2 is a (non-induced) subgraph of the target graph1, using the VF2 algorithm.

wl_hash

Compute the Weisfeiler-Lehman hash of a graph.

wl_hash_iterations

Compute WL hashes at each iteration level (subtree patterns of depth 0..k).

wl_isomorphic

Check if two graphs have equal WL hash (necessary but not sufficient for isomorphism).