creating objects from trivial graph format text file. java. dijkstra algorithm.
- by user560084
i want to create objects, vertex and edge, from trivial graph format txt file. one of programmers here suggested that i use trivial graph format to store data for dijkstra algorithm.
the problem is that at the moment all the information, e.g., weight, links, is in the sourcecode. i want to have a separate text file for that and read it into the program.
i thought about using a code for scanning through the text file by using scanner. but i am not quite sure how to create different objects from the same file. could i have some help please?
the file is
v0 Harrisburg
v1 Baltimore
v2 Washington
v3 Philadelphia
v4 Binghamton
v5 Allentown
v6 New York
#
v0 v1 79.83
v0 v5 81.15
v1 v0 79.75
v1 v2 39.42
v1 v3 103.00
v2 v1 38.65
v3 v1 102.53
v3 v5 61.44
v3 v6 96.79
v4 v5 133.04
v5 v0 81.77
v5 v3 62.05
v5 v4 134.47
v5 v6 91.63
v6 v3 97.24
v6 v5 87.94
and the dijkstra algorithm code is
Downloaded from: http://en.literateprograms.org/Special:Downloadcode/Dijkstra%27s_algorithm_%28Java%29
*/
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Vertex implements Comparable<Vertex>
{
public final String name;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) {
name = argName;
}
public String toString() {
return name;
}
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}
}
class Edge
{
public final Vertex target;
public final double weight;
public Edge(Vertex argTarget, double argWeight) {
target = argTarget;
weight = argWeight;
}
}
public class Dijkstra
{
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}
public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}
public static void main(String[] args)
{
Vertex v0 = new Vertex("Nottinghill_Gate");
Vertex v1 = new Vertex("High_Street_kensignton");
Vertex v2 = new Vertex("Glouchester_Road");
Vertex v3 = new Vertex("South_Kensignton");
Vertex v4 = new Vertex("Sloane_Square");
Vertex v5 = new Vertex("Victoria");
Vertex v6 = new Vertex("Westminster");
v0.adjacencies = new Edge[]{new Edge(v1, 79.83), new Edge(v6, 97.24)};
v1.adjacencies = new Edge[]{new Edge(v2, 39.42), new Edge(v0, 79.83)};
v2.adjacencies = new Edge[]{new Edge(v3, 38.65), new Edge(v1, 39.42)};
v3.adjacencies = new Edge[]{new Edge(v4, 102.53), new Edge(v2, 38.65)};
v4.adjacencies = new Edge[]{new Edge(v5, 133.04), new Edge(v3, 102.53)};
v5.adjacencies = new Edge[]{new Edge(v6, 81.77), new Edge(v4, 133.04)};
v6.adjacencies = new Edge[]{new Edge(v0, 97.24), new Edge(v5, 81.77)};
Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };
computePaths(v0);
for (Vertex v : vertices)
{
System.out.println("Distance to " + v + ": " + v.minDistance);
List<Vertex> path = getShortestPathTo(v);
System.out.println("Path: " + path);
}
}
}
and the code for scanning file is
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
public class DataScanner1 {
//private int total = 0;
//private int distance = 0;
private String vector;
private String stations;
private double [] Edge = new double [];
/*public int getTotal(){
return total;
}
*/
/*
public void getMenuInput(){
KeyboardInput in = new KeyboardInput;
System.out.println("Enter the destination? ");
String val = in.readString();
return val;
}
*/
public void readFile(String fileName) {
try {
Scanner scanner =
new Scanner(new File(fileName));
scanner.useDelimiter
(System.getProperty("line.separator"));
while (scanner.hasNext()) {
parseLine(scanner.next());
}
scanner.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public void parseLine(String line) {
Scanner lineScanner = new Scanner(line);
lineScanner.useDelimiter("\\s*,\\s*");
vector = lineScanner.next();
stations = lineScanner.next();
System.out.println("The current station is " + vector + " and the destination to the next station is " + stations + ".");
//total += distance;
//System.out.println("The total distance is " + total);
}
public static void main(String[] args) {
/* if (args.length != 1) {
System.err.println("usage: java TextScanner2"
+ "file location");
System.exit(0);
}
*/
DataScanner1 scanner = new DataScanner1();
scanner.readFile(args[0]);
//int total =+ distance;
//System.out.println("");
//System.out.println("The total distance is " + scanner.getTotal());
}
}
