edu.ucla.sspace.graph.isomorphism

Class VF2IsomorphismTester

java.lang.Object

edu.ucla.sspace.graph.isomorphism.AbstractIsomorphismTester

edu.ucla.sspace.graph.isomorphism.VF2IsomorphismTester

All Implemented Interfaces:

IsomorphismTester

public class VF2IsomorphismTester
extends AbstractIsomorphismTester

An implementation of the VF2 algorithm for detecting isomorphic graphs. This algorithm may be found in:

• Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26:10. 2004. Available here

This implementation will test that the number of edges between two vertices are equivalent. However, the implementation does not test that the types are equivalent. In essence, this class checks only for structural equivalence, independent of any addition properties on the nodes or edges.

This implementation is an adaptation of the VFLib implementation.

This class is thread-safe.

Author:

David Jurgens

Constructor Summary

Constructors

Constructor and Description
VF2IsomorphismTester() Creates a new VF2IsomorphismTester instance

Method Summary

Methods

Modifier and Type	Method and Description
protected State	makeInitialState(Graph<? extends Edge> g1, Graph<? extends Edge> g2) Returns a new State for running the VF2 algorithm.

Methods inherited from class edu.ucla.sspace.graph.isomorphism.AbstractIsomorphismTester

areIsomorphic, findIsomorphism

Methods inherited from class java.lang.Object

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

Constructor Detail

VF2IsomorphismTester

public VF2IsomorphismTester()

Creates a new VF2IsomorphismTester instance

Method Detail

makeInitialState

protected State makeInitialState(Graph<? extends Edge> g1,
                     Graph<? extends Edge> g2)

Returns a new State for running the VF2 algorithm.

Specified by:

makeInitialState in class AbstractIsomorphismTester