Package org.jgrapht.alg.isomorphism

Class VF2AbstractIsomorphismInspector<V,E>

java.lang.Object

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

Type Parameters:

V - the type of the vertices

E - the type of the edges

All Implemented Interfaces:

IsomorphismInspector<V,E>

Direct Known Subclasses:

VF2GraphIsomorphismInspector, VF2SubgraphIsomorphismInspector

public abstract class VF2AbstractIsomorphismInspector<V,E>
extends java.lang.Object
implements IsomorphismInspector<V,E>

Base implementation of the VF2 algorithm using its feature of detecting 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

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

Field Summary

Fields

Modifier and Type	Field	Description
protected java.util.Comparator<E>	edgeComparator
protected Graph<V,E>	graph1
protected Graph<V,E>	graph2
protected org.jgrapht.alg.isomorphism.GraphOrdering<V,E>	ordering1
protected org.jgrapht.alg.isomorphism.GraphOrdering<V,E>	ordering2
protected java.util.Comparator<V>	vertexComparator

Constructor Summary

Constructors

Constructor	Description
VF2AbstractIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2)	Construct a new base implementation of the VF2 isomorphism inspector.
VF2AbstractIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2, boolean cacheEdges)	Construct a new base implementation of the VF2 isomorphism inspector.
VF2AbstractIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2, java.util.Comparator<V> vertexComparator, java.util.Comparator<E> edgeComparator)	Construct a new base implementation of the VF2 isomorphism inspector.
VF2AbstractIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2, java.util.Comparator<V> vertexComparator, java.util.Comparator<E> edgeComparator, boolean cacheEdges)	Construct a new base implementation of the VF2 isomorphism inspector.

Method Summary

Modifier and Type	Method	Description
abstract java.util.Iterator<GraphMapping<V,E>>	getMappings()	Get an iterator over all calculated (isomorphic) mappings between two graphs.
boolean	isomorphismExists()	Check if an isomorphism exists.

Methods inherited from class java.lang.Object

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

Field Detail

graph1

protected Graph<V,E> graph1

graph2

protected Graph<V,E> graph2

vertexComparator

protected java.util.Comparator<V> vertexComparator

edgeComparator

protected java.util.Comparator<E> edgeComparator

ordering1

protected org.jgrapht.alg.isomorphism.GraphOrdering<V,E> ordering1

ordering2

protected org.jgrapht.alg.isomorphism.GraphOrdering<V,E> ordering2

Constructor Detail

VF2AbstractIsomorphismInspector

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

Construct a new base implementation of the VF2 isomorphism inspector.

Parameters:

graph1 - the first graph

graph2 - the second graph

vertexComparator - comparator for semantic equivalence of vertices

edgeComparator - comparator for semantic equivalence of edges

cacheEdges - if true, edges get cached for faster access

VF2AbstractIsomorphismInspector

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

Construct a new base implementation of the VF2 isomorphism inspector.

Parameters:

graph1 - the first graph

graph2 - the second graph

vertexComparator - comparator for semantic equivalence of vertices

edgeComparator - comparator for semantic equivalence of edges

VF2AbstractIsomorphismInspector

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

Construct a new base implementation of the VF2 isomorphism inspector.

Parameters:

graph1 - the first graph

graph2 - the second graph

cacheEdges - if true, edges get cached for faster access

VF2AbstractIsomorphismInspector

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

Construct a new base implementation of the VF2 isomorphism inspector.

Parameters:

graph1 - the first graph

graph2 - the second graph

Method Detail

getMappings

public abstract java.util.Iterator<GraphMapping<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>

Returns:

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

isomorphismExists

public boolean isomorphismExists()

Description copied from interface: IsomorphismInspector

Check if an isomorphism exists.

Specified by:

isomorphismExists in interface IsomorphismInspector<V,E>

Returns:

true if there is an isomorphism, false if there is no isomorphism