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
 

Field Detail

DFS_STEP

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

DFS

public DFS()
Empty (and only) constructor. All algorithm parameters must be given by calling the appropriate dfs-method.
Method Detail

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 algorithm
start - the starting Node for the algorithm
propertyID - 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 algorithm
start - the starting Node for the algorithm
tracer - 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 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