jdsl.graph.algo
Class BFS

java.lang.Object
  |
  +--jdsl.graph.algo.BFS
Direct Known Subclasses:
DBFS

public abstract class BFS
extends java.lang.Object

Class implementing an abstract Breadth First Search. This abstract algorithmic template may be extended to solve a variety of problems on either directed or undirected graphs.

Author:
Andrew Schwerin

Field Summary
protected static java.lang.Object CROSS_EDGE
          Constant signifying that an edge stored in markedEdges is a cross edge.
protected static java.lang.Object DISCOVERY_EDGE
          Constant signifying that an edge stored in markedEdges is a discovery edge.
protected  InspectableGraph graph
          The graph on which the algorithm is currently executing.
 
Constructor Summary
BFS()
           
 
Method Summary
protected  int depth(Vertex v)
           
 java.lang.Object execute(InspectableGraph g, Vertex start, java.lang.Object info)
          Executes a breadth first search (BFS).
protected abstract  void finishVisit(Vertex v)
          Abstract method called on a vertex at the end of a visit (after all of its untraversed edges have been traversed).
protected abstract  void initialize(Vertex v, java.lang.Object info)
          Abstract method to initialize the object at the beginning of a BFS execution.
protected abstract  EdgeIterator interestingEdges(Vertex v)
          Abstract method that returns an iterator over those edges incident to the parameter vertex in the graph which should be considered for exploration.
protected  boolean isCrossEdge(Edge e)
           
protected  boolean isDiscoveryEdge(Edge e)
           
protected  boolean isMarked(Edge e)
           
protected  boolean isMarked(Vertex v)
           
protected  void mark(Edge e, java.lang.Object kind)
          Marks e as being of type kind.
protected  void mark(Vertex v, int depth)
          Marks v as being of depth depth in the BFS tree created by this BFS.
protected abstract  java.lang.Object result()
          Abstract method called at the very end of the BFS execution.
protected abstract  void startVisit(Vertex v)
          Abstract method called on a vertex when it is visited.
protected abstract  void traverseCross(Edge e, Vertex v, Vertex w)
          Abstract method called when traversing a cross edge.
protected abstract  void traverseDiscovery(Edge e, Vertex parent, Vertex child)
          Abstract method called when traversing a disocvery edge.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DISCOVERY_EDGE

protected static final java.lang.Object DISCOVERY_EDGE
Constant signifying that an edge stored in markedEdges is a discovery edge.

CROSS_EDGE

protected static final java.lang.Object CROSS_EDGE
Constant signifying that an edge stored in markedEdges is a cross edge.

graph

protected InspectableGraph graph
The graph on which the algorithm is currently executing.
Constructor Detail

BFS

public BFS()
Method Detail

execute

public java.lang.Object execute(InspectableGraph g,
                                Vertex start,
                                java.lang.Object info)
Executes a breadth first search (BFS).
Parameters:
InspectableGraph - The graph on which to perform the BFS
Vertex - The Vertex at which to start (the root of the BFS tree)
Object - Should store any auxilary information needed for successful execution of subclasses. This variable is passed on to the initialize(.) method, which should be redefined by the user.
Returns:
Object The result of the execution as returned by the protected method result(.)

initialize

protected abstract void initialize(Vertex v,
                                   java.lang.Object info)
Abstract method to initialize the object at the beginning of a BFS execution. Must be reimplemented by subclasses.
Parameters:
Vertex - v The start vertex in the call to execute(.)
Object - info The Object info passed to execute(.). Should contain any extra data needed by subclasses of BFS.

startVisit

protected abstract void startVisit(Vertex v)
Abstract method called on a vertex when it is visited. Visitation of a vertex occurs during the exploration of all vertices at its depth. Depth may be found for the parameter vertex by calling the depth(Vertex) method. Must be reimplemented by subclasses.
Parameters:
Vertex - v The vertex for which the visit is now starting

finishVisit

protected abstract void finishVisit(Vertex v)
Abstract method called on a vertex at the end of a visit (after all of its untraversed edges have been traversed). Must be reimplemented by subclasses
Parameters:
Vertex - The vertex for which the visit is now ending.

interestingEdges

protected abstract EdgeIterator interestingEdges(Vertex v)
Abstract method that returns an iterator over those edges incident to the parameter vertex in the graph which should be considered for exploration. Subclasses of BFS may implement this method so as to traverse edges as though they were undirected or to traverse the directed edges in the forward or reverse directions, or to in some other way hand pick which edges were of interest for exploration.
Parameters:
Vertex - The vertex for which interesting incident edges shouldbe returned
Returns:
An iterator over interesting edges incident to the parameter Vertex

traverseDiscovery

protected abstract void traverseDiscovery(Edge e,
                                          Vertex parent,
                                          Vertex child)
Abstract method called when traversing a disocvery edge. This method must be reimplemented by subclasses.

Note that the difference in depth between parent and child is exactly one.

Parameters:
Edge - e The discovery edge being traversed
Vertex - parent The vertex incident to e with lesser depth in the BFS tree.
Vertex - child The vertex incident to e with greater depth in the BFS tree.

traverseCross

protected abstract void traverseCross(Edge e,
                                      Vertex v,
                                      Vertex w)
Abstract method called when traversing a cross edge. This method must be reimplemented by subclasses.

Note that the difference in depth between parent and child is not necessarily exactly one, although the depth of both nodes is known.

Parameters:
Edge - e The cross edge being traversed
Vertex - v The vertex to which e is incident that is being visited currently.
Vertex - w The vertex opposite v along e.

result

protected abstract java.lang.Object result()
Abstract method called at the very end of the BFS execution.
Returns:
Object The result of the BFS computation performed by a concrete subclass.

mark

protected void mark(Edge e,
                    java.lang.Object kind)
Marks e as being of type kind.
Parameters:
Edge - e The edge to mark
Object - kind either DISCOVERY_EDGE, or CROSS_EDGE.

isMarked

protected boolean isMarked(Edge e)
Returns:
boolean true iff edge e has been marked as either a discovery edge (DISCOVERY_EDGE) or a cross edge (CROSS_EDGE).

isDiscoveryEdge

protected boolean isDiscoveryEdge(Edge e)
Returns:
boolean true iff edge e has been marked as a discovery edge (DISCOVERY_EDGE).

isCrossEdge

protected boolean isCrossEdge(Edge e)
Returns:
boolean true iff edge e has been marked as a cross edge (CROSS_EDGE).

mark

protected void mark(Vertex v,
                    int depth)
Marks v as being of depth depth in the BFS tree created by this BFS.
Parameters:
Vertex - v the vertex to mark
int - depth The depth of v in the BFS tree.

isMarked

protected boolean isMarked(Vertex v)
Returns:
boolean true iff vertex v has been marked with a depth.

depth

protected int depth(Vertex v)
Returns:
int The depth of v or -1 if v has not yet been marked.