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 multiple-edges.
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 multiple-edges.
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