implementation of the A* algorithm More...

Inheritance diagram for aud.example.graph.AStarShortestPath:

Collaboration diagram for aud.example.graph.AStarShortestPath:

Public Member Functions
	AStarShortestPath (MyGraph g, MyNode s1)
	create instance with destination `s1` More...

	AStarShortestPath (MyGraph g)

String	name ()
	get traversal name More...

void	start (MyNode s0)
	find shortest path to destination More...

void	start (MyNode s0, MyNode s1)
	find shortest path from `s0` to `s1` 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
double	h (MyNode node)
	heuristic that guides search 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}: compares f-values (in contrast to {#link DijkstraShortestPath} 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

implementation of the A* algorithm

Definition at line 10 of file AStarShortestPath.java.

Constructor & Destructor Documentation

◆ AStarShortestPath() [1/2]

aud.example.graph.AStarShortestPath.AStarShortestPath	(	MyGraph	g,
		MyNode	s1
	)

create instance with destination s1

Definition at line 27 of file AStarShortestPath.java.

◆ AStarShortestPath() [2/2]

aud.example.graph.AStarShortestPath.AStarShortestPath ( MyGraph g )

Definition at line 32 of file AStarShortestPath.java.

                                      {
    this(g,null);
  }

Member Function Documentation

◆ h()

double aud.example.graph.AStarShortestPath.h ( MyNode node )

protected

heuristic that guides search

Definition at line 37 of file AStarShortestPath.java.

                                  {
    double[] a=s1_.getPosition(), b=node.getPosition();
    double dx=b[0]-a[0], dy=b[1]-a[1];
    return Math.sqrt(dx*dx+dy*dy);
  }

◆ name()

String aud.example.graph.AStarShortestPath.name ( )

get traversal name

Reimplemented from aud.example.graph.Traversal.

Definition at line 43 of file AStarShortestPath.java.

43{ return "A*"; }

◆ start() [1/2]

void aud.example.graph.AStarShortestPath.start ( MyNode s0 )

find shortest path to destination

Reimplemented from aud.example.graph.Traversal.

Definition at line 46 of file AStarShortestPath.java.

                                         {
    if (s1_==null)
      throw new RuntimeException("A* requires destination");
 
    initialize(); // reset all node attributes
 
    int n=g_.getNumNodes();
    int count=0;
    PriorityQueue<MyNode>  open=new PriorityQueue<MyNode>(n,compareNodes);
    HashMap<MyNode,Double> closed=new HashMap<MyNode,Double>(n);
    s0.d=0.0;
    s0.f=h(s0);
 
    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));
      closed.insert(s,s.d);
      showVisit(s);
 
      if (s==s1_) {
        if (verbose>0)
          System.out.println("reached destination '"+s.getLabel()+"'");
 
        ((SimpleDecorator) g_.getDecorator()).unmarkNode(s);
        ((SimpleDecorator) g_.getDecorator()).highlightNode(null);
        ((SimpleDecorator) g_.getDecorator()).highlightEdge(null);
        s.color="red"; // destination
 
        break;
      }
 
      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
 
        if (!closed.contains(t)) {
 
          double dt=s.d+(e.hasWeight() ? e.getWeight() : 1.0);
          double pr=dt+h(t);
 
          boolean push=Double.isInfinite(t.d);
 
          if (dt<t.d) {
            t.ord=count++;
            t.p=s;
            t.d=dt;
            t.f=pr;
 
            showMark(t);
 
            if (push)
              open.push(t);
            else
              open.lower(t);
          }
 
          if (verbose>0)
            System.out.println("open="+open.toString());
        }
      }
    }
 
    // backtracking: output from destination to source
 
    ((SimpleDecorator) g_.getDecorator()).unmarkAllEdges();
    System.out.println("backtracked path: ");
 
    MyNode node=s1_;
 
    while (node!=s0) {
      System.out.print(node.toString()+" ");
      if (node!=s1_) {
        node.color="red";
        ((SimpleDecorator) g_.getDecorator()).unmarkNode(node);
      }
      g_.getEdge(node.p,node).color="red";
      g_.getEdge(node.p,node).penwidth=4.0;
 
      node=node.p;
    }
    node.color="red";
    ((SimpleDecorator) g_.getDecorator()).unmarkNode(node);
    System.out.println(s0);
  }

◆ start() [2/2]

void aud.example.graph.AStarShortestPath.start	(	MyNode	s0,
		MyNode	s1
	)

find shortest path from s0 to s1

Definition at line 145 of file AStarShortestPath.java.

                                         {
    s1_=s1;
    start(s0);
  }

Member Data Documentation

◆ compareNodes

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

protected

Initial value:

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

comparator for {#link aud.PriorityQueue}: compares f-values (in contrast to {#link DijkstraShortestPath}

Definition at line 18 of file AStarShortestPath.java.

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

AStarShortestPath.java

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members