I have solved the question, and in turn felt the need to get it reviewed. Any suggestions for clean up and optimization would help. Also please verify my complexity: \$O(V + E)\$.

GraphCycleDetection should be named to Graph, but it was named on purpose to avoid conflict in Eclipse workspaces, so please ignore renaming it as part of feedback.

Thanks to Keith Schwarz's code, which was a huge inspiration in designing my classes.

class GraphCycleDetection<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 source                    the source node.
     * @param destination               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 source, T destination, double length) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            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(source).put(destination, length);
    }

    /**
     * Removes an edge from the graph.
     * 
     * @param source        If the source node.
     * @param destination   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 source, T destination) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        graph.get(source).remove(destination);
    }

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



/**
 * 
 * Complexity:
 * O (V + E)
 * http://stackoverflow.com/questions/6850357/explanation-of-runtimes-of-bfs-and-dfs
 */
public final class DAGCycleDetection {

    private DAGCycleDetection() { }

    /** 
     * Returns true if graph contains a cycle else returns false
     * 
     * @param graph  the graph to check for cycle
     * @return true if cycle exists, else false.
     */
    public static <T> boolean cycle(GraphCycleDetection<T> graph) {
        final Set<T> visitedNodes = new HashSet<T>();
        final Set<T> completedNodes = new HashSet<T>();

        for (T node : graph) {
            if (dfs(graph, node, visitedNodes, completedNodes)) return true;
        }
        return false;
    }

    /** 
     * Returns true if graph contains a cycle else returns false
     * 
     * 
     * @param graph              the graph, which should be checked for cycles
     * @param node               the current node whose edges should be traversed.
     * @param visitedNodes       the nodes visited so far.  
     * @return                   true if graph contains a cycle else return false;
     */
    private static <T> boolean dfs (GraphCycleDetection<T> graph, 
                                    T node, 
                                    Set<T> visitedNodes,
                                    Set<T> completedNodes
                                    ) {
        assert graph != null;
        assert node != null;
        assert visitedNodes != null;

        if (visitedNodes.contains(node)) {
            if (completedNodes.contains(node)) return false;
            return true;
        }

        visitedNodes.add(node); // constitues O(1) for each vertex

        for (Entry<T, Double> entry : graph.edgesFrom(node).entrySet()) {
            if (dfs(graph, entry.getKey(), visitedNodes, completedNodes)) return true;
        }

        completedNodes.add(node);

        return false;
    }

    public static void main(String[] args) {
        GraphCycleDetection<Integer> gcd1 = new GraphCycleDetection<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);
        System.out.println("Expected false, Actual: " + cycle(gcd1));

        GraphCycleDetection<Integer> gcd2 = new GraphCycleDetection<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);
        System.out.println("Expected true, Actual: " + cycle(gcd2));

        GraphCycleDetection<Integer> gcd3 = new GraphCycleDetection<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);
        System.out.println("Expected false, Actual: " + cycle(gcd3));


        GraphCycleDetection<Integer> gcd4 = new GraphCycleDetection<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);
        System.out.println("Expected true, Actual: " + cycle(gcd4));

        // disconnected graph.
        GraphCycleDetection<Integer> gcd5 = new GraphCycleDetection<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); 
        System.out.println("Expected true, Actual: " + cycle(gcd5));
    }
}
up vote 4 down vote accepted

You are going about this wrong.... closing the stable door after the horse has bolted.

Your addEdge() method should throw an exception if adding the edge would result in an invalid DAG.

This way you can guarantee that there are no cycles, your Graph is always valid, and you do not need to do a monolithic 'stop the world' check for every node.

Checking for cycles before adding an edge is a whole lot easier too (although not necessarily faster) because you do not need to rely on any complicated memory structures to do it.

private boolean isReachable(T target, T from) {
    if (target.equals(from)) {
        return true;
    }
    for (T nxt : graph.get(from).keySet()) {
        if (isReachable(target, nxt)) {
            return true;
        }
    }
    return false;
}

Then, in your addEdge(...) method you can simply:

if (isReachable(source, destination)) {
    throw new IllegalArgumentException("Cannot add this edge because it would create a cycle");
}

While this method for pre-validating the graph may, in the long run, consume (slightly) more time than a single global graph-validation, it will allow a number of other processes to make better choices and assumptions. Being able to guarantee an acyclic graph at all times is very beneficial.

Just something minor:

I'm not sure why you keep on insisting to name data structures after specific algorithms (you seem to do that in most of your code you post).

  1. GraphCycleDetection is a graph and should therefore be named Graph. It can be used for many other things not just for cycle detection.

  2. DAGCycleDetection is a bit of an oxymoron: DAG means Directed Acyclic Graph which by definition contains no cycles. The class should probably just be named GraphCycleDetection (which is possible if you name your data structure properly).

  3. cycle should be named hasCycle - this will make it clear just by reading the method name of what the return value represents.

  • I am fully aware of my naming being distorted. Its done because I dont want conflicts in my eclipse workspace. GraphCycleDetection should be named to Graph, but named on purpose to avoid conflict in eclipse workspaces, please ignore renameming it as part of feedback. – JavaDeveloper Dec 25 '13 at 18:33

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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