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