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.jav a>
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(Objec t o)
{
return compareTo((Vert ex)o);
}
public int compareTo(Verte x 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.is Empty())
{
this.m_iDistanc e += 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.isE mpty()) ? 0 : m_alVertex.size () - 1;
}
// Gets the last stop on this edge
public Vertex getLastVertex()
{
if (m_alVertex.isE mpty())
{
return null;
}
else
{
return (Vertex)m_alVer tex.get(m_alVer tex.size() - 1);
}
}
// Returns whether or not the given Vertex is in this edge
public boolean hasVertex(Verte x v)
{
return m_alVertex.cont ains(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(V ertex 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(Ver tex 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_VAL UE;
private final Comparator shortestDistanc eComparator = new
Comparator()
{
public int compare(Object left,Object right) throws
IllegalArgument Exception
{
if (!(left instanceof Vertex) || !(right instanceof Vertex))
{
throw IllegalArgument Exception;
}
return compare((Vertex )left,(Vertex)r ight);
}
private int compare(Vertex left,Vertex right)
{
// This trick doesn't work for huge distances, approaching
Integer.MAX_VAL UE
int result = getShortestDist ance(left) -
getShortestDist ance(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(shortes tDistanceCompar ator);
// 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 shortestDistanc es = 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(GraphM ap 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)unsettl edNodes.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.getDestin ations(u).itera tor();i.hasNext ();)
{
Vertex v = (Vertex)i.next( );
// skip node already settled
if (isSettled(v))
{
continue;
}
if (getShortestDis tance(v) > getShortestDist ance(u) +
graph.getDistan ce(u,v))
{
// assign new shortest distance and mark unsettled
setShortestDist ance(v,getShort estDistance(u) +
graph.getDistan ce(u,v));
// assign predecessor in shortest path
setPredecessor( v,u);
}
}
}
// Mark a vertex as settled
private void markSettled(Ver tex v)
{
settledNodes.ad d(v);
}
// Return whether a vertex has a shortest distance
private boolean isSettled(Verte x v)
{
return settledNodes.co ntains(v);
}
// Return the shortest distance from a source to the given vertex or
max int
public int getShortestDist ance(Vertex v)
{
Integer d = (Integer)shorte stDistances.get (v);
return (d == null) ? MAX_DISTANCE : d.intValue();
}
// Set the new shortest distance, and rebalance
private void setShortestDist ances(Vertex v,int distance)
{
// ensure no duplicates
unsettledNodes. remove(v);
shortestDistanc es.put(v,new Integer(distanc e));
// 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)predece ssors.get(v);
}
private void setPredecessor( Vertex a,Vertex b)
{
predecessors.pu t(a,b);
}
// Initalise all data structures
private void init(Vertex start)
{
settledNodes.cl ear();
unsettledNodes. clear();
shortestDistanc es.clear();
predecessors.cl ear();
// add starting vertex
setShortestDist ance(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(cur rent))
{
break;
}
// destination reached, stop
if (current == end)
{
break;
}
markSettled(cur rent);
relaxNeighbours (current);
}
}
}
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.jav a>
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(Objec t o)
{
return compareTo((Vert ex)o);
}
public int compareTo(Verte x 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.is Empty())
{
this.m_iDistanc e += 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.isE mpty()) ? 0 : m_alVertex.size () - 1;
}
// Gets the last stop on this edge
public Vertex getLastVertex()
{
if (m_alVertex.isE mpty())
{
return null;
}
else
{
return (Vertex)m_alVer tex.get(m_alVer tex.size() - 1);
}
}
// Returns whether or not the given Vertex is in this edge
public boolean hasVertex(Verte x v)
{
return m_alVertex.cont ains(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(V ertex 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(Ver tex 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_VAL UE;
private final Comparator shortestDistanc eComparator = new
Comparator()
{
public int compare(Object left,Object right) throws
IllegalArgument Exception
{
if (!(left instanceof Vertex) || !(right instanceof Vertex))
{
throw IllegalArgument Exception;
}
return compare((Vertex )left,(Vertex)r ight);
}
private int compare(Vertex left,Vertex right)
{
// This trick doesn't work for huge distances, approaching
Integer.MAX_VAL UE
int result = getShortestDist ance(left) -
getShortestDist ance(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(shortes tDistanceCompar ator);
// 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 shortestDistanc es = 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(GraphM ap 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)unsettl edNodes.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.getDestin ations(u).itera tor();i.hasNext ();)
{
Vertex v = (Vertex)i.next( );
// skip node already settled
if (isSettled(v))
{
continue;
}
if (getShortestDis tance(v) > getShortestDist ance(u) +
graph.getDistan ce(u,v))
{
// assign new shortest distance and mark unsettled
setShortestDist ance(v,getShort estDistance(u) +
graph.getDistan ce(u,v));
// assign predecessor in shortest path
setPredecessor( v,u);
}
}
}
// Mark a vertex as settled
private void markSettled(Ver tex v)
{
settledNodes.ad d(v);
}
// Return whether a vertex has a shortest distance
private boolean isSettled(Verte x v)
{
return settledNodes.co ntains(v);
}
// Return the shortest distance from a source to the given vertex or
max int
public int getShortestDist ance(Vertex v)
{
Integer d = (Integer)shorte stDistances.get (v);
return (d == null) ? MAX_DISTANCE : d.intValue();
}
// Set the new shortest distance, and rebalance
private void setShortestDist ances(Vertex v,int distance)
{
// ensure no duplicates
unsettledNodes. remove(v);
shortestDistanc es.put(v,new Integer(distanc e));
// 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)predece ssors.get(v);
}
private void setPredecessor( Vertex a,Vertex b)
{
predecessors.pu t(a,b);
}
// Initalise all data structures
private void init(Vertex start)
{
settledNodes.cl ear();
unsettledNodes. clear();
shortestDistanc es.clear();
predecessors.cl ear();
// add starting vertex
setShortestDist ance(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(cur rent))
{
break;
}
// destination reached, stop
if (current == end)
{
break;
}
markSettled(cur rent);
relaxNeighbours (current);
}
}
}
Comment