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.
	edges []OutEdge

	// Cache the fact that |SetKnownWellFounded| has been invoked.
	knownWellFounded bool
}

func (node *SimpleNode) Name() string {
	return fmt.Sprintf("Node%d", node.value)
}

func (node *SimpleNode) OutEdges() []OutEdge {
	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.Name()))
	}
	node.knownWellFounded = true
}

//Creates a new SimpleNode.
func NewNode(value, numEdges int, isSquare bool) *SimpleNode {
	node := new(SimpleNode)
	node.value = value
	node.edges = make([]OutEdge, 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] = OutEdge{"", 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.Name()] = 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.Name()]; !ok {
			return fmt.Errorf("%s: unexpected: %s, expected: %v, actual: %s", name, n.Name(), 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.Name())
		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 expectedFirstA=%q", i, cycleDescription.String(), c.expectedFirstA)
			}
			if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastA)) {
				t.Fatalf("Case %d: got=%s expectedLastA=%q", i, cycleDescription.String(), c.expectedLastA)
			}
			if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathA)) {
				t.Fatalf("Case %d: got=%s expectedPathA=%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 expectedFirstB=%q", i, cycleDescription.String(), c.expectedFirstB)
				}
				if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastB)) {
					t.Fatalf("Case %dB: got=%s expectedLastB=%q", i, cycleDescription.String(), c.expectedLastB)
				}
				if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathB)) {
					t.Fatalf("Case %dB: got=%s expectedPathB=%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)
				}
			}
		}
	}
}