Package org.jgrapht.alg.isomorphism
Class VF2State<V,E>
- java.lang.Object
-
- org.jgrapht.alg.isomorphism.VF2State<V,E>
-
- Type Parameters:
V
- the type of the verticesE
- the type of the edges
- Direct Known Subclasses:
VF2GraphIsomorphismState
,VF2SubgraphIsomorphismState
abstract class VF2State<V,E> extends java.lang.Object
controls the matching between two graphs according to the VF2 algorithm.
-
-
Field Summary
Fields Modifier and Type Field Description protected int
addedVertex1
protected int
addVertex1
protected int
addVertex2
protected int[]
core1
protected int[]
core2
protected int
coreLen
protected static boolean
DEBUG
protected java.util.Comparator<E>
edgeComparator
protected GraphOrdering<V,E>
g1
protected GraphOrdering<V,E>
g2
protected int[]
in1
protected int[]
in2
protected int
n1
protected int
n2
static int
NULL_NODE
protected int[]
out1
protected int[]
out2
protected int
t1BothLen
protected int
t1InLen
protected int
t1OutLen
protected int
t2BothLen
protected int
t2InLen
protected int
t2OutLen
protected java.util.Comparator<V>
vertexComparator
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
addPair()
adds the pair to the current matching.protected boolean
areCompatibleEdges(int v1, int v2, int u1, int u2)
checks the edges from v1 to v2 and from u1 to u2 for semantic equivalenceprotected boolean
areCompatibleVertexes(int v1, int v2)
checks the vertices v1 and v2 for semantic equivalencevoid
backtrack()
removes the last added pair from the matchingIsomorphicGraphMapping<V,E>
getCurrentMapping()
abstract boolean
isFeasiblePair()
boolean
isGoal()
boolean
nextPair()
calculates a pair of nodes which may be added to the current matching, according to the VF2 algorithm.void
resetAddVertexes()
protected void
showLog(java.lang.String method, java.lang.String str)
creates the debug output only if DEBUG is true.
-
-
-
Field Detail
-
NULL_NODE
public static final int NULL_NODE
- See Also:
- Constant Field Values
-
DEBUG
protected static final boolean DEBUG
- See Also:
- Constant Field Values
-
core1
protected int[] core1
-
core2
protected int[] core2
-
in1
protected int[] in1
-
in2
protected int[] in2
-
out1
protected int[] out1
-
out2
protected int[] out2
-
coreLen
protected int coreLen
-
n1
protected int n1
-
n2
protected int n2
-
t1BothLen
protected int t1BothLen
-
t2BothLen
protected int t2BothLen
-
t1InLen
protected int t1InLen
-
t2InLen
protected int t2InLen
-
t1OutLen
protected int t1OutLen
-
t2OutLen
protected int t2OutLen
-
addedVertex1
protected int addedVertex1
-
addVertex1
protected int addVertex1
-
addVertex2
protected int addVertex2
-
g1
protected GraphOrdering<V,E> g1
-
g2
protected GraphOrdering<V,E> g2
-
vertexComparator
protected java.util.Comparator<V> vertexComparator
-
edgeComparator
protected java.util.Comparator<E> edgeComparator
-
-
Constructor Detail
-
VF2State
public VF2State(GraphOrdering<V,E> g1, GraphOrdering<V,E> g2, java.util.Comparator<V> vertexComparator, java.util.Comparator<E> edgeComparator)
- Parameters:
g1
- GraphOrdering on first graphg2
- GraphOrdering on second graph (possible subgraph)vertexComparator
- comparator for semantic equality of verticesedgeComparator
- comparator for semantic equality of edges
-
-
Method Detail
-
nextPair
public boolean nextPair()
calculates a pair of nodes which may be added to the current matching, according to the VF2 algorithm.- Returns:
- false, if there are no more pairs left
-
addPair
public void addPair()
adds the pair to the current matching.
-
isGoal
public boolean isGoal()
- Returns:
- is the matching already complete?
-
isFeasiblePair
public abstract boolean isFeasiblePair()
- Returns:
- true, if the already matched vertices of graph1 plus the first vertex of nextPair are isomorphic to the already matched vertices of graph2 and the second one vertex of nextPair.
-
backtrack
public void backtrack()
removes the last added pair from the matching
-
areCompatibleVertexes
protected boolean areCompatibleVertexes(int v1, int v2)
checks the vertices v1 and v2 for semantic equivalence- Parameters:
v1
-v2
-- Returns:
- v1 and v2 are equivalent
-
areCompatibleEdges
protected boolean areCompatibleEdges(int v1, int v2, int u1, int u2)
checks the edges from v1 to v2 and from u1 to u2 for semantic equivalence- Parameters:
v1
-v2
-u1
-u2
-- Returns:
- edges are equivalent
-
getCurrentMapping
public IsomorphicGraphMapping<V,E> getCurrentMapping()
-
resetAddVertexes
public void resetAddVertexes()
-
showLog
protected void showLog(java.lang.String method, java.lang.String str)
creates the debug output only if DEBUG is true.- Parameters:
method
-str
-
-
-