Package com.ibm.wala.util.graph.traverse
Class DFS
- java.lang.Object
-
- com.ibm.wala.util.graph.traverse.DFS
-
public class DFS extends java.lang.Object
utilities related to depth-first search.
-
-
Constructor Summary
Constructors Constructor Description DFS()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <T> java.util.Set<T>
getReachableNodes(Graph<T> G)
Perform a DFS and return the set of all nodes visited.static <T> java.util.Set<T>
getReachableNodes(Graph<T> G, java.util.Collection<? extends T> C)
Perform a DFS starting with a particular node set and return the set of all nodes visited.static <T> java.util.Collection<T>
getReachableNodes(Graph<T> G, java.util.Collection<? extends T> C, java.util.function.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> java.util.Iterator<T>
iterateDiscoverTime(Graph<T> G, java.util.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, java.util.Iterator<? extends T> ie)
static <T> java.util.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.
-
-
-
Method Detail
-
getReachableNodes
public static <T> java.util.Collection<T> getReachableNodes(Graph<T> G, java.util.Collection<? extends T> C, java.util.function.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:
java.lang.IllegalArgumentException
- if C is null
-
getReachableNodes
public static <T> java.util.Set<T> getReachableNodes(Graph<T> G, java.util.Collection<? extends T> C)
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:
java.lang.IllegalArgumentException
- if C is null
-
getReachableNodes
public static <T> java.util.Set<T> getReachableNodes(Graph<T> G) throws java.lang.IllegalArgumentException
Perform a DFS and return the set of all nodes visited.- Parameters:
G
- the graph containing n- Returns:
- Set
- Throws:
java.lang.IllegalArgumentException
- if G == null
-
sortByDepthFirstOrder
public static <T> java.util.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. 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
public static <T> DFSDiscoverTimeIterator<T> iterateDiscoverTime(Graph<T> G)
- Parameters:
G
-- Returns:
- iterator of nodes of G in order of DFS discover time
-
iterateDiscoverTime
public static <T> java.util.Iterator<T> iterateDiscoverTime(Graph<T> G, java.util.Iterator<T> roots) throws java.lang.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:
java.lang.IllegalArgumentException
- if roots == null
-
iterateDiscoverTime
public static <T> DFSDiscoverTimeIterator<T> iterateDiscoverTime(Graph<T> G, T N)
- 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 java.lang.IllegalArgumentException
- Parameters:
G
- a graph- Returns:
- iterator of nodes of G in order of DFS finish time
- Throws:
java.lang.IllegalArgumentException
- if G == null
-
iterateFinishTime
public static <T> DFSFinishTimeIterator<T> iterateFinishTime(Graph<T> G, java.util.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
-
-