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