Question
How do I complete my Prim-Jarnik code? I write a code the solution my assignment and is giving me errors and i cannot understand why.
How do I complete my Prim-Jarnik code?
I write a code the solution my assignment and is giving me errors and i cannot understand why.
import java.util.*;
public class Graph {
public static final double INFINITY = Double.MAX_VALUE;
public void addEdge( String sourceName, String destName, double cost ) {
Vertex v = getVertex(sourceName);
Vertex w = getVertex(destName);
v.adj.add(new Edge(w, cost));
}
public void printPath( String destName ) {
Vertex w = vertexMap.get(destName);
if (w == null)
throw new NoSuchElementException();
else if (w.dist == INFINITY)
System.out.println(destName + " is unreachable");
else {
System.out.print("(Cost is: " + w.dist + ") ");
printPath(w);
System.out.println();
}
}
private Vertex getVertex( String vertexName ) {
Vertex v = vertexMap.get(vertexName);
if (v == null) {
v = new Vertex(vertexName);
vertexMap.put(vertexName, v);
}
return v;
}
public void printPath( Vertex dest ) {
if (dest.prev != null){
printPath(dest.prev);
System.out.print(" to ");
}
System.out.print(dest.name);
}
public void printGraph(){
for (Vertex v : vertexMap.values()){
System.out.print(" Vertex "+v.name+" connects to: ");
for (Edge e : v.adj)
System.out.print(e.dest.name+" ");
}
}
public void clearAll( ) {
for (Vertex v : vertexMap.values())
v.reset();
}
public Graph prim(){
// TODO: Implement the Prim-Jarnik algorithm, instructions below
/*
* INSTRUCTIONS
*
* Complete the Prim-Jarnik algorithm implementation here!
*
* Use each Vertex object's dist field to store cheapCost
* and its prev field to store cheapEdge.
*
* We're using an Array List as a pseudo-priority queue, due to
* unfortunate ways that the built-in Java PriorityQueue class behaves.
* This makes our implementation somewhat slower than the theoretical maximum.
*
* In order to make this work as a PQ, we need to resort the set
* every time we make a change to one of its members. You can do this
* with this command: Collections.sort(set). I've set up the Vertex class
* so that its natural ordering uses the dist field.
*
* Be sure to resort the set after you make one or more changes to one of its members!
* (When does this happen in the Prim-Jarnik algorithm?) Also, when removing a Vertex
* from the set, use the remove(index) ArrayList method. (To act like a PQ, which
* index should you always remove from?)
*
* You only ever need to add Edges to your answer Graph, with the addEdge method,
* since that method creates Vertex objects it doesn't already find in the Graph.
* When you add an Edge, be sure to add it both ways, since our implementation uses
* a local adjacency list in each Vertex object. (That is, add A-->B as well as B-->A,
* with the same cost.)
*
* Finally, be sure that you're only adding edges to your answer Graph, NOT the original!
*/
// Set up the PQ as an ArrayList, load references to original Graph vertices
ArrayList set = new ArrayList();
for (Vertex v : vertexMap.values())
set.add(v);
Collections.sort(set);
Graph ans = new Graph();
// This is the core loop of Prim-Jarnik.
// What should be the conditional governing the while loop?
while (set.size() > 0){
Vertex v = set.get(0);
set.remove(0);
for (Edge e : v.adj){
Vertex w = e.dest;
if (w.dist > e.cost){
w.dist = e.cost;
w.prev = v;
Collections.sort(set);
}
}
ans.addEdge(v.name, v.prev.name, v.dist);
}
return ans;
} // end prim
// Implements BFS
public void unweighted( String startName ) {
clearAll();
Vertex start = vertexMap.get(startName);
if (start == null)
throw new NoSuchElementException("Start vertex not found");
Queue q = new LinkedList();
q.add(start); start.dist = 0;
while (!q.isEmpty()) {
Vertex v = q.remove();
for (Edge e: v.adj) {
Vertex w = e.dest;
if (w.dist == INFINITY) {
w.dist = v.dist+1;
w.prev = v;
q.add(w);
}
}
}
}
public void dijkstra( String startName ) {
PriorityQueue pq = new PriorityQueue();
Vertex start = vertexMap.get(startName);
if (start == null)
throw new NoSuchElementException("Start vertex not found.");
clearAll();
pq.add(new Path(start, 0)); start.dist = 0;
int nodesSeen = 0;
// While the PQ isn't empty and we haven't visited all nodes
while (!pq.isEmpty() && nodesSeen < vertexMap.size()) {
Path vrec = pq.remove();
Vertex v = vrec.dest;
if (v.visited != 0) // already processed this node
continue;
v.visited = 1;
nodesSeen++;
for (Edge e : v.adj) {
Vertex w = e.dest; // reference to one adjacent node
double cvw = e.cost; // cost for traveling V-->W
if (cvw < 0)
throw new GraphException("Graph has negative edges");
if (w.dist > v.dist + cvw) {
w.dist = v.dist + cvw;
w.prev = v;
pq.add(new Path(w, w.dist));
}
}
}
}
public void negative( String startName ) {
clearAll();
Vertex start = vertexMap.get(startName);
if (start == null)
throw new NoSuchElementException("Start vertex not found");
Queue q = new LinkedList();
q.add(start); start.dist = 0; start.visited++;
while (!q.isEmpty()) {
Vertex v = q.remove();
if (v.visited++ > 2 * vertexMap.size())
throw new GraphException("Negative cycle detected.");
for (Edge e : v.adj) {
Vertex w = e.dest;
double cvw = e.cost;
if (w.dist > v.dist + cvw){
w.dist = v.dist + cvw;
w.prev = v;
if (w.visited++ % 2 == 0)
q.add(w);
else
w.visited--;
}
}
}
} // end negative
public void acyclic( String startName ) {
Vertex start = vertexMap.get(startName);
if (start == null)
throw new NoSuchElementException("Start vertex not found.");
clearAll();
Queue q = new LinkedList();
start.dist = 0;
Collection vertexSet = vertexMap.values();
for (Vertex v : vertexSet)
for (Edge e : v.adj)
e.dest.visited++;
for (Vertex v : vertexSet)
if (v.visited == 0)
q.add(v);
int iterations;
for (iterations = 0; !q.isEmpty(); iterations++){
Vertex v = q.remove();
for (Edge e : v.adj) {
Vertex w = e.dest;
double cvw = e.cost;
if (--w.visited == 0)
q.add(w);
if (v.dist == INFINITY)
continue;
if (w.dist > v.dist + cvw) {
w.dist = v.dist + cvw;
w.prev = v;
}
}
}
if (iterations != vertexMap.size())
throw new GraphException("Graph has a cycle!");
} // end acyclic
private Map vertexMap = new HashMap( );
}// end Graph
// Used to signal violations of preconditions for
// various shortest path algorithms.
class GraphException extends RuntimeException {
public GraphException( String name )
{ super( name ); }
}// end GraphException
class Edge {
public Vertex dest;
public double cost;
public Edge(Vertex d, double c){
dest = d;
cost = c;
} // end constructor
} // end class Edge
import java.io.FileReader;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.util.Scanner;
import java.util.StringTokenizer;
/**
* A main routine that:
* 1. Reads a file (supplied as a command-line parameter)
* containing edges.
* 2. Forms the graph;
* 3. Repeatedly prompts for two vertices and
* runs the shortest path algorithm.
* The data file is a sequence of lines of the format
* source destination cost
*/
public class GraphAlgorithms {
public static void main(String[] args ) {
Graph g = new Graph();
try {
FileReader fin = new FileReader( args[0] );
Scanner graphFile = new Scanner(fin);
// Read the edges and insert
String line;
while( graphFile.hasNextLine( ) ) {
line = graphFile.nextLine( );
StringTokenizer st = new StringTokenizer( line );
try {
if( st.countTokens( ) != 3 ) {
System.err.println( "Skipping bad line " + line );
continue;
}
String source = st.nextToken( );
String dest = st.nextToken( );
int cost = Integer.parseInt( st.nextToken( ) );
g.addEdge( source, dest, cost );
}
catch( NumberFormatException e )
{ System.err.println( "Skipping bad line " + line ); }
}
}
catch(IOException e ){
System.err.println(e);
}
System.out.println( "File read..." );
Scanner in = new Scanner( System.in );
while( processRequest( in, g ) )
;
} // end main
/**
2 * Process a request; return false if end of file.
3 */
public static boolean processRequest( Scanner in, Graph g ) {
try {
System.out.print( "Enter start node:" );
String startName = in.nextLine( );
System.out.print( "Enter destination node:" );
String destName = in.nextLine( );
System.out.print( "Enter algorithm (u, d, n, a ): " );
String alg = in.nextLine( );
switch (alg) {
case "u":
g.unweighted(startName);
case "d":
g.dijkstra(startName);
case "n":
g.negative(startName);
case "a":
g.acyclic(startName);
default:
System.out.println("Performing unweighted analysis");
g.unweighted(startName);
}
g.printPath( destName );
}
catch(NoSuchElementException e){
return false;
}
catch(GraphException e ){
System.err.println(e);
}
return true;
} // end processRequest
}
class Path implements Comparable {
public Vertex dest;
public double cost;
public Path(Vertex d, double c) {
dest = d;
cost = c;
} // end constructor
public int compareTo(Path rhs) {
double otherCost = rhs.cost;
// this DOUBLE TERNARY statement returns
// -1 if this.cost < parameter Path cost
// 1 if this.cost > parameter Path cost
// 0 if the costs are equal
return cost < otherCost ? -1 : cost > otherCost? 1 : 0;
} // end compareTo
} // end class Path
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
import java.util.StringTokenizer;
public class PrimJarnik {
public static void main( String [ ] args ) {
Graph g = new Graph( );
// Uncomment the following line to load a test graph.
loadTestGraph(g);
g.printGraph();
// Uncomment the following line to load a graph from a file.
//loadGraph(g);
g.clearAll();
System.out.println( "File read, graph loaded." );
System.out.println( "Running Prim-Jarnik..." );
Graph ans = g.prim();
ans.printGraph();
} // end main
// Loads the graph I use in the presentation for testing purposes.
public static void loadTestGraph(Graph g){
g.addEdge("A", "B", 6);
g.addEdge("B", "A", 6);
g.addEdge("A", "D", 4);
g.addEdge("D", "A", 4);
g.addEdge("D", "B", 7);
g.addEdge("B", "D", 7);
g.addEdge("B", "E", 7);
g.addEdge("E", "B", 7);
g.addEdge("B", "C", 10);
g.addEdge("C", "B", 10);
g.addEdge("D", "C", 8);
g.addEdge("C", "D", 8);
g.addEdge("D", "E", 12);
g.addEdge("E", "D", 12);
g.addEdge("E", "C", 5);
g.addEdge("C", "E", 5);
g.addEdge("E", "F", 7);
g.addEdge("F", "E", 7);
g.addEdge("C", "F", 6);
g.addEdge("F", "C", 6);
}// end loadTestGraph
public static void loadGraph(Graph g){
try {
Scanner input = new Scanner(System.in);
System.out.println("Enter file name: ");
String file = input.next();
FileReader fin = new FileReader(file);
Scanner graphFile = new Scanner(fin);
// Read the edges and insert
String line;
while( graphFile.hasNextLine( ) ) {
line = graphFile.nextLine( );
StringTokenizer st = new StringTokenizer( line );
try {
if( st.countTokens( ) != 3 ) {
System.err.println( "Skipping bad line " + line );
continue;
}
String source = st.nextToken( );
String dest = st.nextToken( );
int cost = Integer.parseInt( st.nextToken( ) );
g.addEdge( source, dest, cost );
}
catch( NumberFormatException e )
{ System.err.println( "Skipping bad line " + line ); }
}
}
catch( IOException e )
{ System.err.println( e ); }
}// end loadGraph
}
import java.util.LinkedList;
import java.util.List;
class Vertex implements Comparable {
public String name;
public List adj;
public double dist;
public Vertex prev; // previous Vertex on shortest path
public int visited;
public Vertex(String nm)
{ name = nm; adj = new LinkedList(); visited = 0;}
public void reset()
{ dist = Graph.INFINITY; prev = null; visited = 0;}
public int compareTo(Vertex other)
{ return (int) (this.dist - other.dist); }
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started