Check if directed graph contains a cycle

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 implements Iterable {

/* 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> graph = new HashMap>();

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

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.

StackExchange Code Review Q#38063, answer score: 4