Package org.jgrapht.alg.isomorphism

Class VF2SubgraphIsomorphismInspector<V,E>

java.lang.Object

org.jgrapht.alg.isomorphism.VF2AbstractIsomorphismInspector<V,E>

org.jgrapht.alg.isomorphism.VF2SubgraphIsomorphismInspector<V,E>

Type Parameters:

V - the type of the vertices

E - the type of the edges

All Implemented Interfaces:

IsomorphismInspector<V,E>

public class VF2SubgraphIsomorphismInspector<V,E>
extends VF2AbstractIsomorphismInspector<V,E>

This is an implementation of the VF2 algorithm using its feature of detecting subgraph isomorphism between two graphs as described in Cordella et al. A (sub)graph isomorphism algorithm for matching large graphs (2004), DOI:10.1109/TPAMI.2004.75, http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1323804

Note that this inspector 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. For example, given as input the cubical graph $Q_{3}$ and the square graph, isomorphic mappings will be found between the square and the faces of the cube. However, given the complete graph $K_{5}$ and the square graph as input, no isomorphisms will be found since all induced subgraphs of a complete graph are themselves complete graphs.

Consequently, in the case where both input graphs have the same number of vertices, this algorithm is equivalent to running VF2GraphIsomorphismInspector.

This implementation of the VF2 algorithm does not support graphs with multiple (parallel) edges.

Field Summary

Fields inherited from class org.jgrapht.alg.isomorphism.VF2AbstractIsomorphismInspector

edgeComparator, graph1, graph2, ordering1, ordering2, vertexComparator

Constructor Summary

Constructors

Constructor	Description
VF2SubgraphIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2)	Construct a new VF2 subgraph isomorphism inspector.
VF2SubgraphIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2, boolean cacheEdges)	Construct a new VF2 subgraph isomorphism inspector.
VF2SubgraphIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2, java.util.Comparator<V> vertexComparator, java.util.Comparator<E> edgeComparator)	Construct a new VF2 subgraph isomorphism inspector.
VF2SubgraphIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2, java.util.Comparator<V> vertexComparator, java.util.Comparator<E> edgeComparator, boolean cacheEdges)	Construct a new VF2 subgraph isomorphism inspector.

Method Summary

Modifier and Type	Method	Description
org.jgrapht.alg.isomorphism.VF2SubgraphMappingIterator<V,E>	getMappings()	Get an iterator over all calculated (isomorphic) mappings between two graphs.

Methods inherited from class org.jgrapht.alg.isomorphism.VF2AbstractIsomorphismInspector

isomorphismExists

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

VF2SubgraphIsomorphismInspector

public VF2SubgraphIsomorphismInspector(Graph<V,E> graph1,
                                       Graph<V,E> graph2,
                                       java.util.Comparator<V> vertexComparator,
                                       java.util.Comparator<E> edgeComparator,
                                       boolean cacheEdges)

Construct a new VF2 subgraph isomorphism inspector.

Parameters:

graph1 - the first graph

graph2 - the second graph (possible induced subgraph of graph1)

vertexComparator - comparator for semantic equivalence of vertices

edgeComparator - comparator for semantic equivalence of edges

cacheEdges - if true, edges get cached for faster access

VF2SubgraphIsomorphismInspector

public VF2SubgraphIsomorphismInspector(Graph<V,E> graph1,
                                       Graph<V,E> graph2,
                                       java.util.Comparator<V> vertexComparator,
                                       java.util.Comparator<E> edgeComparator)

Construct a new VF2 subgraph isomorphism inspector.

Parameters:

graph1 - the first graph

graph2 - the second graph (possible induced subgraph of graph1)

vertexComparator - comparator for semantic equivalence of vertices

edgeComparator - comparator for semantic equivalence of edges

VF2SubgraphIsomorphismInspector

public VF2SubgraphIsomorphismInspector(Graph<V,E> graph1,
                                       Graph<V,E> graph2,
                                       boolean cacheEdges)

Construct a new VF2 subgraph isomorphism inspector.

Parameters:

graph1 - the first graph

graph2 - the second graph (possible induced subgraph of graph1)

cacheEdges - if true, edges get cached for faster access

VF2SubgraphIsomorphismInspector

public VF2SubgraphIsomorphismInspector(Graph<V,E> graph1,
                                       Graph<V,E> graph2)

Construct a new VF2 subgraph isomorphism inspector.

Parameters:

graph1 - the first graph

graph2 - the second graph (possible induced subgraph of graph1)

Method Detail

getMappings

public org.jgrapht.alg.isomorphism.VF2SubgraphMappingIterator<V,E> getMappings()

Description copied from interface: IsomorphismInspector

Get an iterator over all calculated (isomorphic) mappings between two graphs.

Specified by:

getMappings in interface IsomorphismInspector<V,E>

Specified by:

getMappings in class VF2AbstractIsomorphismInspector<V,E>

Returns:

an iterator over all calculated (isomorphic) mappings between two graphs