I am trying to implement Dijkstra's algorithm using a directed graph via an adjacency list. I found some sample code I have been using as an example. In that code, the graph is populated like this:
private static final Graph.Edge[] GRAPH = {
new Graph.Edge("a", "b", 7),
new Graph.Edge("a", "c", 9),
new Graph.Edge("a", "f", 14),
new Graph.Edge("b", "c", 10),
new Graph.Edge("b", "d", 15),
new Graph.Edge("c", "d", 11),
new Graph.Edge("c", "f", 2),
new Graph.Edge("d", "e", 6),
new Graph.Edge("e", "f", 9),};
private static final String START = "a";
private static final String END = "e";
Since I need to populate from an adjacency list in a text file, I instead tried to do it in this manner:
List<Graph.Edge> list = new ArrayList<>();
try {
Scanner scanner = new Scanner(new File(filename));
while (scanner.hasNextLine()) {
String source = scanner.findInLine(NAME);
if (source != null) {
while (true) {
String to = scanner.findInLine(NAME);
if (to == null) {
break;
}
int weight = Integer.valueOf(scanner.findInLine(WEIGHT));
list.add(new Graph.Edge(source, to, weight));
}
}
scanner.nextLine();
}
} catch (FileNotFoundException | NumberFormatException e) {
}
with
static final Pattern NAME = Pattern.compile("\\w+");
static final Pattern WEIGHT = Pattern.compile("\\d+");
In the sample code, they then run dijkstra's algorithm on the graph in the following way:
Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
g.printAllPaths();
I tried to update my code to work for this implementation of the algorithm. I came up with the following:
try {
Scanner scanner = new Scanner(new File(filename));
while (scanner.hasNextLine()) {
String source = scanner.findInLine(NAME);
if (source != null) {
while (true) {
String go = scanner.findInLine(NAME);
if (go == null) {
break;
}
int weight = Integer.valueOf(scanner.findInLine(WEIGHT));
Graph.Edge edge = new Graph.Edge(source, go, weight);
Graph g = new Graph(GRAPH);
g.dijkstra(source);
g.printPath(go);
}
}
scanner.nextLine();
}
} catch (FileNotFoundException | NumberFormatException e) {
}
When I try and run this, it seems to not correctly populate my graph. It produces the errors from the dijkstra and printPath method saying that "Graph doesn't contain start/end vertex." How can I update my code so that the graph is correctly populated and able to implement the algorithm correctly? Thanks!
EDIT: Here is a sample of my input file
1 2 1 3 1
2 4 2
3 2 2 5 4
4 3 3 5 3
5 1 4
It follows the format source, adj. vertex, weight, adj. vertex, weight....
EDIT 2: Use of Graph.Edge`
class Graph {
private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges
/**
* One edge of the graph (only used by Graph constructor)
*/
public static class Edge {
public final String v1, v2;
public final int dist;
public Edge(String v1, String v2, int dist) {
this.v1 = v1;
this.v2 = v2;
this.dist = dist;
}
}
and
public Graph(Edge[] edges) {
graph = new HashMap<>(edges.length);
//one pass to find all vertices
for (Edge e : edges) {
if (!graph.containsKey(e.v1)) {
graph.put(e.v1, new Vertex(e.v1));
}
if (!graph.containsKey(e.v2)) {
graph.put(e.v2, new Vertex(e.v2));
}
}
//another pass to set neighbouring vertices
for (Edge e : edges) {
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
//graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
}
}
EDIT: Here is where I found the original sample code from http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java
Graph.Edgethat is created from the input data? Thelistandedgevariables don't appear to be used elsewhere.