Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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();
    }

}
share|improve this question

2 Answers 2

up vote 6 down vote accepted
  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.

share|improve this answer
    
@PeterTaylor: Yes it should, fixed thanks –  ChrisWue Oct 7 '13 at 18:39
    
You can fix the codeblock by simply intending it by 8 spaces, no need for the quote. –  Bobby Oct 8 '13 at 7:14
    
@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. –  ChrisWue Oct 8 '13 at 7:16

It looks ok to me (did not review functionality). Only think i can suggest is to use validation from commons-lang so you can shorten your parameter validity checks.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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