edu.ucla.sspace.graph.isomorphism

Class VF2State

java.lang.Object

edu.ucla.sspace.graph.isomorphism.VF2State

All Implemented Interfaces:

State

public class VF2State
extends Object
implements State

A State implementation for testing isomorphism using the VF2 algorithm's logic. Note that this implementation requires that the graphs have contiguous vertex indices (beginning at 0 to g.order()-1.

This implementation is based on the vf2_state implemenation in VFLib.

Field Summary

Fields inherited from interface edu.ucla.sspace.graph.isomorphism.State

NULL_NODE

Constructor Summary

Constructors

Modifier	Constructor and Description
	VF2State(Graph<? extends Edge> g1, Graph<? extends Edge> g2) Creates a new VF2State with an empty mapping between the two graphs.
protected	VF2State(VF2State copy)

Method Summary

Methods

Modifier and Type	Method and Description
void	addPair(int node1, int node2) Adds the two vertices to this State's vertex mapping.
protected boolean	areCompatableVertices(int v1, int v2)
protected boolean	areCompatibleEdges(int v1, int v2, int v3, int v4)
void	backTrack() Undoes the mapping added in the prior call to addPair.
VF2State	copy() Makes a shallow copy of the content of this state.
Graph<? extends Edge>	getGraph1() Returns the first graph being matched
Graph<? extends Edge>	getGraph2() Returns the first graph being matched
Map<Integer,Integer>	getVertexMapping() Returns the current mapping between vertices.
boolean	isDead() Returns true if the current state of mapping cannot proceed because some invalid mapping has occurred and no further pairs would result in an isomorphic match.
boolean	isFeasiblePair(int node1, int node2) Returns true if mapping node1 to node2 would preseve the isomorphism between the graphs to the extend that their vertices have been mapped thusfar.
boolean	isGoal() Returns true if all the vertices have been mapped.
Pair<Integer>	nextPair(int prevN1, int prevN2) Returns the next candidate for isomorphic matching given these prior two vertices that were matched.

Methods inherited from class java.lang.Object

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

Constructor Detail

VF2State

public VF2State(Graph<? extends Edge> g1,
        Graph<? extends Edge> g2)

Creates a new VF2State with an empty mapping between the two graphs.

VF2State

protected VF2State(VF2State copy)

Method Detail

getGraph1

public Graph<? extends Edge> getGraph1()

Returns the first graph being matched

Specified by:

getGraph1 in interface State

getGraph2

public Graph<? extends Edge> getGraph2()

Returns the first graph being matched

Specified by:

getGraph2 in interface State

nextPair

public Pair<Integer> nextPair(int prevN1,
                     int prevN2)

Returns the next candidate for isomorphic matching given these prior two vertices that were matched. If prevN1 and prevN1 are NULL_NODE, this should return the initial candidate.

Specified by:

nextPair in interface State

areCompatibleEdges

protected boolean areCompatibleEdges(int v1,
                         int v2,
                         int v3,
                         int v4)

areCompatableVertices

protected boolean areCompatableVertices(int v1,
                            int v2)

isFeasiblePair

public boolean isFeasiblePair(int node1,
                     int node2)

Returns true if mapping node1 to node2 would preseve the isomorphism between the graphs to the extend that their vertices have been mapped thusfar.

Specified by:

isFeasiblePair in interface State

addPair

public void addPair(int node1,
           int node2)

Adds the two vertices to this State's vertex mapping.

Specified by:

addPair in interface State

isGoal

public boolean isGoal()

Returns true if all the vertices have been mapped. Equivalently, returns true if the graphs are isomorphic.

Specified by:

isGoal in interface State

isDead

public boolean isDead()

Returns true if the current state of mapping cannot proceed because some invalid mapping has occurred and no further pairs would result in an isomorphic match.

Specified by:

isDead in interface State

getVertexMapping

public Map<Integer,Integer> getVertexMapping()

Returns the current mapping between vertices.

Specified by:

getVertexMapping in interface State

copy

public VF2State copy()

Makes a shallow copy of the content of this state.

Specified by:

copy in interface State

backTrack

public void backTrack()

Undoes the mapping added in the prior call to addPair.

Specified by:

backTrack in interface State