Simple Loop Finder

# Simple Loop Finder

Given a graph consisting of nodes, where any given node can point to any number of other nodes, the code below finds a loop, if it exists, starting from any given node. If the chosen node is part of more than one loop, only the first loop found is returned. If the chosen node is not itself part of a loop, but is connected to a loop, then nothing is returned.

## Tests

 ```package tools.loopfinder; import java.util.ArrayList; import java.util.List; public class LoopFinderTest extends TestCase { public void testSimpleLoop_Trivial_NoLoop() { TestNode n1 = new TestNode("1"); List nodesInLoop = LoopFinder.findSimpleLoop(n1); assertEquals(0, nodesInLoop.size()); } public void testSimpleLoop_NoLoop() { TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); n1.sendTo(n2); List nodesInLoop = LoopFinder.findSimpleLoop(n1); assertEquals(0, nodesInLoop.size()); } public void testSimpleLoop_TightLoop() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); n1.sendTo(n2); n2.sendTo(n1); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // assert assertEquals(2, nodesInLoop.size()); assertEquals(n1, nodesInLoop.get(0)); assertEquals(n2, nodesInLoop.get(1)); } public void testSimpleLoop_TightLoop_WithTail_OnProcessedFacility() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); n1.sendTo(n2); n1.sendTo(n3); n2.sendTo(n1); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // assert assertEquals(2, nodesInLoop.size()); assertEquals(n1, nodesInLoop.get(0)); assertEquals(n2, nodesInLoop.get(1)); } public void testSimpleLoop_TightLoop_WithTail_OnOtherFacility() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); n1.sendTo(n2); n2.sendTo(n3); n2.sendTo(n1); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // assert assertEquals(2, nodesInLoop.size()); assertEquals(n1, nodesInLoop.get(0)); assertEquals(n2, nodesInLoop.get(1)); } public void testSimpleLoop_2TightLoops() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); new TestNode("4"); n1.sendTo(n2); n2.sendTo(n1); n1.sendTo(n3); n3.sendTo(n1); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // assert assertEquals(2, nodesInLoop.size()); assertEquals(n1, nodesInLoop.get(0)); assertEquals(n2, nodesInLoop.get(1)); } public void testSimpleLoop_LargerLoop() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); n1.sendTo(n2); n2.sendTo(n3); n3.sendTo(n1); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // setup assertEquals(3, nodesInLoop.size()); assertEquals(n1, nodesInLoop.get(0)); assertEquals(n2, nodesInLoop.get(1)); assertEquals(n3, nodesInLoop.get(2)); } public void test_NoLoop_ConnectedToALoopDownstream() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); n1.sendTo(n2); n2.sendTo(n3); n3.sendTo(n2); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // setup assertEquals(0, nodesInLoop.size()); } public void test_NoLoop_ConnectedToALoopUpstream() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); n2.sendTo(n1); n3.sendTo(n2); n2.sendTo(n3); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // setup assertEquals(0, nodesInLoop.size()); } public void test_Loop_MainLoopContainsNestedLoop() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); n1.sendTo(n3); n2.sendTo(n1); n3.sendTo(n2); n2.sendTo(n3); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // assert assertEquals(3, nodesInLoop.size()); assertEquals(n1, nodesInLoop.get(0)); assertEquals(n3, nodesInLoop.get(1)); assertEquals(n2, nodesInLoop.get(2)); } public void test_Loop_MainLoopContainsNestedLoop_WithExcludedNodes() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); TestNode n4 = new TestNode("4"); n1.sendTo(n4); n4.sendTo(n2); n2.sendTo(n3); n2.sendTo(n1); n4.sendTo(n4); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // assert assertEquals(3, nodesInLoop.size()); assertEquals(n1, nodesInLoop.get(0)); assertEquals(n4, nodesInLoop.get(1)); assertEquals(n2, nodesInLoop.get(2)); } public void testTwoParallelStreams_WithOneComplicatedNonLoop_AndOneLoop() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); TestNode n4 = new TestNode("4"); TestNode n5 = new TestNode("5"); TestNode n6 = new TestNode("6"); TestNode n7 = new TestNode("7"); n1.sendTo(n2); n2.sendTo(n3); n2.sendTo(n4); n3.sendTo(n5); n5.sendTo(n3); n4.sendTo(n5); n1.sendTo(n6); n6.sendTo(n7); n7.sendTo(n1); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // assert assertEquals("three TestNodes", 3, nodesInLoop.size()); assertEquals(n1, nodesInLoop.get(0)); assertEquals(n6, nodesInLoop.get(1)); assertEquals(n7, nodesInLoop.get(2)); } public void testSimpleLoop_Pyramid_NoLoops() { // setup TestNode n1 = new TestNode("1"); TestNode n2 = new TestNode("2"); TestNode n3 = new TestNode("3"); TestNode n4 = new TestNode("4"); TestNode n5 = new TestNode("5"); n1.sendTo(n2); n2.sendTo(n3); n1.sendTo(n4); n4.sendTo(n5); n4.sendTo(n2); n5.sendTo(n3); // execute List nodesInLoop = LoopFinder.findSimpleLoop(n1); // assert assertEquals(0, nodesInLoop.size()); } }   class TestNode implements Node { private String name; private List outgoing = new ArrayList(); public TestNode(String name) { this.name = name; } public void sendTo(TestNode n) { outgoing.add(n); } @Override public String toString() { return name; } public int compareTo(Object o) { TestNode n = (TestNode) o; return name.compareTo(n.name); } public List getOutgoing() { return outgoing; } } ```

## Implementation

 ``` package tools.loopfinder; import java.util.List; public interface Node extends Comparable { public abstract List getOutgoing(); } ```

 ```package tools.loopfinder import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Set; public class LoopFinder { public static List findSimpleLoop(Node startingNode) { Set visitedNodes = new HashSet(); List loop = LoopFinder.findSimpleLoop(startingNode, startingNode, visitedNodes, true); if (loop == null) { return new ArrayList(); } return loop; } private static List findSimpleLoop(Node startingNode, Node currentNode, Set visitedNodes, boolean firstCall) { if (LoopFinder.returnedToStartingNode(startingNode, currentNode, firstCall)) { return new LinkedList(); } if (LoopFinder.alreadyVisitedHere(visitedNodes, currentNode)) { return null; } visitedNodes.add(currentNode); List outgoing = currentNode.getOutgoing(); Collections.sort(outgoing); for (Iterator iter = outgoing.iterator(); iter.hasNext();) { Node outgoingNode = (Node) iter.next(); List loop = LoopFinder.findSimpleLoop(startingNode, outgoingNode, visitedNodes, false); if (loop != null) { loop.add(0, currentNode); return loop; } } return null; } private static boolean alreadyVisitedHere(Set visitedNodes, Node currentNode) { return visitedNodes.contains(currentNode); } private static boolean returnedToStartingNode(Node startingNode, Node currentNode, boolean first) { return !first && startingNode.equals(currentNode); } } ```