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 instances

Warning

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 vertex_correspondence(vertex, forward=True)[source]

Get the corresponding vertex.

Parameters

  • vertex – the first vertex

  • forward – if True the map is from g1 to g2, otherwise from g2 to g1

Returns

the vertex on the other graph or None if it does not exist

abstract vertices_correspondence(forward=True)[source]

Get a dictionary with all the corresponding vertices.

Parameters

forward – if True the map is from g1 to g2, otherwise from g2 to g1

Returns

a dictionary with keys vertices from one of the graphs and values vertices from the other graph