sandmark.util.graph
Class Bfs

java.lang.Object
  |
  +--sandmark.util.graph.Bfs

All Implemented Interfaces:

java.util.Iterator

public class Bfs

extends java.lang.Object

implements java.util.Iterator

Field Summary

(package private) static int	BLACK
(package private) java.util.Iterator	edgeIter
(package private) Graph	graph
(package private) static int	GRAY
(package private) boolean	hasNextPath
(package private) Path	nextPath
(package private) java.util.HashMap	parent
(package private) java.util.ArrayList	queue
(package private) static int	WHITE

Constructor Summary

Bfs(Graph graph, Node root)
Perform a breadth-first-search on a graph from a particular root node.

Method Summary

boolean	hasNext()
static void	main(java.lang.String[] args)
java.lang.Object	next()
void	remove()

Methods inherited from class java.lang.Object

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

Field Detail

WHITE

static final int WHITE

See Also:

Constant Field Values

GRAY

static final int GRAY

See Also:

Constant Field Values

BLACK

static final int BLACK

See Also:

Constant Field Values

queue

java.util.ArrayList queue

graph

Graph graph

edgeIter

java.util.Iterator edgeIter

nextPath

Path nextPath

hasNextPath

boolean hasNextPath

parent

java.util.HashMap parent

Constructor Detail

Bfs

public Bfs(Graph graph,
           Node root)

Perform a breadth-first-search on a graph from a particular root node.

    Bfs d = new Bfs(graph,root);
    while (d.hasNext()) {
       sandmark.util.graph.Path path = (sandmark.util.graph.Path) d.next();
    }
 

We generate a set of paths, where path[0]==root and path[path.length-1] is the node we're currently visiting.

Parameters:

graph - the graph

root - the root node from which we start exploring.

Method Detail

hasNext

public boolean hasNext()

Specified by:

hasNext in interface java.util.Iterator

next

public java.lang.Object next()

Specified by:

next in interface java.util.Iterator

remove

public void remove()

Specified by:

remove in interface java.util.Iterator

main

public static void main(java.lang.String[] args)