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

DFS()

Method Summary

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, Filter filter) Perform a DFS starting with a particular node and return the set of all nodes visited.
static <T> DFSDiscoverTimeIterator	iterateDiscoverTime(Graph<T> G)
static <T> java.util.Iterator<T>	iterateDiscoverTime(Graph<T> G, java.util.Iterator<T> roots)
static <T> DFSDiscoverTimeIterator	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.

Methods inherited from class java.lang.Object

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

Constructor Detail

DFS

public DFS()

Method Detail

getReachableNodes

public static <T> java.util.Collection<T> getReachableNodes(Graph<T> G,
                                                            java.util.Collection<? extends T> C,
                                                            Filter 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:

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 graph

n - the initial node

Returns:

a sorted set of nodes in the graph in depth first order

iterateDiscoverTime

public static <T> DFSDiscoverTimeIterator 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 iterateDiscoverTime(Graph<T> G,
                                                              T N)

Parameters:

G -

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 -

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 -

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