Isomorphism¶
Algorithms¶

jgrapht.algorithms.isomorphism.
vf2
(graph1, graph2)[source]¶ The VF2 algorithm for detection of isomorphism between two graphs.
Cordella et al. A (sub)graph isomorphism algorithm for matching large graphs (2004), DOI:10.1109/TPAMI.2004.75
This implementation of the VF2 algorithm does not support graphs with multipleedges.
Note
Graph mappings are represented using
GraphMapping
instances Parameters
graph1 – the first graph
graph2 – the second graph
 Returns
an iterator over graph mappings if the graphs are isomorphic, otherwise None

jgrapht.algorithms.isomorphism.
vf2_subgraph
(graph1, graph2)[source]¶ The VF2 algorithm for detection of subgraph isomorphism between two graphs.
Cordella et al. A (sub)graph isomorphism algorithm for matching large graphs (2004), DOI:10.1109/TPAMI.2004.75
This implementation of the VF2 algorithm does not support graphs with multipleedges.
Note
Graph mappings are represented using
GraphMapping
instancesWarning
This algorithm only finds isomorphisms between a smaller graph and all induced subgraphs of a larger graph. It does not find isomorphisms between the smaller graph and arbitrary subgraphs of the larger graph.
 Parameters
graph1 – the first graph
graph2 – the second graph
 Returns
an iterator over graph mappings if the graphs are isomorphic, otherwise None
Types¶
A mapping from one graph to another is represented using instances of the following class.

class
jgrapht.types.
GraphMapping
[source]¶ A graph mapping between two graphs g1 and g2.

abstract
edge_correspondence
(edge, forward=True)[source]¶ Get the corresponding edge.
 Parameters
edge – the first edge
forward – if True the map is from g1 to g2, otherwise from g2 to g1
 Returns
the edge on the other graph or None if it does not exist

abstract
edges_correspondence
(forward=True)[source]¶ Get a dictionary with all the corresponding edges.
 Parameters
forward – if True the map is from g1 to g2, otherwise from g2 to g1
 Returns
a dictionary with keys edges from one of the graphs and values edges from the other graph

abstract