Mojom frontend: An algorithm for detecting ill-founded nodes in a graph.

mojom/mojom_parser/utils/wellfounded_graphs_test.go

Index: mojom/mojom_parser/utils/wellfounded_graphs_test.go
diff --git a/mojom/mojom_parser/utils/wellfounded_graphs_test.go b/mojom/mojom_parser/utils/wellfounded_graphs_test.go
new file mode 100644
index 0000000000000000000000000000000000000000..958fa9a5882c7f2897b8f85b12c92a98a60508da
--- /dev/null
+++ b/mojom/mojom_parser/utils/wellfounded_graphs_test.go
@@ -0,0 +1,1349 @@
+package utils
+
+import (
+	"bytes"
+	"fmt"
+	"strings"
+	"testing"
+)
+
+////////////////////////////////////////////////////
+// SimpleNode type
+////////////////////////////////////////////////////
+
+// SimpleNode is a simple implementation of the |Node| interface used
+// for testing.
+type SimpleNode struct {
+	// The value of this node
+	value int
+
+	// Is this node a square node?
+	isSquare bool
+
+	// The list of out-edges. The elements will be *SimpleNodes.
+	edges []Node
+
+	// Cache the fact that |SetKnownWellFounded| has been invoked.
+	knownWellFounded bool
+}
+
+func (node *SimpleNode) DebugName() string {
+	return fmt.Sprintf("Node%d", node.value)
+}
+
+func (node *SimpleNode) OutEdges() []Node {
+	return node.edges
+}
+
+func (node *SimpleNode) IsSquare() bool {
+	return node.isSquare
+}
+
+func (node *SimpleNode) KnownWellFounded() bool {
+	return node.knownWellFounded
+}
+
+func (node *SimpleNode) SetKnownWellFounded() {
+	if node.knownWellFounded {
+		panic(fmt.Sprintf("SetKnownWellFounded invoked twice on %s", node.DebugName()))
+	}
+	node.knownWellFounded = true
+}
+
+//Creates a new SimpleNode.
+func NewNode(value, numEdges int, isSquare bool) *SimpleNode {
+	node := new(SimpleNode)
+	node.value = value
+	node.edges = make([]Node, numEdges)
+	node.isSquare = isSquare
+	return node
+}
+
+////////////////////////////////////////////////////
+// Test Utilities
+////////////////////////////////////////////////////
+
+// Builds a test graph containing only circle nodes.
+// The connection matrix should have the following form:
+// connectionMatrix[i][j] = k indicates that there is an edge in the graph
+// from Node i to Node K. k must be less than len(connectionMatrix).
+func buildCircleTestGraph(connectionMatrix [][]int) (nodes []*SimpleNode) {
+	return buildTestGraph(connectionMatrix, nil)
+}
+
+// Builds a test graph. The connection matrix should have the following form:
+// connectionMatrix[i][j] = k indicates that there is an edge in the graph
+// from Node i to Node K. k must be less than len(connectionMatrix).
+// If |squares| is not nil then it must contain the list of indices of the nodes that are squares.
+func buildTestGraph(connectionMatrix [][]int, squares []int) (nodes []*SimpleNode) {
+	squareMap := make(map[int]bool)
+	if squares != nil {
+		for _, n := range squares {
+			squareMap[n] = true
+		}
+	}
+	nodes = make([]*SimpleNode, len(connectionMatrix))
+	for index, connectionList := range connectionMatrix {
+		_, isSquare := squareMap[index]
+		nodes[index] = NewNode(index, len(connectionList), isSquare)
+	}
+	for index, connectionList := range connectionMatrix {
+		for i, target := range connectionList {
+			nodes[index].edges[i] = nodes[target]
+		}
+	}
+	return
+}
+
+// expectedDebugData is used to store an expectation for the value of the |debugData| populated
+// by the ethod |checkWellFounded|. This data captures the result of phase 1 of the algorithm.
+type expectedDebugData struct {
+	initialPendingSet    []string
+	initialFoundationSet []string
+}
+
+func compareDebugData(expected *expectedDebugData, actual *debugData) error {
+	if expected == nil {
+		panic("expected cannot be nil")
+		return nil
+	}
+	if err := compareNodeSlice(expected.initialPendingSet, actual.initialPendingSet, "initialPendingSet"); err != nil {
+		return err
+	}
+	return compareNodeSlice(expected.initialFoundationSet, actual.initialFoundationSet, "initialFoundationSet")
+}
+
+func compareNodeSlice(expected []string, actual []Node, name string) error {
+	expectedMap := make(map[string]bool)
+	actualMap := make(map[string]bool)
+	for _, n := range expected {
+		expectedMap[n] = true
+	}
+	for _, n := range actual {
+		actualMap[n.DebugName()] = true
+	}
+	for _, n := range expected {
+		if _, ok := actualMap[n]; !ok {
+			return fmt.Errorf("%s: missing %s, actual: %s", name, n, NodeSliceToString(actual))
+		}
+	}
+	for _, n := range actual {
+		if _, ok := expectedMap[n.DebugName()]; !ok {
+			return fmt.Errorf("%s: unexpected: %s, expected: %v, actual: %s", name, n.DebugName(), expected, NodeSliceToString(actual))
+		}
+	}
+	return nil
+}
+
+func NodeSliceToString(nodeSlice []Node) string {
+	var buffer bytes.Buffer
+	fmt.Fprintf(&buffer, "[")
+	first := true
+	for _, n := range nodeSlice {
+		if !first {
+			fmt.Fprintf(&buffer, ", ")
+		}
+		fmt.Fprintf(&buffer, "%s", n.DebugName())
+		first = false
+	}
+	fmt.Fprintln(&buffer, "]")
+	return buffer.String()
+}
+
+////////////////////////////////////////////////////
+// Tests
+////////////////////////////////////////////////////
+
+type WellFoundedGraphTestCase struct {
+	// The connection matrix describing the digraph for this case.
+	connectionMatrix [][]int
+
+	// If this is non-nil it should be the list of indices of the square nodes.
+	squares []int
+
+	// The expected result when searching from Node0
+	expectedFirstA, expectedLastA, expectedPathA string
+
+	// The expected result when searching from Node1
+	expectedFirstB, expectedLastB, expectedPathB string
+
+	expectedDebugDataA, expectedDebugDataB expectedDebugData
+}
+
+// TestWellFoundedIsWellFoundedCirclesOnly tests the function |checkWellFounded|
+// on graphs that are well-founded and that contain only circles. For
+// graphs that contain only circles being well-founded is equivalent to
+// being acyclic.
+func TestWellFoundedIsWellFoundedCirclesOnly(t *testing.T) {
+	cases := []WellFoundedGraphTestCase{
+
+		// Case: Single node, no self-loop
+		{
+			connectionMatrix: [][]int{
+				{},
+			},
+		},
+
+		// Case: Linear chain of length 4
+		{
+			connectionMatrix: [][]int{
+				{1}, // 0 -> 1
+				{2}, // 1 -> 2
+				{3}, // 2 -> 3
+				{},  // 3 -> ||
+			},
+		},
+
+		// Case: Diamond
+		//
+		//      0
+		//    1   2
+		//      3
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{3},    // 1
+				{3},    // 2
+				{},     // 3
+			},
+		},
+
+		// Case: Complex, double diamond with a tail
+		//
+		//     0
+		//   1   2
+		// 6   3    4
+		//        5
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{3, 6}, // 1
+				{3, 4}, // 2
+				{5},    // 3
+				{5},    // 4
+				{},     // 5
+				{},     // 6
+			},
+		},
+
+		// Case: 0 and 1 are independent roots
+		//
+		//     0    1
+		//   7   2  |
+		// 6   3    4
+		//        5
+		{
+			connectionMatrix: [][]int{
+				{7, 2}, // 0
+				{4},    // 1
+				{3, 4}, // 2
+				{5},    // 3
+				{5},    // 4
+				{},     // 5
+				{},     // 6
+				{3, 6}, // 7
+			},
+		},
+	}
+
+	for i, c := range cases {
+		graph := buildCircleTestGraph(c.connectionMatrix)
+		dbgData := debugData{}
+		cycleDescription := checkWellFounded(graph[0], &dbgData)
+		if cycleDescription != nil {
+			t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescription)
+		}
+		if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err != nil {
+			t.Fatalf("Case %dA: %s", i, err.Error())
+		}
+		if len(graph) > 1 {
+			dbgData := debugData{}
+			cycleDescription = checkWellFounded(graph[1], &dbgData)
+			if cycleDescription != nil {
+				t.Fatalf("Case %dB: Detected a cycle: %s", i, cycleDescription)
+			}
+			if err := compareDebugData(&c.expectedDebugDataB, &dbgData); err != nil {
+				t.Fatalf("Case %dB: %s", i, err.Error())
+			}
+		}
+	}
+}
+
+// TestWellFoundedNotWellFoundedCirclesOnly tests the function |checkWellFounded|
+// on graphs that are not well-founded and that contain only circles. For
+// graphs that contain only circles being well-founded is equivalent to
+// being acyclic.
+func TestWellFoundedNotWellFoundedCirclesOnly(t *testing.T) {
+
+	cases := []WellFoundedGraphTestCase{
+
+		// Case: Single node with self-loop
+		{
+			connectionMatrix: [][]int{
+				{0},
+			},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node0",
+			expectedPathA:  "Node0",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet: []string{"Node0"},
+			},
+		},
+
+		// Case: Loop of length 4
+		{
+			connectionMatrix: [][]int{
+				{1}, // 0 -> 1
+				{2}, // 1 -> 2
+				{3}, // 2 -> 3
+				{0}, // 3 -> 0
+			},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node3",
+			expectedPathA:  "Node0, Node1, Node2, Node3",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node0",
+			expectedPathB:  "Node1, Node2, Node3, Node0",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+			},
+		},
+
+		// Case: Diamond with a loop-back from bottom to top
+		//
+		//      0  <--
+		//    1   2  |
+		//      3 ---|
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{3},    // 1
+				{3},    // 2
+				{0},    // 3
+			},
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node3",
+			expectedPathA:  "Node0, Node1, Node3",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node0",
+			expectedPathB:  "Node1, Node3, Node0",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+			},
+		},
+
+		// Case: Complex, double diamond with a tail and a bridge and
+		// a loop back to the top
+		//
+		//           0
+		//       1       2   <----
+		//    6      3      4    |
+		//               5 ------|
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{3, 6}, // 1
+				{3, 4}, // 2
+				{5},    // 3
+				{5},    // 4
+				{2},    // 5
+				{},     // 6
+			},
+			expectedFirstA: "Node3",
+			expectedLastA:  "Node2",
+			expectedPathA:  "Node3, Node5, Node2",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5"},
+			},
+
+			expectedFirstB: "Node3",
+			expectedLastB:  "Node2",
+			expectedPathB:  "Node3, Node5, Node2",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet: []string{"Node1", "Node2", "Node3", "Node4", "Node5"},
+			},
+		},
+
+		// Case: More complex
+		//
+		//
+		//             0
+		//        1    2    3  <------
+		//           4    5          |
+		//              6   8  7     |
+		//             11   9 -------|
+		//             12   10
+		{
+			connectionMatrix: [][]int{
+				{1, 2, 3}, // 0
+				{4},       // 1
+				{4, 5},    // 2
+				{5},       // 3
+				{6},       // 4
+				{6, 7, 8}, // 5
+				{11},      // 6
+				{},        // 7
+				{9},       // 8
+				{10, 3},   // 9
+				{},        // 10
+				{12},      // 11
+				{},        // 12
+			},
+			expectedFirstA: "Node5",
+			expectedLastA:  "Node3",
+			expectedPathA:  "Node5, Node8, Node9, Node3",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet: []string{"Node0", "Node2", "Node3", "Node5", "Node8", "Node9"},
+			},
+		},
+
+		// Case: No loop from 0 but loop from 1
+		//
+		//
+		//             1
+		//        0    2    3  <----
+		//          4    5        |
+		//            6  8   7    |
+		//          11     9 ------|
+		//          12     10
+		{
+			connectionMatrix: [][]int{
+				{4},       // 0
+				{0, 2, 3}, // 1
+				{4, 5},    // 2
+				{5},       // 3
+				{6},       // 4
+				{6, 7, 8}, // 5
+				{11},      // 6
+				{},        // 7
+				{9},       // 8
+				{10, 3},   // 9
+				{},        // 10
+				{12},      // 11
+				{},        // 12
+			},
+			expectedFirstB: "Node5",
+			expectedLastB:  "Node3",
+			expectedPathB:  "Node5, Node8, Node9, Node3",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet: []string{"Node1", "Node2", "Node3", "Node5", "Node8", "Node9"},
+			},
+		},
+	}
+
+	for i, c := range cases {
+		graph := buildCircleTestGraph(c.connectionMatrix)
+		// Test from root=Node0
+		dbgData := debugData{}
+		cycleDescription := checkWellFounded(graph[0], &dbgData)
+		if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err != nil {
+			t.Fatalf("Case %dA: %s", i, err.Error())
+		}
+		if len(c.expectedPathA) == 0 {
+			if cycleDescription != nil {
+				t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescription)
+			}
+		} else {
+			if cycleDescription == nil {
+				t.Fatalf("Case %d: Expected a cycle.", i)
+			}
+			if !strings.Contains(cycleDescription.String(), fmt.Sprintf("first:%s", c.expectedFirstA)) {
+				t.Fatalf("Case %d: got=%s expectedFirst=%q", i, cycleDescription.String(), c.expectedFirstA)
+			}
+			if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastA)) {
+				t.Fatalf("Case %d: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastA)
+			}
+			if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathA)) {
+				t.Fatalf("Case %d: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathA)
+			}
+		}
+
+		// Test from root=Node1
+		if len(graph) > 1 {
+			dbgData := debugData{}
+			cycleDescription := checkWellFounded(graph[1], &dbgData)
+			if err := compareDebugData(&c.expectedDebugDataB, &dbgData); err != nil {
+				t.Fatalf("Case %dB: %s", i, err.Error())
+			}
+			if len(c.expectedPathB) == 0 {
+				if cycleDescription != nil {
+					t.Fatalf("Case %dB: Detected a cycle: %s", i, cycleDescription)
+				}
+			} else {
+				if cycleDescription == nil {
+					t.Fatalf("Case %dB: Expected a cycle.", i)
+				}
+				if !strings.Contains(cycleDescription.String(), fmt.Sprintf("first:%s", c.expectedFirstB)) {
+					t.Fatalf("Case %dB: got=%s expectedFirst=%q", i, cycleDescription.String(), c.expectedFirstB)
+				}
+				if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastB)) {
+					t.Fatalf("Case %dB: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastB)
+				}
+				if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathB)) {
+					t.Fatalf("Case %dB: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathB)
+				}
+			}
+		}
+	}
+}
+
+// TestWellFoundedIsWellFounded tests the function |checkWellFounded| on graphs
+// that contain both circles and squares and are well-founded.
+func TestWellFoundedIsWellFounded(t *testing.T) {
+	cases := []WellFoundedGraphTestCase{
+
+		// Case: Single square node, no self-loop
+		{
+			connectionMatrix: [][]int{
+				{},
+			},
+			squares: []int{0},
+		},
+
+		// Case: Loop through right branch but not through left branch.
+		//
+		//      [0] <--|
+		//    1     2--|
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{},     // 1
+				{0},    // 2
+			},
+			squares: []int{0},
+		},
+
+		// Case: Loop through left branch but not through rigt branch.
+		//
+		//      [0] <--|
+		//    2     1--|
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{0},    // 1
+				{},     // 2
+			},
+			squares: []int{0},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node1"},
+				initialFoundationSet: []string{"Node0"},
+			},
+		},
+
+		// Case: Loop through right branch below the root
+		//
+		//       0 <---|
+		//      [1]    |
+		//    2     3--|
+		{
+			connectionMatrix: [][]int{
+				{1},    // 0
+				{2, 3}, // 1
+				{},     // 2
+				{0},    // 3
+			},
+			squares: []int{1},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node3"},
+				initialFoundationSet: []string{"Node0"},
+			},
+		},
+
+		// Case: Loop through left branch below the root
+		//
+		//       0 <---|
+		//      [1]    |
+		//    3     2--|
+		{
+			connectionMatrix: [][]int{
+				{1},    // 0
+				{2, 3}, // 1
+				{0},    // 2
+				{},     // 3
+			},
+			squares: []int{1},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node2"},
+				initialFoundationSet: []string{"Node0"},
+			},
+		},
+
+		// Case: We know 0 is well-founded before we see the loop from 4 to 0
+		//
+		//
+		//   1  <-- [0] <--|
+		//          [2]    |
+		//        3     4--|
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{},     // 1
+				{3, 4}, // 2
+				{},     // 3
+				{0},    // 4
+			},
+			squares: []int{0, 2},
+		},
+
+		// Case: Well-founded becuase of 8
+		//         0
+		//         1
+		//         2 <--
+		//         3   |
+		//  8 <-- [4]  |
+		//         5   |
+		//         6---|
+		//         7
+		{
+			connectionMatrix: [][]int{
+				{1},    // 0
+				{2},    // 1
+				{3},    // 2
+				{4},    // 3
+				{5, 8}, // 4
+				{6},    // 5
+				{2, 7}, // 6
+				{},     // 7
+				{},     // 8
+			},
+			squares: []int{4},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node5", "Node6"},
+				initialFoundationSet: []string{"Node2"},
+			},
+		},
+
+		// Case: Double loops through right branches
+		//
+		//       0 <---|
+		//      [1]<---|-----
+		//    2     3--|    |
+		//         [4]      |
+		//      5   6   7 --|
+		//      8   9   10
+		{
+			connectionMatrix: [][]int{
+				{1},       // 0
+				{2, 3},    // 1
+				{},        // 2
+				{0, 4},    // 3
+				{5, 6, 7}, // 4
+				{8},       // 5
+				{9},       // 6
+				{1, 10},   // 7
+				{},        // 8
+				{},        // 9
+				{},        // 10
+			},
+			squares: []int{1, 4},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node3"},
+				initialFoundationSet: []string{"Node0"},
+			},
+		},
+
+		// Case: Double loops through left branches
+		//
+		//       0 <---|
+		//      [1]<---|-----
+		//    3     2--|    |
+		//         [4]      |
+		//      7   6   5 --|
+		//      8   9   10
+		{
+			connectionMatrix: [][]int{
+				{1},       // 0
+				{2, 3},    // 1
+				{0, 4},    // 2
+				{},        // 3
+				{5, 6, 7}, // 4
+				{1, 10},   // 5
+				{9},       // 6
+				{8},       // 7
+				{},        // 8
+				{},        // 9
+				{},        // 10
+			},
+			squares: []int{1, 4},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node2", "Node5"},
+				initialFoundationSet: []string{"Node0", "Node1"},
+			},
+		},
+
+		// Case: Crossing up and down on right
+		//
+		//         0 -----|
+		//         1      |
+		//        [2] <---|-----
+		//      3     4 <-|    |
+		//            5        |
+		//            6        |
+		//            7 -------|
+		//
+		{
+			connectionMatrix: [][]int{
+				{1, 4}, // 0
+				{2},    // 1
+				{3, 4}, // 2
+				{},     // 3
+				{5},    // 4
+				{6},    // 5
+				{7},    // 6
+				{2},    // 7
+			},
+			squares: []int{2},
+		},
+
+		// Case: Crossing up and down on left
+		//
+		//         0 -----|
+		//         1      |
+		//        [2] <---|-----
+		//      4     3 <-|    |
+		//            5        |
+		//            6        |
+		//            7 -------|
+		//
+		{
+			connectionMatrix: [][]int{
+				{1, 3}, // 0
+				{2},    // 1
+				{3, 4}, // 2
+				{5},    // 3
+				{},     // 4
+				{6},    // 5
+				{7},    // 6
+				{2},    // 7
+			},
+			squares: []int{2},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node3", "Node5", "Node6", "Node7"},
+				initialFoundationSet: []string{"Node2"},
+			},
+		},
+
+		// Case:
+		//
+		//            [0]  <------|
+		//   |---->1        2     |
+		//   |<---[3]-------------|
+		//
+		//
+		//
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{3},    // 1
+				{},     // 2
+				{0, 1}, // 3
+			},
+			squares: []int{0, 3},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node1", "Node3"},
+				initialFoundationSet: []string{"Node0"},
+			},
+		},
+
+		// Case:
+		//
+		//  |-----> 0  <------\
+		//  |   [1] --> [2]---|--> 4
+		//  |    ^      \
+		//  |----|-------3
+		//
+		//
+		{
+			connectionMatrix: [][]int{
+				{1, 2},    // 0
+				{2},       // 1
+				{0, 3, 4}, // 2
+				{0, 1},    // 3
+				{},        // 4
+			},
+			squares: []int{1, 2},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node3"},
+				initialFoundationSet: []string{"Node0", "Node1"},
+			},
+		},
+
+		// Case:
+		//
+		//     |-->[1]
+		//    [2]< -|    0
+		//     ^    |
+		//     |----|
+		//
+		//
+		{
+			connectionMatrix: [][]int{
+				{},     // 0
+				{0, 2}, // 1
+				{1, 2}, // 2
+			},
+			squares: []int{1, 2},
+		},
+
+		// Case: Double loops through left branches
+		//
+		//       0 <---|
+		//      [1]<---|-----
+		//    3     2--|    |
+		//         [4]      |
+		//      7   6   5 --|
+		//      8   9   10
+		{
+			connectionMatrix: [][]int{
+				{1},       // 0
+				{2, 3},    // 1
+				{0, 4},    // 2
+				{},        // 3
+				{5, 6, 7}, // 4
+				{1, 10},   // 5
+				{9},       // 6
+				{8},       // 7
+				{},        // 8
+				{},        // 9
+				{},        // 10
+			},
+			squares: []int{1, 4},
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node2", "Node5"},
+				initialFoundationSet: []string{"Node0", "Node1"},
+			},
+		},
+	}
+
+	for i, c := range cases {
+		graph := buildTestGraph(c.connectionMatrix, c.squares)
+		dbgData := debugData{}
+		cycleDescription := checkWellFounded(graph[0], &dbgData)
+		if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err != nil {
+			t.Fatalf("Case %dA: %s", i, err.Error())
+		}
+		if cycleDescription != nil {
+			t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescription)
+		}
+		if len(graph) > 1 {
+			dbgData := debugData{}
+			cycleDescription := checkWellFounded(graph[1], &dbgData)
+			if err := compareDebugData(&c.expectedDebugDataB, &dbgData); err != nil {
+				t.Fatalf("Case %dB: %s", i, err.Error())
+			}
+			if cycleDescription != nil {
+				t.Fatalf("Case %dB: Detected a cycle: %s", i, cycleDescription)
+			}
+		}
+	}
+}
+
+// TestWellFoundedNotWellFounded tests the function |checkWellFounded| on graphs
+// that contain both circles and squares and are not well-founded.
+func TestWellFoundedNotWellFounded(t *testing.T) {
+
+	cases := []WellFoundedGraphTestCase{
+
+		// Case: Single square node with self-loop
+		{
+			connectionMatrix: [][]int{
+				{0},
+			},
+
+			squares: []int{0},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node0",
+			expectedPathA:  "Node0",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Loop of length 4 with 1 square at the root
+		{
+			connectionMatrix: [][]int{
+				{1}, // 0 -> 1
+				{2}, // 1 -> 2
+				{3}, // 2 -> 3
+				{0}, // 3 -> 0
+			},
+
+			squares: []int{0},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node3",
+			expectedPathA:  "Node0, Node1, Node2, Node3",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node0",
+			expectedPathB:  "Node1, Node2, Node3, Node0",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Loop of length 4 with 2 squares
+		{
+			connectionMatrix: [][]int{
+				{1}, // 0 -> 1
+				{2}, // 1 -> 2
+				{3}, // 2 -> 3
+				{0}, // 3 -> 0
+			},
+
+			squares: []int{1, 2},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node3",
+			expectedPathA:  "Node0, Node1, Node2, Node3",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node0",
+			expectedPathB:  "Node1, Node2, Node3, Node0",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Loop through left and right branches
+		//
+		//     |--> [0] <--|
+		//     |--1     2--|
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{0},    // 1
+				{0},    // 2
+			},
+			squares: []int{0},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node1",
+			expectedPathA:  "Node0, Node1",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node0",
+			expectedPathB:  "Node1, Node0",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Loop through left and right branches below the root
+		//
+		//  |----> 0 <---|
+		//  |     [1]    |
+		//  |-- 2     3--|
+		{
+			connectionMatrix: [][]int{
+				{1},    // 0
+				{2, 3}, // 1
+				{0},    // 2
+				{0},    // 3
+			},
+			squares: []int{1},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node2",
+			expectedPathA:  "Node0, Node1, Node2",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node0",
+			expectedPathB:  "Node1, Node2, Node0",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Self loop at one node below a square
+		//
+		//      [0]
+		//    1     2--|
+		//          ^  |
+		//          |  |
+		//          ----
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{},     // 1
+				{2},    // 2
+			},
+			squares: []int{0},
+
+			expectedFirstA: "Node2",
+			expectedLastA:  "Node2",
+			expectedPathA:  "Node2",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node2"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Self loop at one node below a square, other side
+		//
+		//      [0]
+		//    2     1--|
+		//          ^  |
+		//          |  |
+		//          ----
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{1},    // 1
+				{},     // 2
+			},
+			squares: []int{0},
+
+			expectedFirstA: "Node1",
+			expectedLastA:  "Node1",
+			expectedPathA:  "Node1",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node1"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node1",
+			expectedPathB:  "Node1",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node1"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Self loop off of one branch of a square.
+		//
+		//             [0]
+		//          1       2
+		//          3 -|
+		//          ^  |
+		//          |---
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{3},    // 1
+				{},     // 2
+				{3},    // 3
+			},
+			squares: []int{0},
+
+			expectedFirstA: "Node3",
+			expectedLastA:  "Node3",
+			expectedPathA:  "Node3",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node1", "Node3"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node3",
+			expectedLastB:  "Node3",
+			expectedPathB:  "Node3",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node1", "Node3"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Hard loop off of one branch of a square.
+		//
+		//             [0]
+		//      --> 1       2
+		//      |   3
+		//      |---4
+		{
+			connectionMatrix: [][]int{
+				{1, 2}, // 0
+				{3},    // 1
+				{},     // 2
+				{4},    // 3
+				{1},    // 4
+			},
+			squares: []int{0},
+
+			expectedFirstA: "Node1",
+			expectedLastA:  "Node4",
+			expectedPathA:  "Node1, Node3, Node4",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node1", "Node3", "Node4"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node4",
+			expectedPathB:  "Node1, Node3, Node4",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node1", "Node3", "Node4"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Graph below 0 is well-founded and 1 is well-founded but not the graph below 1.
+		//
+		//         [1]
+		//     2 -|    0
+		//     ^  |
+		//     |--|
+		//
+		//
+		{
+			connectionMatrix: [][]int{
+				{},     // 0
+				{0, 2}, // 1
+				{2},    // 2
+			},
+			squares: []int{1},
+
+			expectedFirstB: "Node2",
+			expectedLastB:  "Node2",
+			expectedPathB:  "Node2",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node2"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Different loops through both branches sharing nodes.
+		//
+		//        0 <------|
+		//        1        |
+		//       [2]       |
+		//    3        4   |
+		//     \       5   |
+		//      \----> 6   |
+		//             7 --|
+		{
+			connectionMatrix: [][]int{
+				{1},    // 0
+				{2},    // 1
+				{3, 4}, // 2
+				{6},    // 3
+				{5},    // 4
+				{6},    // 5
+				{7},    // 6
+				{0},    // 7
+			},
+			squares: []int{2},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node7",
+			expectedPathA:  "Node0, Node1, Node2, Node3, Node6, Node7",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6", "Node7"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node0",
+			expectedPathB:  "Node1, Node2, Node3, Node6, Node7, Node0",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6", "Node7"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Different loops through both branches sharing nodes--switch sides.
+		//
+		//        0 <------|
+		//        1        |
+		//       [2]       |
+		//    4        3   |
+		//     \       5   |
+		//      \----> 6   |
+		//             7 --|
+		{
+			connectionMatrix: [][]int{
+				{1},    // 0
+				{2},    // 1
+				{3, 4}, // 2
+				{5},    // 3
+				{6},    // 4
+				{6},    // 5
+				{7},    // 6
+				{0},    // 7
+			},
+			squares: []int{2},
+
+			expectedFirstA: "Node0",
+			expectedLastA:  "Node7",
+			expectedPathA:  "Node0, Node1, Node2, Node3, Node5, Node6, Node7",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6", "Node7"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node1",
+			expectedLastB:  "Node0",
+			expectedPathB:  "Node1, Node2, Node3, Node5, Node6, Node7, Node0",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6", "Node7"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Not Well-founded becuase of 8 becuase 4 is a circle
+		//         0
+		//         1
+		//         2 <--
+		//         3   |
+		//  8 <--  4   |
+		//         5   |
+		//         6---|
+		//         7
+		{
+			connectionMatrix: [][]int{
+				{1},    // 0
+				{2},    // 1
+				{3},    // 2
+				{4},    // 3
+				{5, 8}, // 4
+				{6},    // 5
+				{2, 7}, // 6
+				{},     // 7
+				{},     // 8
+			},
+			squares: []int{},
+
+			expectedFirstA: "Node2",
+			expectedLastA:  "Node6",
+			expectedPathA:  "Node2, Node3, Node4, Node5, Node6",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node2",
+			expectedLastB:  "Node6",
+			expectedPathB:  "Node2, Node3, Node4, Node5, Node6",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node1", "Node2", "Node3", "Node4", "Node5", "Node6"},
+				initialFoundationSet: []string{},
+			},
+		},
+
+		// Case: Not Well-founded becuase of 8 becuase there is no 8
+		//         0
+		//         1
+		//         2 <--
+		//         3   |
+		//       [4]   |
+		//         5   |
+		//         6---|
+		//         7
+		{
+			connectionMatrix: [][]int{
+				{1},    // 0
+				{2},    // 1
+				{3},    // 2
+				{4},    // 3
+				{5},    // 4
+				{6},    // 5
+				{2, 7}, // 6
+				{},     // 7
+			},
+			squares: []int{4},
+
+			expectedFirstA: "Node2",
+			expectedLastA:  "Node6",
+			expectedPathA:  "Node2, Node3, Node4, Node5, Node6",
+			expectedDebugDataA: expectedDebugData{
+				initialPendingSet:    []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6"},
+				initialFoundationSet: []string{},
+			},
+
+			expectedFirstB: "Node2",
+			expectedLastB:  "Node6",
+			expectedPathB:  "Node2, Node3, Node4, Node5, Node6",
+			expectedDebugDataB: expectedDebugData{
+				initialPendingSet:    []string{"Node1", "Node2", "Node3", "Node4", "Node5", "Node6"},
+				initialFoundationSet: []string{},
+			},
+		},
+	}
+
+	for i, c := range cases {
+		graph := buildTestGraph(c.connectionMatrix, c.squares)
+		// Test from root=Node0
+		dbgData := debugData{}
+		cycleDescription := checkWellFounded(graph[0], &dbgData)
+		if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err != nil {
+			t.Fatalf("Case %dA: %s", i, err.Error())
+		}
+		if len(c.expectedPathA) == 0 {
+			if cycleDescription != nil {
+				t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescription)
+			}
+		} else {
+			if cycleDescription == nil {
+				t.Fatalf("Case %d: Expected a cycle.", i)
+			}
+			if !strings.Contains(cycleDescription.String(), fmt.Sprintf("first:%s", c.expectedFirstA)) {
+				t.Fatalf("Case %d: got=%s expectedFirst=%q", i, cycleDescription.String(), c.expectedFirstA)
+			}
+			if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastA)) {
+				t.Fatalf("Case %d: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastA)
+			}
+			if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathA)) {
+				t.Fatalf("Case %d: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathA)
+			}
+		}
+
+		// Test from root=Node1
+		if len(graph) > 1 {
+			dbgData := debugData{}
+			cycleDescription := checkWellFounded(graph[1], &dbgData)
+			if err := compareDebugData(&c.expectedDebugDataB, &dbgData); err != nil {
+				t.Fatalf("Case %dB: %s", i, err.Error())
+			}
+			if len(c.expectedPathB) == 0 {
+				if cycleDescription != nil {
+					t.Fatalf("Case %dB: Detected a cycle: %s", i, cycleDescription)
+				}
+			} else {
+				if cycleDescription == nil {
+					t.Fatalf("Case %dB: Expected a cycle.", i)
+				}
+				if !strings.Contains(cycleDescription.String(), fmt.Sprintf("first:%s", c.expectedFirstB)) {
+					t.Fatalf("Case %dB: got=%s expectedFirst=%q", i, cycleDescription.String(), c.expectedFirstB)
+				}
+				if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastB)) {
+					t.Fatalf("Case %dB: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastB)
+				}
+				if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathB)) {
+					t.Fatalf("Case %dB: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathB)
+				}
+			}
+		}
+	}
+}