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 |
BFS_STEP
public static final int BFS_STEP
- Trace label constant indicating that the algorithm has made one step forward.
BFS
public BFS()
- Constructor creating a
BFS
-object which can perform
BFS on the given Graph
G
starting from Node
s
.
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 algorithmstart
- the starting Node
for the algorithmpropertyID
- 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 algorithmstart
- the starting Node
for the algorithmpropertyID
- the key-prefix under which the results will be stored in
g
's propertiestracer
- the Tracer
which records the algorithm step by step