com.ibm.wala.util.graph.traverse
Class BFSIterator<T>

java.lang.Object
  com.ibm.wala.util.graph.traverse.BFSIterator<T>

All Implemented Interfaces:

java.util.Iterator<T>

public class BFSIterator<T>
extends java.lang.Object
implements java.util.Iterator<T>

This class implements breadth-first search over a Graph, returning an Iterator of the nodes of the graph in order of discovery. This class follows the outNodes of the graph nodes to define the graph, but this behavior can be changed by overriding the getConnected method.

Field Summary

protected Graph<T>

G Governing Graph

Constructor Summary

BFSIterator(Graph<T> G)
Constructor DFSFinishTimeIterator.

BFSIterator(Graph<T> G, java.util.Iterator<? extends T> nodes)
Construct a breadth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.

BFSIterator(Graph<T> G, T N)
Construct a breadth-first iterator starting with a particular node in a directed graph.

Method Summary

protected java.util.Iterator<? extends T>	getConnected(T n) get the out edges of a given node
boolean	hasNext() Return whether there are any more nodes left to enumerate.
T	next() Find the next graph node in discover time order.
void	remove()

Methods inherited from class java.lang.Object

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

Field Detail

G

protected Graph<T> G

Governing Graph

Constructor Detail

BFSIterator

public BFSIterator(Graph<T> G,
                   T N)

Construct a breadth-first iterator starting with a particular node in a directed graph.

Parameters:

G - the graph whose nodes to enumerate

Throws:

java.lang.IllegalArgumentException - if G is null

BFSIterator

public BFSIterator(Graph<T> G,
                   java.util.Iterator<? extends T> nodes)

Construct a breadth-first enumerator across the (possibly improper) subset of nodes reachable from the nodes in the given enumeration.

Parameters:

nodes - the set of nodes from which to start searching

Throws:

java.lang.IllegalArgumentException - if G is null

BFSIterator

public BFSIterator(Graph<T> G)
            throws java.lang.NullPointerException

Constructor DFSFinishTimeIterator.

Parameters:

G -

Throws:

java.lang.NullPointerException - if G is null

Method Detail

hasNext

public boolean hasNext()

Return whether there are any more nodes left to enumerate.

Specified by:

hasNext in interface java.util.Iterator<T>

Returns:

true if there nodes left to enumerate.

next

public T next()
       throws java.util.NoSuchElementException

Find the next graph node in discover time order.

Specified by:

next in interface java.util.Iterator<T>

Returns:

the next graph node in discover time order.

Throws:

java.util.NoSuchElementException

getConnected

protected java.util.Iterator<? extends T> getConnected(T n)

get the out edges of a given node

Parameters:

n - the node of which to get the out edges

Returns:

the out edges

remove

public void remove()
            throws UnimplementedError

Specified by:

remove in interface java.util.Iterator<T>

Throws:

UnimplementedError

See Also:

Iterator.remove()