Package com.ibm.wala.util.graph.traverse

Class DFS

java.lang.Object

com.ibm.wala.util.graph.traverse.DFS

public class DFS
extends Object

utilities related to depth-first search.

Constructor Summary

Constructors

Constructor	Description
DFS()

Method Summary

Modifier and Type	Method	Description
static <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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 from

filter - only traverse nodes that need this filter

Throws:

IllegalArgumentException - if C is null

getReachableNodes

public 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.

Parameters:

G - the graph containing n

Returns:

Set

Throws:

IllegalArgumentException - if C is null

getReachableNodes

public static <T> Set<T> getReachableNodes(Graph<T> G)
                                    throws IllegalArgumentException

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

public 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. The nodes are sorted by depth first order.

Parameters:

G - a graph

n - 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)

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

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 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 graph

ie - roots of traversal, in order to visit in outermost loop of DFS

Returns:

iterator of nodes of G in order of DFS finish time