Hi everyone, I'm implementing Dijkstra's algorithm for a class
project, and I'm having trouble compiling the class that runs the
algorithm. All of the other files compile fine except for this one.
I am using the compiler like this:
javac -classpath .. <filename.java>
The source code of the classes follow. Dijkstra.java is the class
that won't compile, because the compiler doesn't recgonise the Vertex
and GraphMap classes, even though the other files compile. What could
the problem be? Thanks!
----------------------------------------------------
package graphADT;
import java.io.*;
import java.util.*;
public abstract class Vertex
{
// ID number
protected int m_iID;
// Returns number
public int getID()
{
return this.m_iID;
}
// Comparison functions
// Two vertices are equal if they are the same object or the ID is
the same
public boolean equals(Object o)
{
return this == o || equals((Vertex)o);
}
public boolean equals(Vertex v)
{
return this.m_iID == v.m_iID;
}
public int compareTo(Object o)
{
return compareTo((Vertex)o);
}
public int compareTo(Vertex v)
{
return this.m_iID = v.m_iID;
}
}
--------------------------------------------------------
package graphADT;
import java.io.*;
import java.util.*;
public abstract class Edge
{
// ArrayList of vertices on this edge
private ArrayList m_alVertex = new ArrayList();
// Distance
private int m_iDistance = 0;
// Add a new vertex to this edge
public void addEdge(Edge e,int distance)
{
if (!m_alVertex.isEmpty())
{
this.m_iDistance += distance;
}
m_alVertex.add(e);
}
// Return the total distance of this edge
public int getDistance()
{
return m_iDistance;
}
// Return the total number of vertices on this edge. Starting one is
not counted
public int getVertices()
{
return (m_alVertex.isEmpty()) ? 0 : m_alVertex.size() - 1;
}
// Gets the last stop on this edge
public Vertex getLastVertex()
{
if (m_alVertex.isEmpty())
{
return null;
}
else
{
return (Vertex)m_alVertex.get(m_alVertex.size() - 1);
}
}
// Returns whether or not the given Vertex is in this edge
public boolean hasVertex(Vertex v)
{
return m_alVertex.contains(v);
}
}
---------------------------------------------------------------
package graphADT;
import java.util.*;
public abstract class GraphMap
{
// The two dimensional array that represents the graph
private final int[][] edges;
GraphMap(int Num)
{
edges = new int[Num][Num];
}
// Link two vertices with a direct edge with given distance
public void addDirectEdge(Vertex start,Vertex end,int distance)
{
edges[start.getID()][end.getID()] = distance;
}
// return the distance between two vertices, or 0 if no path
public int getDistance(Vertex start,Vertex end)
{
return edges[start.getID()][end.getID()];
}
// Return all destinations from a given vertex
public abstract List getDestinations(Vertex v);
// Return all vertices leading to a given vertex
public abstract List getPredecessors(Vertex v);
// Return the transposed graph of this graph
// We're returning a two dimensional array because this is an
abstract class
public int[][] getInverse()
{
int[][] inverse = new int[edges.length][edges.length];
for (int i = 0;i < edges.length;i++)
{
for (int j = 0;j < edges.length;j++)
{
inverse[i][j] = edges[j][i];
}
}
return inverse;
}
}
-----------------------------------------------------------------------
package groupADT;
import java.util.*;
public abstract class Dijkstra
{
public static final int MAX_DISTANCE = Integer.MAX_VALUE;
private final Comparator shortestDistanceComparator = new
Comparator()
{
public int compare(Object left,Object right) throws
IllegalArgumentException
{
if (!(left instanceof Vertex) || !(right instanceof Vertex))
{
throw IllegalArgumentException;
}
return compare((Vertex)left,(Vertex)right);
}
private int compare(Vertex left,Vertex right)
{
// This trick doesn't work for huge distances, approaching
Integer.MAX_VALUE
int result = getShortestDistance(left) -
getShortestDistance(right);
return (result == 0) ? left.compareTo(right) : result;
}
};
// The graph
private final GraphMap graph;
// The working set of vertices
private final SortedSet unsettledNodes = new
TreeSet(shortestDistanceComparator);
// Set of vertices for which the shortest distance from the starting
point has been found
private final Set settledNodes = new HashSet();
// The currently known shortest distance to all vertices
private final Map shortestDistances = new HashMap();
// Maps a vertex to it's predecessor in a spanning tree of shortest
paths
private final Map predecessors = new HashMap();
// Constructor
public Dijkstra(GraphMap graph)
{
this.graph = graph;
}
// Get the vertex with the shortest distance, and remove it from the
priority queue
private Vertex extractMin()
{
if (unsettledNodes.isEmpty())
{
return null;
}
Vertex min = (Vertex)unsettledNodes.first();
unsettledNodes.remove(min);
return min;
}
// Compute shortest distance for neighbouring nodes and update if
better distance
private void relaxNeighbours(Vertex u)
{
for (Iterator i = graph.getDestinations(u).iterator();i.hasNext();)
{
Vertex v = (Vertex)i.next();
// skip node already settled
if (isSettled(v))
{
continue;
}
if (getShortestDistance(v) > getShortestDistance(u) +
graph.getDistance(u,v))
{
// assign new shortest distance and mark unsettled
setShortestDistance(v,getShortestDistance(u) +
graph.getDistance(u,v));
// assign predecessor in shortest path
setPredecessor(v,u);
}
}
}
// Mark a vertex as settled
private void markSettled(Vertex v)
{
settledNodes.add(v);
}
// Return whether a vertex has a shortest distance
private boolean isSettled(Vertex v)
{
return settledNodes.contains(v);
}
// Return the shortest distance from a source to the given vertex or
max int
public int getShortestDistance(Vertex v)
{
Integer d = (Integer)shortestDistances.get(v);
return (d == null) ? MAX_DISTANCE : d.intValue();
}
// Set the new shortest distance, and rebalance
private void setShortestDistances(Vertex v,int distance)
{
// ensure no duplicates
unsettledNodes.remove(v);
shortestDistances.put(v,new Integer(distance));
// Rebalance the set with the shortest distances found
unsettledNodes.add(v);
}
// Return the city leading to the city on the shortest path
public Vertex getPredecessor(Vertex v)
{
return (Vertex)predecessors.get(v);
}
private void setPredecessor(Vertex a,Vertex b)
{
predecessors.put(a,b);
}
// Initalise all data structures
private void init(Vertex start)
{
settledNodes.clear();
unsettledNodes.clear();
shortestDistances.clear();
predecessors.clear();
// add starting vertex
setShortestDistance(start,0);
unsettlednodes.add(start);
}
// Run Dijkstra's algorithm
public void execute(Vertex start,Vertex end)
{
init(start);
Vertex current;
while ((current = extractMin()) != null)
{
if (!isSettled(current))
{
break;
}
// destination reached, stop
if (current == end)
{
break;
}
markSettled(current);
relaxNeighbours(current);
}
}
}
