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
controls the matching between two graphs according to the VF2 algorithm.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected int
protected int
protected int
protected final int[]
protected final int[]
protected int
protected static final boolean
protected final Comparator
<E> protected final GraphOrdering
<V, E> protected final GraphOrdering
<V, E> protected final int[]
protected final int[]
protected final int
protected final int
static final int
protected final int[]
protected final int[]
protected int
protected int
protected int
protected int
protected int
protected int
protected final Comparator
<V> -
Constructor Summary
ConstructorsConstructorDescriptionVF2State
(GraphOrdering<V, E> g1, GraphOrdering<V, E> g2, Comparator<V> vertexComparator, Comparator<E> edgeComparator) copy constructor -
Method Summary
Modifier and TypeMethodDescriptionvoid
addPair()
adds the pair to the current matching.protected boolean
areCompatibleEdges
(int v1, int v2, int u1, int u2) checks the edges from $v_1$ to $v_2$ and from $u_1$ to $u_2$ for semantic equivalenceprotected boolean
areCompatibleVertexes
(int v1, int v2) checks the vertices $v_1$ and $v_2$ for semantic equivalencevoid
removes the last added pair from the matchingabstract boolean
boolean
isGoal()
boolean
nextPair()
calculates a pair of nodes which may be added to the current matching, according to the VF2 algorithm.void
protected void
creates the debug output only if DEBUG is true.
-
Field Details
-
NULL_NODE
public static final int NULL_NODE- See Also:
-
DEBUG
protected static final boolean DEBUG- See Also:
-
core1
protected final int[] core1 -
core2
protected final int[] core2 -
in1
protected final int[] in1 -
in2
protected final int[] in2 -
out1
protected final int[] out1 -
out2
protected final int[] out2 -
n1
protected final int n1 -
n2
protected final int n2 -
coreLen
protected int coreLen -
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
-
g2
-
vertexComparator
-
edgeComparator
-
-
Constructor Details
-
VF2State
public VF2State(GraphOrdering<V, E> g1, GraphOrdering<V, E> g2, Comparator<V> vertexComparator, 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
-
VF2State
copy constructor- Parameters:
s
-
-
-
Method Details
-
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 $v_1$ and $v_2$ 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 $v_1$ to $v_2$ and from $u_1$ to $u_2$ for semantic equivalence- Parameters:
v1
-v2
-u1
-u2
-- Returns:
- edges are equivalent
-
getCurrentMapping
-
resetAddVertexes
public void resetAddVertexes() -
showLog
creates the debug output only if DEBUG is true.- Parameters:
method
-str
-
-