Package com.ibm.wala.util.graph.traverse
Class DFSPathFinder<T>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractList<E>
-
- java.util.Vector<E>
-
- java.util.Stack<T>
-
- com.ibm.wala.util.graph.traverse.DFSPathFinder<T>
-
- All Implemented Interfaces:
Serializable
,Cloneable
,Iterable<T>
,Collection<T>
,List<T>
,RandomAccess
- Direct Known Subclasses:
DFSAllPathsFinder
public class DFSPathFinder<T> extends Stack<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 Map<Object,Iterator<? extends T>>
pendingChildren
An iterator of child nodes for each node being searchedstatic long
serialVersionUID
-
Fields inherited from class java.util.Vector
capacityIncrement, elementCount, elementData
-
Fields inherited from class java.util.AbstractList
modCount
-
-
Constructor Summary
Constructors Constructor Description DFSPathFinder(Graph<T> G, Iterator<T> nodes, 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, 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 List<T>
currentPath()
List<T>
find()
protected Iterator<? extends T>
getConnected(T n)
get the out edges of a given nodeprotected 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, Iterator<? extends T> iterator)
Method setPendingChildren.-
Methods inherited from class java.util.Vector
add, add, addAll, addAll, addElement, capacity, clear, clone, contains, containsAll, copyInto, elementAt, elements, ensureCapacity, equals, firstElement, forEach, get, hashCode, indexOf, indexOf, insertElementAt, isEmpty, iterator, lastElement, lastIndexOf, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, removeAllElements, removeElement, removeElementAt, removeIf, removeRange, replaceAll, retainAll, set, setElementAt, setSize, size, sort, spliterator, subList, toArray, toArray, toString, trimToSize
-
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.util.Collection
parallelStream, stream, toArray
-
-
-
-
Constructor Detail
-
DFSPathFinder
public DFSPathFinder(Graph<T> G, T N, Predicate<T> f) throws IllegalArgumentException
Construct a depth-first enumerator starting with a particular node in a directed graph.- Parameters:
G
- the graph whose nodes to enumerate- Throws:
IllegalArgumentException
- if G is null
-
-
Method Detail
-
find
public 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.
-
hasNext
public boolean hasNext()
Return whether there are any more nodes left to enumerate.- Returns:
- true if there nodes left to enumerate.
-
getPendingChildren
protected Iterator<? extends T> getPendingChildren(T n)
Method getPendingChildren.- Returns:
- Object
-
setPendingChildren
protected void setPendingChildren(T v, Iterator<? extends T> iterator)
Method setPendingChildren.- Parameters:
v
-iterator
-
-
-