aud.example.graph.IterativeDFS2 Class Reference

iterative implementation of DFS Traversal like DepthFirstSearch but as for IterativeDFS1 the order of processed edges differs and nodes are marked before being pushed. More...

Inheritance diagram for aud.example.graph.IterativeDFS2:

Collaboration diagram for aud.example.graph.IterativeDFS2:

Public Member Functions
	IterativeDFS2 (MyGraph g)
String	name ()
	get traversal name More...
void	start (MyNode s0)
	start traversal at node s0 More...
Public Member Functions inherited from aud.example.graph.Traversal
	Traversal (MyGraph g)
	initiate traversal of g More...
abstract String	name ()
	get traversal name More...
abstract void	start (MyNode s0)
	start traversal at node s0 More...
void	showMark (MyNode node)
	callback to give visual feedback on marking a node More...

Additional Inherited Members
Public Attributes inherited from aud.example.graph.Traversal
SingleStepper	singlestepper = null
	may halt if single stepper was set More...
int	nsteps = 1
	halt every nsteps steps in time_ More...
int	verbose = 0
	set verbosity (extra output if >0) More...
Protected Member Functions inherited from aud.example.graph.Traversal
void	initialize ()
	initialize graph for traversal (reset all attributes), provided for convenience to be called by start More...
Protected Attributes inherited from aud.example.graph.Traversal
MyGraph	g_ = null
int	time_ = 0

Detailed Description

iterative implementation of DFS Traversal like DepthFirstSearch but as for IterativeDFS1 the order of processed edges differs and nodes are marked before being pushed.

The latter means that

• a node is never pushed to the stack twice, i.e., the stack size is bounded by the number of nodes, and
• the algorithm stops descending if a node was marked/pushed before, i.e., this is not a true DFS traversal.

Sedgewick (Algorithms, 2nd ed., 1988) gives this algorithm as nonrecursive depth first search but puts some emphasis on the difference to the recursive version.

This version is easily modified to an "optimized" BreadthFirstSearch by exchanging the aud.Stack by a aud.Queue. (Think of what is the difference if you do the same for IterativeDFS1!)

See also

IterativeDFS1

Definition at line 25 of file IterativeDFS2.java.

Constructor & Destructor Documentation

IterativeDFS2()

aud.example.graph.IterativeDFS2.IterativeDFS2

(

MyGraph

g

)

Definition at line 27 of file IterativeDFS2.java.

                                  {
    super(g);
  }

Member Function Documentation

name()

String aud.example.graph.IterativeDFS2.name

(

)

get traversal name

Reimplemented from aud.example.graph.Traversal.

Definition at line 31 of file IterativeDFS2.java.

{ return "iterative DFS (decently cheating)"; }

start()

void aud.example.graph.IterativeDFS2.start

(

MyNode

s0

)

start traversal at node s0

Reimplemented from aud.example.graph.Traversal.

Definition at line 33 of file IterativeDFS2.java.

                                         {
    initialize(); // reset all node attributes
 
    int count=0;
    Stack<MyNode> open=new Stack<MyNode>();
    s0.ord=count++; // marked
    s0.d=0.0;
 
    showMark(s0);
    open.push(s0);
 
    while (!open.is_empty()) {
      if (verbose>0)
        System.out.println("open="+open.toString());
 
      MyNode s=open.pop();
 
      showVisit(s);
 
      for (MyEdge e : g_.getOutEdges(s)) {
 
        if (verbose>1)
          System.err.println(e);
 
        MyNode t=(MyNode) e.destination();
        if (t==s)
            t=(MyNode) e.source(); // undirected graph
 
        if (t.ord<0) { // <=> not marked
          t.ord=count++;
          t.p=s;
          t.d=s.d+(e.hasWeight() ? e.getWeight() : 1.0);
 
          showMark(t);
 
          open.push(t);
        }
      }
    }
  }

References aud.example.graph.MyNode.d, aud.example.graph.Traversal.initialize(), aud.Stack< T >.is_empty(), aud.example.graph.MyNode.ord, aud.Stack< T >.pop(), aud.Stack< T >.push(), aud.example.graph.Traversal.showMark(), aud.adt.AbstractStack< T >.toString(), and aud.example.graph.Traversal.verbose.

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• IterativeDFS2.java