Strong Sauce fucked around with this message at 09:40 on Nov 30, 2008

rjmccall fucked around with this message at 23:03 on Nov 30, 2008

KyPeN fucked around with this message at 01:16 on Dec 1, 2008

public int compareTo(Node right)
{
	if (this.getTotal() > right.getTotal())   //getTotal() returns a double
		return -1;
	if (this.getTotal() < right.getTotal())
		return 1;
	return 0;
}

Clanpot Shake fucked around with this message at 03:43 on Dec 1, 2008

PriorityQueue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>()
{
    public int compare(Node n1, Node n2)
    {
        return n2.getTotal() - n1.getTotal();
    }
});

Outlaw Programmer fucked around with this message at 07:58 on Dec 1, 2008

Rocko Bonaparte fucked around with this message at 19:30 on Dec 2, 2008

package homework;

import java.util.*;

public class Node implements Comparable<Node>
{
	public HashMap<Node, Double> neighbors;
	public Node previous;
	public String name;
	public DPoint location;
	// cost = actual distance from start to this in a straight line
	// heuristic = distance from this to goal in a straight line
	double cost, heuristic, total;
	
	public Node(String n)
	{
		name = n;
		location = new DPoint();
		neighbors = new HashMap<Node, Double>();
	}
	public Node(Node n)
	{
		name = n.getName();
		location = n.getLocation();
		neighbors = new HashMap<Node, Double>(n.getNeighbors());
	}
	public Node(String n, double x, double y)
	{
		name = n;
		location = new DPoint(x,y);
		neighbors = new HashMap<Node, Double>();
	}
	public Node(String n, DPoint a)
	{
		name = n;
		location = a;
		neighbors = new HashMap<Node, Double>();
	}
	public void addNeighbor(Node n, double distance)
	{
		neighbors.put(n, distance);
	}
	public void setNeighbors(HashMap<Node, Double> n)	{	neighbors = n;	}
	public String getName() 				{ 	return name;		}
	public HashMap<Node, Double> getNeighbors()		{	return neighbors;	}
	public DPoint getLocation()				{	return location;	}
	public double getCost()					{ 	return cost;		}
	public double getHeuristic()				{	return heuristic;	}
	public void setPrevious(Node n)				{	previous = n;		}
	public Node getPrevious()				{	return previous;	}
	public double getTotal()							
	{
		total = cost + heuristic;
		return total;			
	}
	
	public void setCost(double c)			{	cost = c;	}
	public void setCost(String c)			
	{		
		for (Node n : neighbors.keySet())
			if (n.name == c)
				cost = neighbors.get(n);
	}
	public void addCost(double c) 			{ 	cost += c;			}
	public void setHeuristic(double h)		{	heuristic = h;			}
	public void setTotal(double t)			{	total = t;			}
	
	public void calcCost(Node start)
	{	cost = location.distance(start.getLocation());		}	
	public void calcHeuristic(Node goal)
	{	heuristic = location.distance(goal.getLocation());	}	
	
	public String toString()
	{
		String s = "";
		for (Node n : neighbors.keySet())
			if (n != null)
				s = s + n.getName() + " ";
		return name;// + " at ("+location.getX()+","+location.getY()+") is connected to " + s;
	}
	public String verbose()
	{
		String s = "";
		for (Node n : neighbors.keySet())
			if (n != null)
				s = s + n.getName() + "("+ neighbors.get(n).doubleValue()+") ";
		return name + " at ("+location.getX()+","+location.getY()+") is connected to " + s;
	}
	
	public boolean equals(Object right)
	{
		if (this.name == ((Node)right).name)
			return true;
		if (!(right instanceof Node))
			return false;
		return (this.getLocation().equals(((Node)right).getLocation()));
	}
	
	public int compareTo(Node right)
	{
		if (this.getTotal() > right.getTotal())
			return -1;
		if (this.getTotal() < right.getTotal())
			return 1;
		return 0;
	}
	public static double distanceBetween(Node x, Node y)
	{
		double Lat1, Lat2, Long1, Long2;
		Lat1 = x.getLocation().getX();
		Lat2 = y.getLocation().getX();
		Long1 = x.getLocation().getY();
		Long2 = y.getLocation().getY();
		return 3963.0 * (2 * Math.asin(
				Math.sqrt(Math.pow(Math.sin(
						Math.toRadians((Lat2-Lat1)/2)),2) + 
						Math.cos(Math.toRadians(Lat1)) *
						Math.cos(Math.toRadians(Lat2)) *
						Math.pow(Math.sin(Math.toRadians((Long2-Long1)/2)), 2))));				
	}
}

PriorityQueue<Node> open = new PriorityQueue<Node>(10,new Comparator<Node>() 
{ 
// orders the nodes in ascending order by total score
	public int compare(Node n1, Node n2) 
	{ 
		int aVal = (int)((n1.getCost() + n1.getHeuristic()) * 100000);
		int bVal = (int)((n2.getCost() + n2.getHeuristic()) * 100000);

                    if (bVal > aVal)
                            return -1;
                    else if (bVal < aVal)
                            return 1;
                    else
                            return 0;
	} 
});		
PriorityQueue<Node> closed = new PriorityQueue<Node>(/*same as above*/);	
ArrayList<Node> path = new ArrayList<Node>();
		
start.setCost(0);		
open.add(start);		
		
double tentscore;				// the cost of the path currently being explored
boolean tent_is_better;			// true means the path we're looking at is better
while (!open.isEmpty())
{
	//Arrays.sort(open.toArray());
	//current = open.remove();	
			
	current = open.poll();
	if (current.equals(goal))		//PATH COMPLETE, reconstruct the path
	{
		System.out.print("On node " + current.getName()+"\n");
		path = reconstructPath(current);
		break;
	}
	else
	{
		System.out.print("On node " + current.getName()+", exploring neighbors...\n");
		closed.add(current);
		for (Node n : current.getNeighbors().keySet())
		{
			System.out.print("\tExploring node " + n.getName()+"...");
			if (closed.contains(n))
			{	
				System.out.print(" Already explored, moving on.\n");
				continue;
			}
			tentscore = current.getCost() + Node.distanceBetween(n, current);
			tent_is_better = false;
			if (!open.contains(n))
			{
				System.out.print(" Adding "+n.getName()+" to the open set, ");
				[b]//open.offer(n);[/b]
				n.setHeuristic(Node.distanceBetween(n, goal));
				tent_is_better = true;
			}
			else if (tentscore < n.getCost())
				tent_is_better = true;
			if (tent_is_better)
			{
				//System.out.print("Adding " + n.getName() + " to the path \n");
				n.setPrevious(current);
				n.setCost(current.name);
				n.addCost(current.getCost());
				n.setTotal(n.getCost() + n.getHeuristic());
				//[b]open.offer(n);[/b]  // UNCOMMENT THIS
				System.out.printf("\n\t\tCost of node: %.2f miles\n\t\tHeuristic Value:
			 %.2f miles\n\t\tEstimated Total Cost of node: %.2f miles\n",
			tentscore,n.getHeuristic(),n.getTotal());
			}
			System.out.print("\tFinished with node " + n.getName()+"\n");
		}
		System.out.print("Finished with node " + current.getName()+"\n");
	}
}	// END WHILE
reportFindings(path);

Clanpot Shake fucked around with this message at 20:30 on Dec 2, 2008

• The way you use setCost(String) during neighbor-update is ridiculous: you already have a handle on the source node (current), you've even set it as previous on the node, but in order to derive the cost to the source node you... linearly search the target node's in-edges for a node with that name?
  
• Why is closed a priority queue? The only operation you perform on it is membership testing; a set would be much faster, but in this case you could get away with a flag on the node.
  
• Queues where you frequently modify the priority of elements already in the queue aren't really ideal for over-the-counter data structures. It'd be much more efficient to use an invasive heap, especially since you know that priorities only ever drop.
  
• With a lot of distance-based algorithms, it's better to work with squared distances; that might be problematic here, because of course you can't add them correctly. But it would eliminate a lot of possibly unnecessary square-roots.