gishur.graph.algorithms
Class BFS

java.lang.Object
  |
  +--gishur.core.algorithms.Algorithm
        |
        +--gishur.graph.algorithms.BFS

public class BFS
extends Algorithm

An Algorithm class to perform the Breadth-first search algorithm on an arbitrary Graph. It is constructed with a Graph. The algorithm can be performed by calling bfs(gishur.graph.core.Graph, gishur.graph.core.Node, java.lang.String) with Node s as source Node. The purpose of BFS is to discover all Nodes reachable from the source Node s, to measure the number of Edges between s and any reachable Node. Besides, it constructs a BFS tree containig all reachable Nodes and only those Edges which are used during BFS. In an unweighted Graph, the paths in this BFS tree are identical to the shortest paths between s and the reachable Nodes. At last, the parent of each Node in the BFS tree (the predecessor) is found by BFS and stored as a result. The BFS starts from the given source Node and checks all neighbours which are on the target end of its outgoing edges. Each not yet discoverd neighbour Node is enqueued as a further candidate for neighbour check. The Nodes whose neighbours have been discoverd completely are coloured black (see constants below), those who have still undiscoverd neighbours are coloured gray and all undiscovered Nodes are coloured white. Thus the algorithm finishes when all reachable Nodes have been coloured black, e.g. the Queue containig the gray Nodes is empty. BFS works both on directed and on undirected Graphs.

Version:
2.0
Author:
Christoph Sachse

Field Summary
static int BFS_STEP
          Trace label constant indicating that the algorithm has made one step forward.
 
Constructor Summary
BFS()
          Constructor creating a BFS-object which can perform BFS on the given Graph G starting from Node s.
 
Method Summary
 void bfs(Graph g, Node start, java.lang.String propertyID)
          Method performing the Breadth-First Search Algorithm on the given Graph.
 void bfs(Graph g, Node start, java.lang.String propertyID, Tracer tracer)
          Method performing the Breadth-First Search Algorithm on the given Graph.
 
Methods inherited from class gishur.core.algorithms.Algorithm
execute, execute, execute, execute, execute, execute, execute, execute, getMethod, getParameter, getParameters, getReturnValue, setMethod, setParameter, setParameters
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

BFS_STEP

public static final int BFS_STEP
Trace label constant indicating that the algorithm has made one step forward.
Constructor Detail

BFS

public BFS()
Constructor creating a BFS-object which can perform BFS on the given Graph G starting from Node s.
Method Detail

bfs

public void bfs(Graph g,
                Node start,
                java.lang.String propertyID)
Method performing the Breadth-First Search Algorithm on the given Graph. The BFS starts at source node start and successively 'discovers' all Nodes reachable from start. The results (the maximal set of reachable Nodes, the Edges of the BFS tree, the distance labels s->u and the predecessor for each reachable Node) are stored as properties of the Graph's Nodes and Edges. They can be read out with GraphElement.getProperty(java.lang.String) and GraphElement.getProperty(java.lang.String) and are defined as follows:

Properties Summary: Nodes
Key Value Type Default value Meaning
BFS.color int gishur.graph.algorithms.BFS.WHITE BFSCursor.BFS_COLOR_WHITE means that this Node has not been discovered by BSF from s. BFSCursor.BFS_COLOR_BLACK means that this Node has been discovered and all his neighbours, too have been discovered. BFSCursor.BFS_COLOR_GRAY means that this Node has been discoverd, but has not been examined for neighbours yet (only occurs during algorithm execution).
BFS.distance int Integer.MAX_VALUE The distance from s to this Node in the BFS tree. If this value is Integer.MAX_VALUE, the Node has not been discovered.
BFS.predecessor gishur.graph.core.SimpleNode null The parent Node of this Node in the BFS tree or null if this Node has not been discovered

Properties Summary: Edges
Key Value Type Default value Meaning
BFS.color int gishur.graph.algorithms.BFS.BLACK BFSCursor.BFS_COLOR_WHITE means that this Edge is part of the BFS tree and BFSCursor.BFS_COLOR_BLACK means that this Edge led to an already discovered Node during BFS and is thus not part of the BFS tree.

Parameters:
g - the Graph on which to perform the algorithm
start - the starting Node for the algorithm
propertyID - the key-prefix under which the results will be stored in g's properties

bfs

public void bfs(Graph g,
                Node start,
                java.lang.String propertyID,
                Tracer tracer)
Method performing the Breadth-First Search Algorithm on the given Graph. The BFS starts at source node start and successively 'discovers' all Nodes reachable from start. The results (the maximal set of reachable Nodes, the Edges of the BFS tree, the distance labels s->u and the predecessor for each reachable Node) are stored as properties of the Graph's Nodes and Edges. They can be read out with GraphElement.getProperty(java.lang.String) and GraphElement.getProperty(java.lang.String) and are defined as follows:

Properties Summary: Nodes
Key Value Type Default value Meaning
BFS.color int gishur.graph.algorithms.BFS.WHITE BFSCursor.BFS_COLOR_WHITE means that this Node has not been discovered by BFS from s. BFSCursor.BFS_COLOR_BLACK means that this Node has been discovered and all his neighbours, too have been discovered. BFSCursor.BFS_COLOR_GRAY means that this Node has been discoverd, but has not been examined for neighbours yet (only occurs during algorithm execution).
BFS.distance int Integer.MAX_VALUE The distance from s to this Node in the BFS tree. If this value is Integer.MAX_VALUE, the Node has not been discovered.
BFS.predecessor gishur.graph.core.SimpleNode null The parent Node of this Node in the BFS tree or null if this Node has not been discovered

Properties Summary: Edges
Key Value Type Default value Meaning
BFS.color int gishur.graph.algorithms.BFS.BLACK BFSCursor.BFS_COLOR_WHITE means that this Edge is part of the BFS tree and BFSCursor.BFS_COLOR_BLACK means that this Edge led to an already discovered Node during BFS and is thus not part of the BFS tree.

Parameters:
g - the Graph on which to perform the algorithm
start - the starting Node for the algorithm
propertyID - the key-prefix under which the results will be stored in g's properties
tracer - the Tracer which records the algorithm step by step