x/container/graph/topo_test.go

package sort

import (
	"testing"
)

// testNode implements the Node interface for testing
type testNode struct {
	value int
	edges []*testNode
}

func (n *testNode) Value() int {
	return n.value
}

func (n *testNode) Adjacencies() []Node[int] {
	result := make([]Node[int], len(n.edges))
	for i, edge := range n.edges {
		result[i] = edge
	}
	return result
}

func TestTopoSort(t *testing.T) {
	t.Run("simple DAG", func(t *testing.T) {
		// Create a simple DAG: 1 -> 2 -> 3
		node3 := &testNode{value: 3}
		node2 := &testNode{value: 2, edges: []*testNode{node3}}
		node1 := &testNode{value: 1, edges: []*testNode{node2}}

		nodes := []Node[int]{node1, node2, node3}
		TopoSort(nodes)

		// After topo sort, nodes should be in reverse topological order
		// The leaf (3) should come first, then 2, then 1
		if nodes[0].Value() != 3 {
			t.Errorf("expected first node to be 3, got %d", nodes[0].Value())
		}
		if nodes[1].Value() != 2 {
			t.Errorf("expected second node to be 2, got %d", nodes[1].Value())
		}
		if nodes[2].Value() != 1 {
			t.Errorf("expected third node to be 1, got %d", nodes[2].Value())
		}
	})

	t.Run("diamond DAG", func(t *testing.T) {
		// Create a diamond DAG:
		//     1
		//    / \
		//   2   3
		//    \ /
		//     4
		node4 := &testNode{value: 4}
		node2 := &testNode{value: 2, edges: []*testNode{node4}}
		node3 := &testNode{value: 3, edges: []*testNode{node4}}
		node1 := &testNode{value: 1, edges: []*testNode{node2, node3}}

		nodes := []Node[int]{node1, node2, node3, node4}
		TopoSort(nodes)

		// Node 4 should come first (leaf), node 1 should come last (root)
		if nodes[0].Value() != 4 {
			t.Errorf("expected first node to be 4, got %d", nodes[0].Value())
		}
		if nodes[3].Value() != 1 {
			t.Errorf("expected last node to be 1, got %d", nodes[3].Value())
		}
	})

	t.Run("single node", func(t *testing.T) {
		node := &testNode{value: 42}
		nodes := []Node[int]{node}
		TopoSort(nodes)

		if nodes[0].Value() != 42 {
			t.Errorf("expected node value 42, got %d", nodes[0].Value())
		}
	})

	t.Run("empty slice", func(t *testing.T) {
		nodes := []Node[int]{}
		TopoSort(nodes)

		if len(nodes) != 0 {
			t.Error("expected empty slice to remain empty")
		}
	})

	t.Run("disconnected nodes", func(t *testing.T) {
		node1 := &testNode{value: 1}
		node2 := &testNode{value: 2}
		node3 := &testNode{value: 3}

		nodes := []Node[int]{node1, node2, node3}
		TopoSort(nodes)

		// All nodes are independent, order might change but all should be present
		if len(nodes) != 3 {
			t.Errorf("expected 3 nodes, got %d", len(nodes))
		}

		values := make(map[int]bool)
		for _, n := range nodes {
			values[n.Value()] = true
		}

		for i := 1; i <= 3; i++ {
			if !values[i] {
				t.Errorf("expected value %d to be present", i)
			}
		}
	})

	t.Run("complex DAG", func(t *testing.T) {
		// More complex graph:
		//     1
		//    / \
		//   2   3
		//   |   |\
		//   4   5 6
		//    \ /
		//     7
		node7 := &testNode{value: 7}
		node4 := &testNode{value: 4, edges: []*testNode{node7}}
		node5 := &testNode{value: 5, edges: []*testNode{node7}}
		node6 := &testNode{value: 6}
		node2 := &testNode{value: 2, edges: []*testNode{node4}}
		node3 := &testNode{value: 3, edges: []*testNode{node5, node6}}
		node1 := &testNode{value: 1, edges: []*testNode{node2, node3}}

		nodes := []Node[int]{node1, node2, node3, node4, node5, node6, node7}
		TopoSort(nodes)

		// Create a map to track the position of each node
		positions := make(map[int]int)
		for i, n := range nodes {
			positions[n.Value()] = i
		}

		// Verify topological ordering constraints (reverse order - leaves first)
		// If there's an edge from A to B, B should come before A in the result
		if positions[2] >= positions[1] {
			t.Error("node 2 should come before node 1 (reverse topo order)")
		}
		if positions[4] >= positions[2] {
			t.Error("node 4 should come before node 2 (reverse topo order)")
		}
		if positions[7] >= positions[4] {
			t.Error("node 7 should come before node 4 (reverse topo order)")
		}
	})
}

func TestRTopoSort(t *testing.T) {
	t.Run("simple DAG", func(t *testing.T) {
		// Create a simple DAG: 1 -> 2 -> 3
		node3 := &testNode{value: 3}
		node2 := &testNode{value: 2, edges: []*testNode{node3}}
		node1 := &testNode{value: 1, edges: []*testNode{node2}}

		nodes := []Node[int]{node1, node2, node3}
		RTopoSort(nodes)

		// After reverse topo sort, nodes should be in topological order
		// The root (1) should come first, then 2, then 3
		if nodes[0].Value() != 1 {
			t.Errorf("expected first node to be 1, got %d", nodes[0].Value())
		}
		if nodes[1].Value() != 2 {
			t.Errorf("expected second node to be 2, got %d", nodes[1].Value())
		}
		if nodes[2].Value() != 3 {
			t.Errorf("expected third node to be 3, got %d", nodes[2].Value())
		}
	})

	t.Run("single node", func(t *testing.T) {
		node := &testNode{value: 42}
		nodes := []Node[int]{node}
		RTopoSort(nodes)

		if nodes[0].Value() != 42 {
			t.Errorf("expected node value 42, got %d", nodes[0].Value())
		}
	})

	t.Run("empty slice", func(t *testing.T) {
		nodes := []Node[int]{}
		RTopoSort(nodes)

		if len(nodes) != 0 {
			t.Error("expected empty slice to remain empty")
		}
	})

	t.Run("two nodes", func(t *testing.T) {
		node2 := &testNode{value: 2}
		node1 := &testNode{value: 1, edges: []*testNode{node2}}

		nodes := []Node[int]{node1, node2}
		RTopoSort(nodes)

		if nodes[0].Value() != 1 {
			t.Errorf("expected first node to be 1, got %d", nodes[0].Value())
		}
		if nodes[1].Value() != 2 {
			t.Errorf("expected second node to be 2, got %d", nodes[1].Value())
		}
	})
}