Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Big Data Concepts, Theories, And Applications

Authors: Shui Yu, Song Guo

1st Edition

3319277634, 9783319277639

More Books

Students also viewed these Databases questions

Question

Examine data collection in research using the questions provided.

Answered: 1 week ago