infovis.graph.algorithm
Class BFSVisitor

java.lang.Object
  extended by infovis.graph.algorithm.BFSVisitor
All Implemented Interfaces:
BreadthFirst.Visitor

public class BFSVisitor
extends Object
implements BreadthFirst.Visitor

Basic implementation of the BreathFirst.Visitor interface

Version:
$Revision: 1.1 $
Author:
Jean-Daniel Fekete

Constructor Summary
BFSVisitor()
           
 
Method Summary
 void blackTarget(int edge)
          Invoked (in addition to non_tree_edge()) if the target vertex is colored black at the time of examination.
 void discoverVertex(int vertex)
          Invoked the first time the algorithm encounters vertex u .
 void examineEdge(int edge)
          Invoked on every out-edge of each vertex immediately after the vertex is removed from the queue.
 void examineVertex(int vertex)
          Invoked in each vertex as it is removed from the queue
 void finishVertex(int vertex)
          Invoked after all of the out edges of u have been examined and all of the adjacent vertices have been discovered.
 void greyTarget(int edge)
          Invoked (in addition to non_tree_edge()) if the target vertex is colored grey at the time of examination.
 void initializeVertex(int vertex)
          Invoked on every vertex before the start of the search.
 void nonTreeEdge(int edge)
          Invoked (in addition to examine_edge()) if the edge is not a tree edge.
 void startVertex(int vertex)
          Invoked on every vertex before the start of the search.
 void treeEdge(int edge)
          Invoked (in addition to examine_edge()) if the edge is a tree edge.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BFSVisitor

public BFSVisitor()
Method Detail

initializeVertex

public void initializeVertex(int vertex)
Description copied from interface: BreadthFirst.Visitor
Invoked on every vertex before the start of the search.

Specified by:
initializeVertex in interface BreadthFirst.Visitor
Parameters:
vertex - the Vertex

blackTarget

public void blackTarget(int edge)
Description copied from interface: BreadthFirst.Visitor
Invoked (in addition to non_tree_edge()) if the target vertex is colored black at the time of examination. The color black indicates that the vertex is no longer in the queue.

Specified by:
blackTarget in interface BreadthFirst.Visitor
Parameters:
edge - the Edge

discoverVertex

public void discoverVertex(int vertex)
Description copied from interface: BreadthFirst.Visitor
Invoked the first time the algorithm encounters vertex u . All vertices closer to the source vertex have been discovered, and vertices further from the source have not yet been discovered.

Specified by:
discoverVertex in interface BreadthFirst.Visitor
Parameters:
vertex - the Vertex

examineEdge

public void examineEdge(int edge)
Description copied from interface: BreadthFirst.Visitor
Invoked on every out-edge of each vertex immediately after the vertex is removed from the queue.

Specified by:
examineEdge in interface BreadthFirst.Visitor
Parameters:
edge - the Edge

examineVertex

public void examineVertex(int vertex)
Description copied from interface: BreadthFirst.Visitor
Invoked in each vertex as it is removed from the queue

Specified by:
examineVertex in interface BreadthFirst.Visitor
Parameters:
vertex - the Vertex

finishVertex

public void finishVertex(int vertex)
Description copied from interface: BreadthFirst.Visitor
Invoked after all of the out edges of u have been examined and all of the adjacent vertices have been discovered.

Specified by:
finishVertex in interface BreadthFirst.Visitor
Parameters:
vertex - the Vertex

greyTarget

public void greyTarget(int edge)
Description copied from interface: BreadthFirst.Visitor
Invoked (in addition to non_tree_edge()) if the target vertex is colored grey at the time of examination. The color grey indicates that the vertex is currently in the queue.

Specified by:
greyTarget in interface BreadthFirst.Visitor
Parameters:
edge - the Edge

nonTreeEdge

public void nonTreeEdge(int edge)
Description copied from interface: BreadthFirst.Visitor
Invoked (in addition to examine_edge()) if the edge is not a tree edge.

Specified by:
nonTreeEdge in interface BreadthFirst.Visitor
Parameters:
edge - the Edge

startVertex

public void startVertex(int vertex)
Description copied from interface: BreadthFirst.Visitor
Invoked on every vertex before the start of the search.

Specified by:
startVertex in interface BreadthFirst.Visitor
Parameters:
vertex - the Vertex

treeEdge

public void treeEdge(int edge)
Description copied from interface: BreadthFirst.Visitor
Invoked (in addition to examine_edge()) if the edge is a tree edge. The target vertex of edge e is discovered at this time.

Specified by:
treeEdge in interface BreadthFirst.Visitor
Parameters:
edge - the Edge


Copyright 2005 by Jean-Daniel Fekete and INRIA, France All rights reserved.