N
- The node type.E
- The edge type.public final class CheckPathsBetweenNodes<N,E>
extends java.lang.Object
#CheckPathsBetweenNodes(DiGraph,
DiGraphNode, DiGraphNode, Predicate, Predicate)
, for a
description of this algorithm.Modifier and Type | Field and Description |
---|---|
private static Annotation |
BACK_EDGE |
private static Annotation |
BLACK |
private com.google.common.base.Predicate<DiGraph.DiGraphEdge<N,E>> |
edgePredicate |
private DiGraph.DiGraphNode<N,E> |
end |
private DiGraph<N,E> |
graph |
private static Annotation |
GRAY |
private boolean |
inclusive |
private com.google.common.base.Predicate<N> |
nodePredicate |
private DiGraph.DiGraphNode<N,E> |
start |
private static Annotation |
VISITED_EDGE |
private static Annotation |
WHITE |
Constructor and Description |
---|
CheckPathsBetweenNodes(DiGraph<N,E> graph,
DiGraph.DiGraphNode<N,E> a,
DiGraph.DiGraphNode<N,E> b,
com.google.common.base.Predicate<N> nodePredicate,
com.google.common.base.Predicate<DiGraph.DiGraphEdge<N,E>> edgePredicate)
Inclusive check.
|
CheckPathsBetweenNodes(DiGraph<N,E> graph,
DiGraph.DiGraphNode<N,E> a,
DiGraph.DiGraphNode<N,E> b,
com.google.common.base.Predicate<N> nodePredicate,
com.google.common.base.Predicate<DiGraph.DiGraphEdge<N,E>> edgePredicate,
boolean inclusive)
Given a graph G with nodes A and B, this algorithm determines if all paths
from A to B contain at least one node satisfying a given predicate.
|
Modifier and Type | Method and Description |
---|---|
boolean |
allPathsSatisfyPredicate() |
private boolean |
checkAllPathsWithoutBackEdges(DiGraph.DiGraphNode<N,E> a,
DiGraph.DiGraphNode<N,E> b)
Verify that all non-looping paths from
a to b pass
through at least one node where nodePredicate is true. |
private boolean |
checkSomePathsWithoutBackEdges(DiGraph.DiGraphNode<N,E> a,
DiGraph.DiGraphNode<N,E> b)
Verify that some non-looping paths from
a to b pass
through at least one node where nodePredicate is true. |
private void |
discoverBackEdges(DiGraph.DiGraphNode<N,E> u) |
private boolean |
ignoreEdge(DiGraph.DiGraphEdge<N,E> e) |
private void |
setUp() |
boolean |
somePathsSatisfyPredicate() |
private void |
tearDown() |
private final com.google.common.base.Predicate<N> nodePredicate
private final com.google.common.base.Predicate<DiGraph.DiGraphEdge<N,E>> edgePredicate
private final boolean inclusive
private static final Annotation BACK_EDGE
private static final Annotation VISITED_EDGE
private static final Annotation WHITE
private static final Annotation GRAY
private static final Annotation BLACK
private final DiGraph.DiGraphNode<N,E> start
private final DiGraph.DiGraphNode<N,E> end
CheckPathsBetweenNodes(DiGraph<N,E> graph, DiGraph.DiGraphNode<N,E> a, DiGraph.DiGraphNode<N,E> b, com.google.common.base.Predicate<N> nodePredicate, com.google.common.base.Predicate<DiGraph.DiGraphEdge<N,E>> edgePredicate, boolean inclusive)
graph
- Graph G to analyze.a
- The node A.b
- The node B.nodePredicate
- Predicate which at least one node on each path from an
A node to B (inclusive) must match.edgePredicate
- Edges to consider as part of the graph. Edges in
graph that don't match edgePredicate will be ignored.inclusive
- Includes node A and B in the test for the node predicate.public CheckPathsBetweenNodes(DiGraph<N,E> graph, DiGraph.DiGraphNode<N,E> a, DiGraph.DiGraphNode<N,E> b, com.google.common.base.Predicate<N> nodePredicate, com.google.common.base.Predicate<DiGraph.DiGraphEdge<N,E>> edgePredicate)
public boolean allPathsSatisfyPredicate()
public boolean somePathsSatisfyPredicate()
private void setUp()
private void tearDown()
private void discoverBackEdges(DiGraph.DiGraphNode<N,E> u)
private boolean ignoreEdge(DiGraph.DiGraphEdge<N,E> e)
private boolean checkAllPathsWithoutBackEdges(DiGraph.DiGraphNode<N,E> a, DiGraph.DiGraphNode<N,E> b)
a
to b
pass
through at least one node where nodePredicate
is true.private boolean checkSomePathsWithoutBackEdges(DiGraph.DiGraphNode<N,E> a, DiGraph.DiGraphNode<N,E> b)
a
to b
pass
through at least one node where nodePredicate
is true.