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.

Perform a graph clone. Verifying complexity to be O(E). Looking for code review, optimizations and best practices.

class NodeOfGraph<T> {
    private final T item;

    NodeOfGraph(T item) { 
        this.item = item;
    }

    public T getItem() {
        return item;
    }
}

public class GraphWithCloneFunctionality<T> implements Iterable<NodeOfGraph<T>> {

    /*
     *  A map from nodes in the graph to list of outgoing edges. 
     */
    private final Map<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> graph;

    public GraphWithCloneFunctionality() {
        graph = new HashMap<NodeOfGraph<T>,  Map<NodeOfGraph<T>, Double>>();
    }

    public GraphWithCloneFunctionality(Map<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> graph) {
        if (graph == null) {
            throw new NullPointerException("The graph should not be null");
        }
        this.graph = graph;
    }

    /**
     *  Adds a new node to the graph. If the node already exists then its a
     *  no-op.
     * 
     * @param node  Adds to a graph. If node is null then this is a no-op.
     * @return      true if node is added, false otherwise.
     */
    public boolean addNode(NodeOfGraph<T> node) {
        if (node == null) {
            throw new NullPointerException("The input node cannot be null.");
        }
        graph.put(node, new HashMap<NodeOfGraph<T>, Double>());
        return true;
    }

    /**
     * Given the two nodes it would add an arc from source 
     * to destination node. 
     *  
     * @param node1                     the node1 node.
     * @param node2                     the node2 node.
     * @param length                    if length if string 
     * @throws NullPointerException     if node1 or nod2 is null.
     * @throws NoSuchElementException   if either node1 or node2 does not exists. 
     */ 
    public void addEdge (NodeOfGraph<T> node1, NodeOfGraph<T> node2, double length) { 
        if (node1 == null || node2 == null) {
            throw new NullPointerException("node1 and node2, both should be non-null.");
        }
        if (!graph.containsKey(node1) || !graph.containsKey(node2)) {
            throw new NoSuchElementException("node1 and node2, both should be part of graph");
        }
        graph.get(node1).put(node2, length);
        graph.get(node2).put(node1, length);
    }

    @Override
    public Iterator<NodeOfGraph<T>> iterator() {
        return graph.keySet().iterator();
    }    

    /**
     * Given a node, returns the edges going outward that node,
     * as an immutable map.
     * 
     * @param node The node whose edges should be queried.
     * @return An immutable view of the edges leaving that node.
     * @throws NullPointerException   If input node is null.
     * @throws NoSuchElementException If node is not in graph.
     */
    public Map<NodeOfGraph<T>, Double> edgesFrom(NodeOfGraph<T> node) {
        if (node == null) {
            throw new NullPointerException("The node should not be null.");
        }
        final Map<NodeOfGraph<T>, Double> edges = graph.get(node);
        if (edges == null) {
            throw new NoSuchElementException("Source node does not exist.");
        }
        return Collections.unmodifiableMap(edges);
    }

    /**
     * Clones the graph. Performs deep copy.
     */
    public GraphWithCloneFunctionality<T> clone() {
        final Map<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> clonedGraph = new HashMap<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>>();
        final Map<NodeOfGraph<T>, NodeOfGraph<T>> cloneMap = new HashMap<NodeOfGraph<T>, NodeOfGraph<T>>();

        for (NodeOfGraph<T> node : graph.keySet()) {
            NodeOfGraph<T> clonedNode = new NodeOfGraph<T>(node.getItem());
            clonedGraph.put(clonedNode, new HashMap<NodeOfGraph<T>, Double>());
            cloneMap.put(node, clonedNode);
        }

        for (Entry<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>>  entry : graph.entrySet())  {
            NodeOfGraph<T> source = entry.getKey();
            NodeOfGraph<T> sourceClone = cloneMap.get(source);
            Map<NodeOfGraph<T>, Double> edges = entry.getValue();

            for (Entry<NodeOfGraph<T>, Double> edge  : edges.entrySet()) {
                NodeOfGraph<T> destination = edge.getKey();
                NodeOfGraph<T> destinationClone = cloneMap.get(destination);
                clonedGraph.get(sourceClone).put(destinationClone, edge.getValue());
            }
        }
        return new GraphWithCloneFunctionality<T>(clonedGraph);
    }


    public static void main(String[] args) {

        GraphWithCloneFunctionality<Integer> graph = new GraphWithCloneFunctionality<Integer>();
        NodeOfGraph<Integer> nodeA = new NodeOfGraph<Integer>(1);
        NodeOfGraph<Integer> nodeB = new NodeOfGraph<Integer>(2);
        NodeOfGraph<Integer> nodeC = new NodeOfGraph<Integer>(3);

        graph.addNode(nodeA);
        graph.addNode(nodeB);
        graph.addNode(nodeC);

        graph.addEdge(nodeA, nodeB, 10);
        graph.addEdge(nodeB, nodeC, 20);

        GraphWithCloneFunctionality<Integer> graphClone = graph.clone();


        for (NodeOfGraph<Integer> node : graphClone) {
            System.out.print("Node-> " + node.getItem() + " Edges-> ");
            for (Entry<NodeOfGraph<Integer>, Double> node1 : graphClone.edgesFrom(node).entrySet()) {
                System.out.print(" Node : " + node1.getKey().getItem() + " value : " + node1.getValue() + " , ");
            }
            System.out.println();
        }
    }
}
share|improve this question

2 Answers 2

Clone is an ugly API. Josh Bloch has a lot to say about it.

My opinion on it, is that you should use it as a last resort, and, when you do use it, it should be a short-cut to a public copy-constructor.

In other words, your clone method should look like:

public GraphWithCloneFunctionality<T> clone() {
    return new GraphWithCloneFunctionality<T>(this);
}

This way, you have the benefit of the Copy-Constructor, and the functionality of the clone as well, if needed.

After having said all that, I can't see any other significant issues in your code's functionality. It looks about right, and nice and clean.

If you create a copy-constructor, it would look something like:

public GraphWithCloneFunctionality(GraphWithCloneFunctionality<T> tocopy) {
    this(copyGraph(tocopy.graph));
}

The copyGraph function would copy the graph, believe it or not.

Talking about graph-copying, this constructor should take a defensive copy of the graph as well. You don't want to have leaks of graph functionality to outside your class...

public GraphWithCloneFunctionality(Map<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> graph) {
    if (graph == null) {
        throw new NullPointerException("The graph should not be null");
    }
    this.graph = graph;
}

The above this.graph = graph is not safe. Use this.graph = copyGraph(graph);

share|improve this answer
    
But I wanted deep-copy. –  JavaDeveloper Apr 7 at 0:45
    
@JavaDeveloper You can do a deep-copy in the constructor just as easily as you do it in the clone.... also, added more detail to answer (submitted early by mistake). –  rolfl Apr 7 at 0:48

Your clone() method looks very nice, and I don't have much to say about it except Good Work.

I've read the code a few times, and even then I almost missed this:

/**
 *  Adds a new node to the graph. If the node already exists then its a
 *  no-op.
 * 
 * @param node  Adds to a graph. If node is null then this is a no-op.
 * @return      true if node is added, false otherwise.
 */
public boolean addNode(NodeOfGraph<T> node) {
    if (node == null) {
        throw new NullPointerException("The input node cannot be null.");
    }
    graph.put(node, new HashMap<NodeOfGraph<T>, Double>());
    return true;
}

The comment assures the caller that trying to add a node which already exists will be no-op and return false.
In actuality - it will override the existing node, deleting all out-going edges, and return true...

This is another example of how a good unit-test suite is a better documentation than comments.

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.