networkx.GraphMatcher

class GraphMatcher(G1, G2)

Check isomorphism of graphs.

A GraphMatcher is responsible for matching undirected graphs (Graph or XGraph) in a predetermined manner. For graphs G1 and G2, this typically means a check for an isomorphism between them, though other checks are also possible. For example, the GraphMatcher class can check if a subgraph of G1 is isomorphic to G2.

Matching is done via syntactic feasibility. It is also possible to check for semantic feasibility. Feasibility, then, is defined as the logical AND of the two functions.

To include a semantic check, the GraphMatcher class should be subclassed, and the semantic_feasibility() function should be redefined. By default, the semantic feasibility function always returns True. The effect of this is that semantics are not considered in the matching of G1 and G2.

For more information, see the docmentation for:

syntactic_feasibliity() semantic_feasibility()

Notes

Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento, “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-1372, Oct., 2004.

Modified to handle undirected graphs. Modified to handle multiple edges.

Examples

Suppose G1 and G2 are isomorphic graphs. Verification is as follows:

>>> G1=nx.path_graph(4)
>>> G2=nx.path_graph(4)
>>> GM = nx.GraphMatcher(G1,G2)
>>> GM.is_isomorphic()
True
>>> GM.mapping
{0: 0, 1: 1, 2: 2, 3: 3}

GM.mapping stores the isomorphism mapping.