Write a program that allows the user to read graph information from a text file

Question

Write a program that allows the user to read graph information from a text file that s/he specifies. Once the file is loaded, the user should be able to view all the vertices and edges (including weights) of the graph. (No need to do this graphically – although you’re welcome to do so if you want!) The user should also be able to select any two vertices from the graph and see the cost of the optimal path between them, as well as the optimal path itself.

Assume that the data file just lists the edges in the graph and their weights. For the example graph discussed previously, the file would look like this:

Note that each graph does not necessarily have a unique file representation. The edges could be listed in any order. Use the following class design for the project:

• Vertex class: This should include an instance variable for the vertex’s name, as well as instance variables for the various quantities needed in Dijkstra’s algorithm (distance, visited status, and previous vertex). You can assume that all vertices in the graph will have unique names.

Edge class: This should include instance variables for the start and end vertices, as well as the edge’s weight.

Graph class: This should include a list of Vertex objects and a list of Edge objects as instance variables. You

can use java.util.ArrayList or java.util.LinkedList for these lists. This class should also include the following methods:

o A method that loads information from a data file
o A method that runs Dijkstra’s algorithm using a specified start and end vertex
o A toString method that includes information about the graph’s vertices and edges

• MappingApp class: This is the client program where all user input will be made. It should contain an instance of Graph and allow the user to load a data file, view the currently loaded graph, or find the shortest path between two vertices in the currently loaded graph. As mentioned before, display both the optimal cost as well as the path itself.

Implement error checking on all user inputs! This includes exception handling: possible crashes due to exceptions like InputMismatchException or FileNotFoundException should be gracefully handled. Your program should never crash due to user input. (However, you can assume that the input file is formatted correctly and contains no duplicate edges.)

Some helpful tips:

You can use the constant Double.POSITIVE_INFINITY for the value of .

The static method Double.parseDouble(String s) is useful to read a string as a double value. The method

returns the double value that was read. For example, calling Double.parseDouble(“3.14”) returns the double value 3.14.

Background Information

Dijkstra’s algorithm, developed in 1959 by the Dutch computer scientist of the same name, gives a way of computing the “shortest” (lowest-cost) path between any two vertices of a graph. Here’s how the algorithm works. Given a graph and a starting vertex:

Assign each vertex a “distance” value. This value will represent the optimal distance between that vertex and the starting vertex. To begin with, assign the starting vertex a distance of 0 and all other vertices a distance of .

Mark all vertices as “unvisited.”

From the entire graph, pick the unvisited vertex with the lowest distance value. Note that the first time you do

this, it’ll always be the starting vertex. Call this the “current” vertex, V.

Consider each of V’s unvisited neighbors (i.e., vertices that are directly accessible from V). For each of these

neighbors N, compute N’s “tentative” distance by adding V’s distance to the weight of the edge connecting V and N. If this tentative distance is less than N’s existing distance, overwrite N’s distance with the new one. When an overwrite is performed, also record vertex V as the “previous” vertex of vertex N.

Once you’ve checked all of V’s unvisited neighbors, mark V as visited. V is now “done” and will not be involved in the algorithm any more.

Check if all vertices in the graph have been visited. If so, the algorithm is finished. If not, return to step 3.

Once the algorithm is finished, the final distance values for each vertex represent the minimum cost required to get from the starting vertex to that vertex. The shortest path itself can be found by going to the end vertex, going to its “previous” vertex, going to that previous vertex’s own “previous” vertex, and so on until you reach the starting vertex.

Aside from its obvious applications for finding routes on maps, Dijkstra’s algorithm is used in a number of network routing protocols (algorithms that determine the optimal paths to send data packets over a network).

Side note: I will not be copying the coding answer, just need to see what needs to be done.

Thank you in advance.

Explanation / Answer

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

public class MappingApp {
   public static class Vertex{
       String name;
       int id;
   }
   public static class Edge{
       Vertex start;
       Vertex end;
       double cost;
   }
   public static void main(String args[]){
       ArrayList<Edge> edges = new ArrayList<>();
       String FILENAME = "C:\Users\Gaurav\Desktop eminder.txt";
       BufferedReader br = null;
       FileReader fr = null;
       int primeLimit = 0;
       String message = null;
       try{
           fr = new FileReader(FILENAME);
           br = new BufferedReader(fr);

           String sCurrentLine;

           br = new BufferedReader(new FileReader(FILENAME));
           while ((sCurrentLine = br.readLine()) != null) {
               String[] splited = sCurrentLine.split("\s+");
               System.out.println(splited[0]+" "+splited[1]+" "+splited[2]);
               Vertex v1 = new Vertex();
               v1.name = splited[0];
               v1.id = (int)splited[0].charAt(0);
               Vertex v2 = new Vertex();
               v2.name = splited[0];
               v2.id = (int)splited[0].charAt(0);
               Edge edge = new Edge();
               edge.start = v1;
               edge.end = v2;
               edge.cost = Double.parseDouble(splited[2]);
               edges.add(edge);
           }
       }catch (IOException e) {
           e.printStackTrace();
       }
       double Adjacency[][] = new double[26][26];
       for(Edge edge:edges){
           Adjacency[edge.start.id][edge.end.id] = edge.cost;
       }
       // Once you have adjacency list, you can easily calculate shortest path using Dijksta
       // Here is the link for its implementation.....
       //http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
   }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.