Class DFS
java.lang.Object
com.ibm.wala.util.graph.traverse.DFS
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionstatic <T> Set
<T> getReachableNodes
(Graph<T> G) Perform a DFS and return the set of all nodes visited.static <T> Set
<T> getReachableNodes
(Graph<T> G, Collection<? extends T> C) Perform a DFS starting with a particular node set and return the set of all nodes visited.static <T> Collection
<T> getReachableNodes
(Graph<T> G, Collection<? extends T> C, Predicate<? super T> filter) Perform a DFS starting with a particular node and return the set of all nodes visited.static <T> DFSDiscoverTimeIterator
<T> iterateDiscoverTime
(Graph<T> G) static <T> Iterator
<T> iterateDiscoverTime
(Graph<T> G, Iterator<T> roots) static <T> DFSDiscoverTimeIterator
<T> iterateDiscoverTime
(Graph<T> G, T N) static <T> DFSFinishTimeIterator
<T> iterateFinishTime
(Graph<T> G) static <T> DFSFinishTimeIterator
<T> iterateFinishTime
(Graph<T> G, @Nullable Iterator<? extends T> ie) static <T> SortedSet
<T> sortByDepthFirstOrder
(Graph<T> G, T n) Perform a DFS of a graph starting with a specified node and return a sorted list of nodes.
-
Constructor Details
-
DFS
public DFS()
-
-
Method Details
-
getReachableNodes
public static <T> Collection<T> getReachableNodes(Graph<T> G, Collection<? extends T> C, Predicate<? super T> filter) Perform a DFS starting with a particular node and return the set of all nodes visited.- Parameters:
C
- collection of nodes to start fromfilter
- only traverse nodes that need this filter- Throws:
IllegalArgumentException
- if C is null
-
getReachableNodes
Perform a DFS starting with a particular node set and return the set of all nodes visited.- Parameters:
G
- the graph containing n- Returns:
- Set
- Throws:
IllegalArgumentException
- if C is null
-
getReachableNodes
Perform a DFS and return the set of all nodes visited.- Parameters:
G
- the graph containing n- Returns:
- Set
- Throws:
IllegalArgumentException
- if G == null
-
sortByDepthFirstOrder
Perform a DFS of a graph starting with a specified node and return a sorted list of nodes. The nodes are sorted by depth first order.- Parameters:
G
- a graphn
- the initial node- Returns:
- a sorted set of nodes in the graph in depth first order
-
iterateDiscoverTime
- Returns:
- iterator of nodes of G in order of DFS discover time
-
iterateDiscoverTime
public static <T> Iterator<T> iterateDiscoverTime(Graph<T> G, Iterator<T> roots) throws IllegalArgumentException - Parameters:
roots
- roots of traversal, in order to visit in outermost loop of DFS- Returns:
- iterator of nodes of G in order of DFS discover time
- Throws:
IllegalArgumentException
- if roots == null
-
iterateDiscoverTime
- Parameters:
N
- root of traversal- Returns:
- iterator of nodes of G in order of DFS discover time
-
iterateFinishTime
public static <T> DFSFinishTimeIterator<T> iterateFinishTime(Graph<T> G) throws IllegalArgumentException - Parameters:
G
- a graph- Returns:
- iterator of nodes of G in order of DFS finish time
- Throws:
IllegalArgumentException
- if G == null
-
iterateFinishTime
public static <T> DFSFinishTimeIterator<T> iterateFinishTime(Graph<T> G, @Nullable Iterator<? extends T> ie) - Parameters:
G
- a graphie
- roots of traversal, in order to visit in outermost loop of DFS- Returns:
- iterator of nodes of G in order of DFS finish time
-