Package com.ibm.wala.util.graph.traverse
Class DFSPathFinder<T>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractList<E>
-
- java.util.ArrayList<T>
-
- com.ibm.wala.util.graph.traverse.DFSPathFinder<T>
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Cloneable
,java.lang.Iterable<T>
,java.util.Collection<T>
,java.util.List<T>
,java.util.RandomAccess
- Direct Known Subclasses:
DFSAllPathsFinder
public class DFSPathFinder<T> extends java.util.ArrayList<T>
This class searches depth-first search for node that matches some criteria. If found, it reports a path to the first node found. This class follows the outNodes of the graph nodes to define the graph, but this behavior can be changed by overriding the getConnected method.- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description protected Graph<T>
G
The graph to searchprotected java.util.Map<java.lang.Object,java.util.Iterator<? extends T>>
pendingChildren
An iterator of child nodes for each node being searchedstatic long
serialVersionUID
-
Constructor Summary
Constructors Constructor Description DFSPathFinder(Graph<T> G, java.util.Iterator<T> nodes, java.util.function.Predicate<T> f)
Construct a depth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.DFSPathFinder(Graph<T> G, T N, java.util.function.Predicate<T> f)
Construct a depth-first enumerator starting with a particular node in a directed graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected java.util.List<T>
currentPath()
java.util.List<T>
find()
protected java.util.Iterator<? extends T>
getConnected(T n)
get the out edges of a given nodeprotected java.util.Iterator<? extends T>
getPendingChildren(T n)
Method getPendingChildren.boolean
hasNext()
Return whether there are any more nodes left to enumerate.protected void
setPendingChildren(T v, java.util.Iterator<? extends T> iterator)
Method setPendingChildren.-
Methods inherited from class java.util.ArrayList
add, add, addAll, addAll, clear, clone, contains, ensureCapacity, equals, forEach, get, hashCode, indexOf, isEmpty, iterator, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, removeIf, removeRange, replaceAll, retainAll, set, size, sort, spliterator, subList, toArray, toArray, trimToSize
-
-
-
-
Field Detail
-
serialVersionUID
public static final long serialVersionUID
- See Also:
- Constant Field Values
-
pendingChildren
protected final java.util.Map<java.lang.Object,java.util.Iterator<? extends T>> pendingChildren
An iterator of child nodes for each node being searched
-
-
Constructor Detail
-
DFSPathFinder
public DFSPathFinder(Graph<T> G, T N, java.util.function.Predicate<T> f) throws java.lang.IllegalArgumentException
Construct a depth-first enumerator starting with a particular node in a directed graph.- Parameters:
G
- the graph whose nodes to enumerate- Throws:
java.lang.IllegalArgumentException
- if G is null
-
DFSPathFinder
public DFSPathFinder(Graph<T> G, java.util.Iterator<T> nodes, java.util.function.Predicate<T> f)
Construct a depth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.- Parameters:
nodes
- the set of nodes from which to start searching
-
-
Method Detail
-
find
public java.util.List<T> find()
- Returns:
- a List of nodes that specifies the first path found from a root to a node accepted by the filter. Returns null if no path found.
-
currentPath
protected java.util.List<T> currentPath()
-
hasNext
public boolean hasNext()
Return whether there are any more nodes left to enumerate.- Returns:
- true if there nodes left to enumerate.
-
getPendingChildren
protected java.util.Iterator<? extends T> getPendingChildren(T n)
Method getPendingChildren.- Returns:
- Object
-
setPendingChildren
protected void setPendingChildren(T v, java.util.Iterator<? extends T> iterator)
Method setPendingChildren.- Parameters:
v
-iterator
-
-
-