Detect cycle in an undirected graph

Question

This code detects cycle in acyclic graph. The assumption of this approach is that there are no parallel edges between any two vertices. Looking for code review, best practices and optimizations.

Also verify the complexity is O(E) and not O(V+E).

class AcyclicGraphCycleDetection<T> implements Iterable<T> {

    /* A map from nodes in the graph to sets of outgoing edges.  Each
     * set of edges is represented by a map from edges to doubles.
     */
    private final Map<T, Map<T, Double>> graph = new HashMap<T, Map<T, Double>>();

    /**
     *  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(T node) {
        if (node == null) {
            throw new NullPointerException("The input node cannot be null.");
        }
        if (graph.containsKey(node)) return false;

        graph.put(node, new HashMap<T, Double>());
        return true;
    }


    /**
     * Given the source and destination node it would add an arc from source 
     * to destination node. If an arc already exists then the value would be 
     * updated the new value.
     *  
     * @param nodeA                    the source node.
     * @param nodeB                    the destination node.
     * @param length                    if length if 
     * @throws NullPointerException     if source or destination is null.
     * @throws NoSuchElementException   if either source of destination does not exists. 
     */
    public void addEdge (T nodeA, T nodeB, double length) {
        if (nodeA == null || nodeB == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(nodeA) || !graph.containsKey(nodeB)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        /* A node would always be added so no point returning true or false */
        graph.get(nodeA).put(nodeB, length);
        graph.get(nodeB).put(nodeA, length);
    }

    /**
     * Removes an edge from the graph.
     * 
     * @param nodeA        If the source node.
     * @param nodeB   If the destination node.
     * @throws NullPointerException     if either source or destination specified is null
     * @throws NoSuchElementException   if graph does not contain either source or destination
     */
    public void removeEdge (T nodeA, T nodeB) {
        if (nodeA == null || nodeB == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(nodeA) || !graph.containsKey(nodeB)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        graph.get(nodeA).remove(nodeB);
        graph.get(nodeB).remove(nodeA);
    }

    /**
     * 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<T, Double> edgesFrom(T node) {
        if (node == null) {
            throw new NullPointerException("The node should not be null.");
        }
        Map<T, Double> edges = graph.get(node);
        if (edges == null) {
            throw new NoSuchElementException("Source node does not exist.");
        }
        return Collections.unmodifiableMap(edges);
    }

    /**
     * Returns the iterator that travels the nodes of a graph.
     * 
     * @return an iterator that travels the nodes of a graph.
     */
    @Override public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }
}


public final class AcyclicCycleDetection {

    private AcyclicCycleDetection() {}

    public static <T> boolean cycle(AcyclicGraphCycleDetection<T> graph) {
        return cycleCheck(graph, graph.iterator().next(), null,  new HashSet<T>());
    }


    private static <T> boolean cycleCheck(AcyclicGraphCycleDetection<T> graph, T node, T parent, Set<T> visitedNodes) {
        if (visitedNodes.contains(node)) {
            return true;
        }

        visitedNodes.add(node);

        for (Entry<T, Double> entry : graph.edgesFrom(node).entrySet()) {
            /*
             * entry.getKey() != parent is the most important piece.
             * 
             * Since its an uni-directed graph, we have a link from 
             * 1->2, as well as a link from 2->1.
             *  
             * So if we dont have this "entry.getKey() != parent" condition, we would always get true for a cycle.  
             */
            if (entry.getKey() != parent && cycleCheck(graph, entry.getKey(), node, visitedNodes)) return true;
        }
        return false;
    }
}

public class AcyclicCycleDetectionTest {

    @Test
    public void test1() {
        AcyclicGraphCycleDetection<Integer> gcd1 = new AcyclicGraphCycleDetection<Integer>();
        gcd1.addNode(1);  gcd1.addNode(2); gcd1.addNode(3);
        gcd1.addEdge(1, 2, 10);
        gcd1.addEdge(2, 3, 10); 
        gcd1.addEdge(1, 3, 10);
        assertEquals(true, AcyclicCycleDetection.cycle(gcd1));
    }

    @Test
    public void test2() {
        AcyclicGraphCycleDetection<Integer> gcd2 = new AcyclicGraphCycleDetection<Integer>();
        gcd2.addNode(1); gcd2.addNode(2); gcd2.addNode(3);
        gcd2.addEdge(1, 2, 10); 
        gcd2.addEdge(2, 3, 10); 
        gcd2.addEdge(3, 1, 10);
        assertEquals(true, AcyclicCycleDetection.cycle(gcd2));
    }

    @Test
    public void test3() {
        AcyclicGraphCycleDetection<Integer> gcd3 = new AcyclicGraphCycleDetection<Integer>();
        gcd3.addNode(1); gcd3.addNode(2); gcd3.addNode(3); gcd3.addNode(4); gcd3.addNode(5); 
        gcd3.addEdge(1, 2, 10); 
        gcd3.addEdge(2, 3, 10); 
        gcd3.addEdge(2, 4, 10);
        gcd3.addEdge(3, 4, 10); 
        gcd3.addEdge(4, 5, 10);
        assertEquals(true, AcyclicCycleDetection.cycle(gcd3));
    }

    @Test
    public void test4() {
        AcyclicGraphCycleDetection<Integer> gcd4 = new AcyclicGraphCycleDetection<Integer>();
        gcd4.addNode(1); gcd4.addNode(2); gcd4.addNode(3); gcd4.addNode(4); gcd4.addNode(5); 
        gcd4.addEdge(1, 2, 10);
        gcd4.addEdge(2, 3, 10); 
        gcd4.addEdge(2, 4, 10); 
        gcd4.addEdge(3, 4, 10);
        gcd4.addEdge(4, 5, 10);  
        gcd4.addEdge(5, 2, 10);
        assertEquals(true, AcyclicCycleDetection.cycle(gcd4));
    }

    @Test
    public void test5() {
        // disconnected graph.
        AcyclicGraphCycleDetection<Integer> gcd5 = new AcyclicGraphCycleDetection<Integer>();
        gcd5.addNode(1); gcd5.addNode(2); gcd5.addNode(3); gcd5.addNode(10); gcd5.addNode(11);
        gcd5.addEdge(1, 2, 10); 
        gcd5.addEdge(2, 3, 10); 
        gcd5.addEdge(3, 1, 10); 
        gcd5.addEdge(10, 11, 10); 
        assertEquals(true, AcyclicCycleDetection.cycle(gcd5));
    }

    @Test
    public void test6() {
        AcyclicGraphCycleDetection<Integer> gcd6 = new AcyclicGraphCycleDetection<Integer>();
        gcd6.addNode(1); gcd6.addNode(2); gcd6.addNode(3); gcd6.addNode(4);
        gcd6.addEdge(1, 2, 10); 
        gcd6.addEdge(2, 3, 10); 
        gcd6.addEdge(2, 4, 10); 
        assertEquals(false, AcyclicCycleDetection.cycle(gcd6));
    }
}

Answer 1

I'm not keen on AcyclicGraphCycleDetection, which is trying to be too many different things at once.

1. It is acting as a definition of your Graph abstraction
2. It is acting as an implementation of your Graph abstraction
3. It is acting as a builder of your graph abstraction

On top of that, it is not named particularly well for any of those three jobs.

I would expect to see, at a minimum:

public interface Graph<T> {
    ... methods you are going to use in your algorithm here
}

public class MapBackedGraph<T> extends Graph<T> {
    private final Map<T, Map<T,Double>> nodes;

    MapBackedGraph(Map<T, Map<T,Double>> nodes) {
        this.nodes = nodes;
    }

    ... implementation of Graph<T> methods
}

Since the construction of the graph is (a) complicated, and (b) separable from the cycle detection algorithm, you ought to be treating the construction of the graph object as a distinct idea...

public interface GraphBuilder<T> {
    public boolean addNode(T node);
    public boolean addEdge(T first, T second, double length);
    public boolean removeEdge(T first, T second);

    public Graph<T> build();
}

public class MapBackedGraphBuilder<T> implements GraphBuilder<T> {
    ...
}

The point here being that when you notice that you want to try a graph implementation that treats edges as first class citizens, you can easily create a new builder implementation that incorporates edges. Or if you happen to notice that you don't really need to know edge length to detect cycles, you could implement a simpler graph builder, that discards the unnecessary length parameter altogether.

An alternative structure that appears in some code bases is to implement the builder as a static inner class of the graph implementation

public class MapBackedGraph<T> extends Graph<T> {
    private final Map<T, Map<T,Double>> nodes;

    MapBackedGraph(Map<T, Map<T,Double>> nodes) {
        this.nodes = nodes;
    }

    ... implementation of Graph<T> methods

    public static class Builder implements GraphBuilder<T> {
        ... implementation of GraphBuilder<T> methods
    }
}

Law of Demeter: you should really be asking for the thing you need, not a thing to get the thing you need.

   for (Entry<T, Double> entry : graph.edgesFrom(node).entrySet()) {
   }

In this block, you are asking for an Edge, so that you can later ask the edge for the other endpoint. Messy. Rewrite the logic so that your loop makes sense

for (Node neighbor : graph.getNeighbors(node)) {
    if ( node == parent ) {
        // Backtracking along the same edge doesn't count as a cycle
    } else {
        if ( cycleCheck(...) ) {
            return true;
        }
    }
}

It's a little bit clumsy to keep repeating graph and visitedNodes all the time. Probably better to recognize that those are properties of the query, and not the iteration. So make a representation of that

 public class CycleQuery<T> {
     private final Graph<T> graph;
     private final Set<T> visitedNodes = new HashSet();

     public CycleQuery(Graph <T> graph) {
         this.graph = graph;
     }

     public boolean cycleCheck(T node, T parent) {
         ...
     }
 }

Answer 2

If the graph can have two or more disconnected subgraphs, you might want to take measures to ensure you check all of the subgraphs. If having disconnected subgraphs is also an error condition, then at least you would want to detect that event rather than letting cycleCheck just traverse one of the subgraphs and then return false.

Alternatively, change the way you build the graph. You could allow a single node to be added to an empty graph, and after that the only change permitted is to add a new node with an edge to an existing node. The resulting graph will always be connected and will never contain a cycle. This construction does impose some restrictions on the sequence with which you add nodes, however; if the graph so far consists of just nodes A and B, which are connected, you can't connect nodes C and D to each other until you connect one of them to either A or B.

By the way, I find the names AcyclicGraphCycleDetection and AcyclicCycleDetection very confusing. It seems that AcyclicGraphCycleDetection is actually the graph itself, while AcyclicCycleDetection is the cycle-detection algorithm to be executed on the graph, but it's hard to remember which name is which, and you could almost not notice that these are two very different types. I suggest naming the graph something simpler, without the words "acyclic", "cycle", or "detection" (unless you change the way it is constructed so that it is guaranteed to be acyclic, in which case it is OK for "acyclic" to be part of the name).