com.ibm.wala.util.graph.traverse
Class DFSVisit

java.lang.Object
  com.ibm.wala.util.graph.traverse.DFSVisit

public class DFSVisit
extends java.lang.Object

Depth first search of a graph using a stack instead of recursive method calls. It allows each vertice of the graph to be visited when its is first discovered and when it is "finished" (i.e. completely processed).

Nested Class Summary

static class	DFSVisit.DefaultSimpleMap<K,V> Default implementation of DFSVisit.SimpleMapbased on a HashMap
static class	DFSVisit.NumberedSimpleMap<K,V> A DFSVisit.SimpleMapthat maps INodeWithNumberto their traversal state.
static interface	DFSVisit.SimpleMap<K,V> A simple map interface.
static class	DFSVisit.Visitor A visitor that visits Nodes in the DFS2 of a graph

Field Summary

static java.util.Iterator

EMPTY_ITERATOR the empty iterator constant

Constructor Summary

DFSVisit()

Method Summary

static <T> void	DFS(Graph<T> g, DFSVisit.Visitor visitor) Depth first search of a graph using a stack instead of recursive method calls.
static <T> void	DFS(Graph<T> g, java.util.Iterator<? extends T> nodes, DFSVisit.Visitor visitor) Depth first search of a graph using a stack instead of recursive method calls.
static <T> void	DFS(Graph<T> g, java.util.Iterator<? extends T> nodes, DFSVisit.Visitor visitor, DFSVisit.SimpleMap<T,java.util.Iterator<? extends T>> states) Depth first search of a graph using a stack instead of recursive method calls.
protected static <T> java.util.Iterator<? extends T>	getConnectedTo(Graph<T> g, T node)

Methods inherited from class java.lang.Object

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

Field Detail

EMPTY_ITERATOR

public static final java.util.Iterator EMPTY_ITERATOR

the empty iterator constant

Constructor Detail

DFSVisit

public DFSVisit()

Method Detail

getConnectedTo

protected static <T> java.util.Iterator<? extends T> getConnectedTo(Graph<T> g,
                                                                    T node)

DFS

public static <T> void DFS(Graph<T> g,
                           java.util.Iterator<? extends T> nodes,
                           DFSVisit.Visitor visitor,
                           DFSVisit.SimpleMap<T,java.util.Iterator<? extends T>> states)

Depth first search of a graph using a stack instead of recursive method calls. This is necessary in order to avoid java.lang.StackOverflowError for big graphs

Parameters:

g - the graph to traverse

nodes - an iterator over the nodes where the traversal should start

visitor - the visitor to notify when nodes are discovered and finished

states - the map to use to store and retrieve the state of nodes

DFS

public static <T> void DFS(Graph<T> g,
                           java.util.Iterator<? extends T> nodes,
                           DFSVisit.Visitor visitor)

Depth first search of a graph using a stack instead of recursive method calls. This is necessary in order to avoid java.lang.StackOverflowError for big graphs

Parameters:

g - the graph to traverse

nodes - an iterator over the nodes where the traversal should start

visitor - the visitor to notify when nodes are discovered and finished

DFS

public static <T> void DFS(Graph<T> g,
                           DFSVisit.Visitor visitor)

Depth first search of a graph using a stack instead of recursive method calls. This is necessary in order to avoid java.lang.StackOverflowError for big graphs

Parameters:

g - the graph to traverse

visitor - the visitor to notify when nodes are discovered and finished

Throws:

java.lang.IllegalArgumentException - if g is null