7
\$\begingroup\$

Please pick my code apart and give me some feedback on how I could make it better or more simple.

final class Edge {
    private final Node node1, node2;
    private final int distance;

    public Edge (Node node1, Node node2, int distance) {
        this.node1 = node1;
        this.node2 = node2;
        this.distance = distance;
    }

    public Node getAdjacentNode (Node node) {
        return node.getValue() != node1.getValue() ? node1 : node2; 
    }

    public int getDistance() {
        return distance;
    }
}

class Node {
    private final int v;
    private int distance = Integer.MAX_VALUE;

    public Node (int v) {
        this.v = v;
    }

    public int getValue() {
        return v;
    }
    public int getDistance() {
        return distance;
    }

    public void setDistance(int distance) {
        this.distance = distance;
    }

    @Override
    public boolean equals(Object o) {
        Node node = (Node) o;
        return node.getValue() == v;
    }

    @Override
    public int hashCode() {
        return v;
    }
}


class Graphs {

    private final Map<Node, ArrayList<Edge>> map;
    private final int numberOfVertices; 

    Graphs(int numberOfVertices) {
        if (numberOfVertices < 0) {
            throw new IllegalArgumentException("A vertex cannot be less than zero");
        }
        this.numberOfVertices = numberOfVertices;
        this.map = new HashMap<Node, ArrayList<Edge>>();
    }

    public void addEdge (Node node1, Node node2, int distance) {
        // necessary to throw null ptr exceptions explicitly since, null can get propagated and saved in edge
        if (node1 == null || node2 == null) {
            throw new NullPointerException("Either of the 2 nodes is null.");
        }
        if (distance < 0) {
            throw new IllegalArgumentException(" The distance cannot be negative. ");
        }

        Edge edge = new Edge(node1, node2, distance);

        addToMap(node1, edge);
        addToMap(node2, edge);
    }

    private void addToMap (Node node, Edge edge) {
        if (map.containsKey(node)) {
            List<Edge> l = map.get(node);
            l.add(edge);
        } else  {
            List<Edge> l = new ArrayList<Edge>();
            l.add(edge);
            map.put(node, (ArrayList<Edge>) l);
        }  
    }

    public List<Edge> getAdj(Node node) {
        return map.get(node);
    }

    public Map<Node, ArrayList<Edge>> getGraph() {
        return map;
    }


    public int getNumVertices() {
        return numberOfVertices;
    }
}

public class Dijkstra {

    private final Graphs graph;

    public Dijkstra(Graphs graph) {
        if (graph == null) {
            throw new NullPointerException("The input graph cannot be null.");
        }
        this.graph = graph;
    }

    /**
     * http://stackoverflow.com/questions/2266827/when-to-use-comparable-and-comparator
     */
    public class NodeCompator implements Comparator<Node>  {
        @Override
        public int compare(Node n1, Node n2) {
            if (n1.getDistance() > n2.getDistance()) {
                return 1;
            } else {
                return -1;
            }
        }
    };

    public Set<Node> findShortest(int source) {
        final Queue<Node> queue = new PriorityQueue<Node>(10, new NodeCompator());

        for (Entry<Node, ArrayList<Edge>> entry :  graph.getGraph().entrySet()) {
            Node currNode = entry.getKey();
            if (currNode.getValue() == source) {
                currNode.setDistance(0);
                queue.add(currNode);
            } 
        }

        final Set<Node> doneSet = new HashSet<Node>();

        while (!queue.isEmpty()) {
            Node src = queue.poll();
            doneSet.add(src);

            for (Edge edge : graph.getAdj(src)) {
                Node currentNode = edge.getAdjacentNode(src);

                if (!doneSet.contains(currentNode)) {
                    int newDistance = src.getDistance() + edge.getDistance();
                    if (newDistance < currentNode.getDistance()) {
                        currentNode.setDistance(newDistance);
                        queue.add(currentNode);
                    } 
                }
            }
        }

        return graph.getGraph().keySet();
    }

}
\$\endgroup\$
  • \$\begingroup\$ It looks ok to me (did not review functionality). The only thing I can suggest is to use validation from commons-lang so you can shorten your parameter validity checks. \$\endgroup\$ – DominikM Oct 7 '13 at 6:54
8
\$\begingroup\$
  1. In your Edge class getAdjacentNode() returns node1 or node2 regardless whether the parameter is one of the two. You should consider throwing an exception (IllegalStateEeption maybe) if the parameter is neither of them.

  2. Your Graphs class should be Graph - an instance of that class represents a single graph and not multiple ones, doesn't it?

  3. What is the point of the numberOfVertices member? It's not used for anything. You should remove it.

  4. You use the distance member of the node to store transient values during the computation in Dijkstra. It's never good to intermingle data representation and iteration over the data. Keep the transient data you need for Dijkstra separate from the nodes and edges. It might incur some extra memory overhead but it's usually worth it. For example if your algorithm fails then it might leave the graph in an inconsistent state. Also you have to reset the graph when you want to re-compute.

  5. This code gets the node with the given value:

    for (Entry<Node, ArrayList<Edge>> entry :  graph.getGraph().entrySet()) {
        Node currNode = entry.getKey();
        if (currNode.getValue() == source) {
            currNode.setDistance(0);
            queue.add(currNode);
        } 
    }
    

    I would add this as a method to Graph like getNode(int value). It makes sense to be able to ask a graph for a specific node.

  6. You should not have to care how the graph internally represents its nodes and edges. So instead of having a method getGraph which just dumps the internally used data structure onto the user have a define interface All you need is either a specific node (see point 5) or all nodes. So add another method getAllNodes() which returns all nodes.

Alternatively consider adding a custom iterator which allows users to traverse all the nodes of the graph without having to care about the internal representation.

The reasoning behind that is: If you ever want to change your internal representation then you either have to convert it to the exposed data structure (means you might have to copy around a lot of data) or you have to change all code using it. Neither of them is particularly nice.

\$\endgroup\$
  • \$\begingroup\$ You can fix the codeblock by simply intending it by 8 spaces, no need for the quote. \$\endgroup\$ – Bobby Oct 8 '13 at 7:14
  • \$\begingroup\$ @Bobby: I didn't add the quote, someone else edited my answer. I assume he did it to highlight that that particular bit of code is a quote from the original question and I agree with that. \$\endgroup\$ – ChrisWue Oct 8 '13 at 7:16
3
\$\begingroup\$

I would like to change a little your code:

for (Entry<Node, ArrayList<Edge>> entry :  graph.getGraph().entrySet()) {
      Node currNode = entry.getKey();
      if (currNode.getValue() == source) {
          currNode.setDistance(0);
      queue.add(currNode);
    } 
}

And make it like this:

Node start = new Node(source);
if (graph.getGraph().containsKey(start)) {
    start.setDistance(0);
    queue.offer(start);
}

It allows us to decrease search time from O(n) loop search to constant O(1) map lookup.


I can provide 1 example:

public static void main(String[] args) {
    Graphs G = new Graphs(7);
    G.addEdge(new Node(0), new Node(1), 4);
    G.addEdge(new Node(0), new Node(2), 3);
    G.addEdge(new Node(0), new Node(4), 7);
    G.addEdge(new Node(1), new Node(3), 5);
    G.addEdge(new Node(2), new Node(3), 11);
    G.addEdge(new Node(4), new Node(3), 2);
    G.addEdge(new Node(5), new Node(3), 2);
    G.addEdge(new Node(6), new Node(3), 10);
    G.addEdge(new Node(4), new Node(6), 5);
    G.addEdge(new Node(6), new Node(5), 3);


    Dijkstra dijkstra = new Dijkstra(G);
    Set<Node> path = dijkstra.findShortest(0);

    Iterator<Node> it = path.iterator();
    while (it.hasNext()) {
        System.out.println(it.next().getDistance());
    }

}

And it returns the wrong value for the start node and for the last one which should be 12 and not 19.

Proof

\$\endgroup\$
2
\$\begingroup\$

This code has a flaw.

Try for this input:

Graph G = new Graph(4);
        G.addEdge(new Node(0), new Node(1), 30);
        G.addEdge(new Node(0), new Node(2), 100);
        G.addEdge(new Node(1), new Node(3), 2);
        G.addEdge(new Node(2), new Node(3), 10);

This code returns:

0
30
100
32

But the correct answer is:

0
30
42
32

The issue is that the code doesn't decrease the key when you find some node (which you have seen before but it has not been in the doneSet yet) which is now closer via a new path. But, you did a pretty great job in avoiding that complicated decreaseKey() implementation by allowing the addition of duplicate nodes in the queue. But, you didn't make use of it. By simple changes, your code can work perfectly. Just add this line:

if (!doneSet.contains(src))

to

    while (!queue.isEmpty()) {
        Node src = queue.poll();
        if (!doneSet.contains(src)){
            doneSet.add(src);

            for (UndirectedEdge edge : graph.getAdj(src)) {
                Node currentNode = edge.getAdjacentNode(src);

                if (!doneSet.contains(currentNode)) {
                    int newDistance = src.getDistance() + edge.getDistance();
                    if (newDistance < currentNode.getDistance()) {
                        currentNode.setDistance(newDistance);
                        queue.add(currentNode);
                    } 
                }
            }
        }
    }

Then, in the end, just return:

return doneSet;

rather than:

return graph.getGraph().keySet();

So, here is the complete implementation of the findShortest(int source) method, so as to remove any confusion:

public Set<Node> findShortest(int source) {
    final Queue<Node> queue = new PriorityQueue<Node>(10, new NodeCompator());

    for (Entry<Node, ArrayList<UndirectedEdge>> entry :  graph.getGraph().entrySet()) {
        Node currNode = entry.getKey();
        if (currNode.getValue() == source) {
            currNode.setDistance(0);
            queue.add(currNode);
        } 
    }

    final Set<Node> doneSet = new HashSet<Node>();

    while (!queue.isEmpty()) {
        Node src = queue.poll();
        if (!doneSet.contains(src)){
            doneSet.add(src);

            for (UndirectedEdge edge : graph.getAdj(src)) {
                Node currentNode = edge.getAdjacentNode(src);

                if (!doneSet.contains(currentNode)) {
                    int newDistance = src.getDistance() + edge.getDistance();
                    if (newDistance < currentNode.getDistance()) {
                        currentNode.setDistance(newDistance);
                        queue.add(currentNode);
                    } 
                }
            }
        }
    }

    return doneSet;
}
\$\endgroup\$

protected by Jamal Dec 3 '16 at 4:01

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.