SandMark version 2.0


sandmark.util.graph
Class Dfs

java.lang.Object
  |
  +--sandmark.util.graph.Dfs
All Implemented Interfaces:
java.lang.Cloneable

public class Dfs
extends java.lang.Object
implements java.lang.Cloneable

Performs a depth-first-search on a sandmark.util.graph.Graph, classifying edges as TREE, BACK, CROSS, or FORWARD.


Field Summary
(package private) static int BLACK
           
(package private)  PriorityQueue finish
           
(package private)  Graph g
           
(package private) static int GRAY
           
(package private)  PriorityQueue start
           
(package private)  int time
           
(package private) static int WHITE
           
 
Constructor Summary
Dfs(Graph g)
           
Dfs(Graph g, Node root)
          Prepare to perform a depth-first-search on a graph.
Dfs(Graph g, PriorityQueue start, PriorityQueue finish)
           
 
Method Summary
 java.lang.Object clone()
           
 Dfs copy()
          Return a copy of the Dfs object.
static void main(java.lang.String[] args)
           
 void pass1()
          Perform the depth-first-search.
 void pass2()
           
 void process()
           
 void process(Node root)
           
 java.util.Iterator reverseTopOrder()
          Generate one node from the graph at a time, in a reverse topological order.
 java.util.Iterator topOrder()
          Generate one node from the graph at a time, in a topological order.
 java.lang.String toString()
          Print out the nodesof the graph in a topological order.
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

WHITE

static final int WHITE
See Also:
Constant Field Values

GRAY

static final int GRAY
See Also:
Constant Field Values

BLACK

static final int BLACK
See Also:
Constant Field Values

start

PriorityQueue start

finish

PriorityQueue finish

time

int time

g

Graph g
Constructor Detail

Dfs

public Dfs(Graph g,
           Node root)
Prepare to perform a depth-first-search on a graph.


Dfs

public Dfs(Graph g)

Dfs

public Dfs(Graph g,
           PriorityQueue start,
           PriorityQueue finish)
Method Detail

clone

public java.lang.Object clone()
                       throws java.lang.CloneNotSupportedException
Overrides:
clone in class java.lang.Object
java.lang.CloneNotSupportedException

copy

public Dfs copy()
Return a copy of the Dfs object.


pass1

public void pass1()
Perform the depth-first-search.


pass2

public void pass2()

process

public void process()

process

public void process(Node root)

topOrder

public java.util.Iterator topOrder()
Generate one node from the graph at a time, in a topological order.


reverseTopOrder

public java.util.Iterator reverseTopOrder()
Generate one node from the graph at a time, in a reverse topological order.


toString

public java.lang.String toString()
Print out the nodesof the graph in a topological order.

Overrides:
toString in class java.lang.Object

main

public static void main(java.lang.String[] args)

SandMark version 2.0

Mon Jun 17 12:30:47 MST 2002