gishur.graph.algorithms
Class DFS
java.lang.Object
|
+--gishur.core.algorithms.Algorithm
|
+--gishur.graph.algorithms.DFS
- public class DFS
- extends Algorithm
Algorithm class performing 'Depth-first search' on a given Graph
g
.
That means it starts discovering g
's Nodes
at an
arbitrarily chosen Node
and goes on discovering Nodes
by moving on to another adjacent Node
whenever possible. If the
algorithm comes to a situation, where there are no further Nodes
to discover from the actual one, it moves backwards to this Node's
predecessor and so on. If it comes back to the starting Node
of one
such procedure and can't find further undiscoverd Nodes
from there,
it starts a new tour at another arbitrarily chosen undiscovered Node
(if there is still one). Each time it starts again in this way, DFS
grows a new DFS
tree. Thus, when DFS
is finished, it leaves
as a result the 'DFS forest' defined by each Node's
predecessor,
which is stored as a property in it (see #execute(Tracer)
).
Another result of DFS
are timestamps (also stored as properties of
the Nodes
). When the algorithm starts, a time counter is set to zero.
Each step, either consisting of the discovery of a new ´Node
or of
the finishing of the visit of an already discoverd one, takes one time unit.
The time when a Node
is first discoverd and the time when the
discovery of all his descendants in the DFS forest is completed are recorded
as properties of this Node
(see #execute(Tracer)}).
DFS works both on directed and on undirected Graphs
.
- Version:
- 1.0
- Author:
- Christoph Sachse
Field Summary |
static int |
DFS_STEP
Trace label constant indicating that the algorithm has made one step forward. |
Constructor Summary |
DFS()
Empty (and only) constructor. |
Method Summary |
void |
dfs(Graph g,
Node start,
java.lang.String propertyID)
Method performing a Depth-first search on Graph g .
|
void |
dfs(Graph g,
Node start,
java.lang.String propertyID,
Tracer tracer)
Method combining the features of dfs(Graph,Node,Tracer) and
dfs(Graph,Node,String) . |
void |
dfs(Graph g,
Node start,
Tracer tracer)
Method performing a Depth-first search on Graph g .
|
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 |
DFS_STEP
public static final int DFS_STEP
- Trace label constant indicating that the algorithm has made one step forward.
DFS
public DFS()
- Empty (and only) constructor. All algorithm parameters must be given by calling the
appropriate
dfs
-method.
dfs
public void dfs(Graph g,
Node start,
java.lang.String propertyID)
- Method performing a Depth-first search on
Graph
g
.
The search starts at Node
start
and traverses the Graph
by moving forward to the next adjacent
Node
whenever possible. It only moves backwards if there are no further
Nodes
to discover at the actual position.
The results of DFS
are stored as properties of the traversed
Graph
's Nodes
and Edges
, if you give propertyID!=null
as an ID-String
. They can be read out
using 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 |
propertyID.color |
int |
gishur.graph.algorithms.DSF.WHITE |
#WHITE means that this Node has not been discovered by
DSF yet. #BLACK means that this Node has been discovered
and all his neighbours, too have been discovered. #GRAY means that this
Node has been discoverd, but has not been examined for neighbours yet
(only occurs during algorithm execution). |
propertyID.dtime |
int |
Integer.MAX_VALUE |
The discovery time of this Node . The first Node
is discovered at time 1. During algorithm execution, each discovery
of a new Node or the ftime-stamping (see below) of a discovered Node
takes one time unit. |
propertyID.ftime |
int |
Integer.MAX_VALUE |
The finishing time of this Node . This is the time when
all his neighbours have been checked from him and all their neighbours, too,
have thus been discovered and their neighbours etc. (only at this point
DFS returns to him!). |
propertyID.predecessor |
gishur.graph.core.SimpleNode |
null |
The parent Node of this Node in a DFS tree or
null if this Node has not been discovered yet.
In opposite to BFS , DFS may produce several trees,
which form the 'DFS forest', because it starts searching at another
Node when it cannot go further from its previous starting
Node . |
- Parameters:
g
- the Graph
on which to perform the algorithmstart
- the starting Node
for the algorithmpropertyID
- the ID-String
identifying the properties
which are assigned to g
(or its components) as algorithm
results
dfs
public void dfs(Graph g,
Node start,
Tracer tracer)
- Method performing a Depth-first search on
Graph
g
.
The search starts at Node
start
and traverses the Graph
by moving forward to the next adjacent
Node
whenever possible. It only moves backwards if there are no further
Nodes
to discover at the actual position.
This method can be handed a Tracer
to record the algorithm steps. If
one calls dfs with tracer!=null
, it will be possible to replay
the algorithm step by step afterwards to examine its way of work.
- Parameters:
g
- the Graph
on which to perform the algorithmstart
- the starting Node
for the algorithmtracer
- the Tracer
which records the algorithm step by step
dfs
public void dfs(Graph g,
Node start,
java.lang.String propertyID,
Tracer tracer)
- Method combining the features of
dfs(Graph,Node,Tracer)
and
dfs(Graph,Node,String)
. The method will perform a depth-first-search
on g
and write the results as properties to g
with key-prefix propertyID
(see dfs(Graph,Node,String)
).
Besides, if tracer!=null
the algorithm steps will be traced
(see dfs(Graph,Node,Tracer)
).
- 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