0

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

7
  • You should do some debugging. Commented Mar 26, 2016 at 18:12
  • In what regard? As far as I know, my method for populating the ArrayList is correct. I am just struggling with how to instead translate that to a graph. Commented Mar 26, 2016 at 18:13
  • Can we please see a sample of your input file. Commented Mar 26, 2016 at 18:14
  • I've updated the post to add it Commented Mar 26, 2016 at 18:16
  • In both algorithm attempts, where do you use the Graph.Edge that is created from the input data? The list and edge variables don't appear to be used elsewhere. Commented Mar 26, 2016 at 18:23

1 Answer 1

1

In order to use the application with file input, use your first file input algorithm. Your second algorithm is useless unless you want to run each line of the file as a Graph with only one Vertex.

Use your code like this (I've put comments on the lines I've changed):

private static final Graph.Edge[] GRAPH = getEdges("input.txt"); // <-- CHANGED THIS
private static final String START = "1"; // <-- CHANGED THIS
private static final String END = "5"; // <-- CHANGED THIS

private static Graph.Edge[] getEdges(String fileName) { // <-- ADDED THIS
    final Pattern NAME = Pattern.compile("\\w+");
    final Pattern WEIGHT = Pattern.compile("\\d+");
    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));
                }
            }
            if (scanner.hasNextLine()) // <-- ADDED THIS
                scanner.nextLine();
        }
    } catch (FileNotFoundException | NumberFormatException e) {
    }
    return list.toArray(new Graph.Edge[0]); // <-- ADDED THIS
}

Then, run the application the same way:

Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
g.printAllPaths();

I tested all of this, and also found that your algorithm for file input breaks on the last line of the file, so I added if (scanner.hasNextLine()) before scanner.nextLine();

Sign up to request clarification or add additional context in comments.

5 Comments

Here's a demo of it working: Ideone Demo There I used System.in though instead of a file. (Scroll to the bottom of the webpage to see the input and output)
Maybe it's a small error somewhere in mine, but when I run it I receive errors that the start and end vertex aren't in the graph. I believe its something with how I upload the file. I'm looking at it now.
Are you using values for START & END that are actually in the file?
I've seemed to have worked out all of the bugs now. Thanks for your help
Awesome! Have a great day :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.