aud.example.graph.IterativeDFS1 Class Reference

Iterative implementation of DFS. More...

Inheritance diagram for aud.example.graph.IterativeDFS1:

Collaboration diagram for aud.example.graph.IterativeDFS1:

Public Member Functions
	IterativeDFS1 (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 order of processed edges differs. We use a second stack to keep track of the parent node in the spanning tree. (This could be solved differently. Note, however, that we have to transfer the "complete state" near push.)

In contrast to IterativeDFS2, nodes are marked only when they are popped off the stack. This simulates the recursive DepthFirstSearch best, but allows to the stack size to grow beyond the number of nodes!

See also

IterativeDFS2

Definition at line 17 of file IterativeDFS1.java.

Constructor & Destructor Documentation

IterativeDFS1()

aud.example.graph.IterativeDFS1.IterativeDFS1

(

MyGraph

g

)

Definition at line 19 of file IterativeDFS1.java.

                                  {
    super(g);
  }

Member Function Documentation

name()

String aud.example.graph.IterativeDFS1.name

(

)

get traversal name

Reimplemented from aud.example.graph.Traversal.

Definition at line 23 of file IterativeDFS1.java.

{ return "iterative DFS (close to DFS)"; };

start()

void aud.example.graph.IterativeDFS1.start

(

MyNode

s0

)

start traversal at node s0

Reimplemented from aud.example.graph.Traversal.

Definition at line 25 of file IterativeDFS1.java.

                                         {
    initialize(); // reset all node attributes
 
    int count=0;
    Stack<MyNode>  open=new Stack<MyNode>();
    Stack<MyNode>  parent=new Stack<MyNode>();
 
    s0.d=0.0;
    open.push(s0);
    parent.push(null);
 
    while (!open.is_empty()) {
      if (verbose>0)
        System.out.println("open="+open.toString());
 
      MyNode s=open.pop();
      MyNode p=parent.pop();
 
      if (s.ord<0) {
        s.ord=count++; // marked
        s.p=p;
 
        if (p!=null) {
          MyEdge e=g_.getEdge(p,s);
          s.d=p.d+(e.hasWeight() ? e.getWeight() : 1.0);
        }
 
        showMark(s);
        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
          open.push(t);
          parent.push(s);
        }
      }
    }
  }

References aud.example.graph.MyNode.d, aud.example.graph.Traversal.g_, aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.getEdge(), aud.graph.SimpleEdge.getWeight(), aud.graph.AbstractEdge.hasWeight(), aud.example.graph.Traversal.initialize(), aud.Stack< T >.is_empty(), aud.example.graph.MyNode.ord, aud.example.graph.MyNode.p, 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:

• IterativeDFS1.java