aud.example.graph.PriorityFirstSearch Class Reference

Priority first search implementation. More...

Inheritance diagram for aud.example.graph.PriorityFirstSearch:

Collaboration diagram for aud.example.graph.PriorityFirstSearch:

Public Member Functions
	PriorityFirstSearch (MyGraph g)
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...

Protected Member Functions
abstract double	priority (MyNode node, MyEdge e)
	Compute priority of a node: 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
Comparator< MyNode >	compareNodes
	comparator for {#link aud.PriorityQueue} More...
Protected Attributes inherited from aud.example.graph.Traversal
MyGraph	g_ = null
int	time_ = 0

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...

Detailed Description

Priority first search implementation.

The priority function must be implemented (e.g., Dijkstra, Prim}.

Definition at line 9 of file PriorityFirstSearch.java.

Constructor & Destructor Documentation

PriorityFirstSearch()

aud.example.graph.PriorityFirstSearch.PriorityFirstSearch

(

MyGraph

g

)

Definition at line 20 of file PriorityFirstSearch.java.

                                        {
    super(g);
  }

Member Function Documentation

priority()

abstract double aud.example.graph.PriorityFirstSearch.priority ( MyNode  node, MyEdge  e  )

abstractprotected

Compute priority of a node:

• node.d+e.getWeight() for Dijkstra's algorithm to find shortest paths (and the shortest path tree)
• e.getWeight() for Prim's algorithm to find the minimum spanning tree

Reimplemented in aud.example.graph.DijkstraShortestPaths, and aud.example.graph.PrimMinimumSpanningTree.

start()

void aud.example.graph.PriorityFirstSearch.start

(

MyNode

s0

)

start traversal at node s0

Reimplemented from aud.example.graph.Traversal.

Definition at line 34 of file PriorityFirstSearch.java.

                                         {
    initialize(); // reset all node attributes
 
    int count=0;
    PriorityQueue<MyNode> open=
      new PriorityQueue<MyNode>(g_.getNumNodes(),compareNodes);
    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();
 
      assert(!Double.isInfinite(s.d));
      showVisit(s);
 
      for (MyEdge e : g_.getOutEdges(s)) {
 
        if (verbose>0)
          System.err.println(e);
 
        MyNode t=(MyNode) e.destination();
        if (t==s)
            t=(MyNode) e.source();          // undirected graph
 
        double pr=priority(s,e);
 
        if (Double.isInfinite(t.d)) {
 
          assert(!open.contains(t));
 
          t.ord=count++;
          t.p=s;
          t.d=pr;
 
          showMark(t);
 
          open.push(t);
        }
        else if (t.d>pr && open.contains(t)) {   // update distance/priority
 
          if (verbose>0)
            System.out.println("update "+t+": priority "+t.d+" -> "+pr+
                 ", parent "+t.p+" -> "+s);
 
          t.p=s;
          t.d=pr;
 
          open.lower(t);
 
          if (verbose>0)
            System.out.println("open="+open.toString());
        }
      }
    }
  }

References aud.example.graph.PriorityFirstSearch.compareNodes, aud.example.graph.MyNode.d, aud.example.graph.Traversal.g_, aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.getNumNodes(), aud.example.graph.Traversal.initialize(), aud.PriorityQueue< T >.is_empty(), aud.PriorityQueue< T >.pop(), aud.PriorityQueue< T >.push(), aud.example.graph.Traversal.showMark(), aud.PriorityQueue< T >.toString(), and aud.example.graph.Traversal.verbose.

Here is the call graph for this function:

Member Data Documentation

compareNodes

Comparator<MyNode> aud.example.graph.PriorityFirstSearch.compareNodes

protected

Initial value:

=
    new Comparator<MyNode>() {
    @Override public int compare(MyNode a,MyNode b) {
      double d=a.d-b.d ;
      return (d<0.0) ? -1 : (d>0.0 ? +1 : 0);
    }
  }

comparator for {#link aud.PriorityQueue}

Definition at line 12 of file PriorityFirstSearch.java.

Referenced by aud.example.graph.PriorityFirstSearch.start().

---

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

• PriorityFirstSearch.java