railpack

1package graph2 3import (4	"testing"5)6 7// TestNode is a simple implementation of Node for testing8type TestNode struct {9	name     string10	parents  []Node11	children []Node12}13 14func NewTestNode(name string) *TestNode {15	return &TestNode{16		name:     name,17		parents:  make([]Node, 0),18		children: make([]Node, 0),19	}20}21 22func (n *TestNode) GetName() string      { return n.name }23func (n *TestNode) GetParents() []Node   { return n.parents }24func (n *TestNode) GetChildren() []Node  { return n.children }25func (n *TestNode) SetParents(p []Node)  { n.parents = p }26func (n *TestNode) SetChildren(c []Node) { n.children = c }27 28func TestGraphBasicOperations(t *testing.T) {29	g := NewGraph()30 31	nodeA := NewTestNode("A")32	nodeB := NewTestNode("B")33 34	g.AddNode(nodeA)35	g.AddNode(nodeB)36 37	if len(g.GetNodes()) != 2 {38		t.Errorf("Expected 2 nodes, got %d", len(g.GetNodes()))39	}40 41	if node, exists := g.GetNode("A"); !exists || node != nodeA {42		t.Error("Failed to retrieve node A")43	}44 45	if _, exists := g.GetNode("C"); exists {46		t.Error("Retrieved non-existent node")47	}48}49 50func TestGraphProcessingOrder(t *testing.T) {51	g := NewGraph()52 53	// Create a simple graph:54	//   A55	//  / \56	// B   C57	//  \ /58	//   D59	nodeA := NewTestNode("A")60	nodeB := NewTestNode("B")61	nodeC := NewTestNode("C")62	nodeD := NewTestNode("D")63 64	g.AddNode(nodeA)65	g.AddNode(nodeB)66	g.AddNode(nodeC)67	g.AddNode(nodeD)68 69	nodeB.SetParents([]Node{nodeA})70	nodeC.SetParents([]Node{nodeA})71	nodeD.SetParents([]Node{nodeB, nodeC})72 73	nodeA.SetChildren([]Node{nodeB, nodeC})74	nodeB.SetChildren([]Node{nodeD})75	nodeC.SetChildren([]Node{nodeD})76 77	order, err := g.ComputeProcessingOrder()78	if err != nil {79		t.Fatalf("Failed to compute processing order: %v", err)80	}81 82	names := make([]string, len(order))83	for i, node := range order {84		names[i] = node.GetName()85	}86	t.Logf("Order: %v", names)87 88	// Verify order (should be A before B and C, and B and C before D)89	if len(order) != 4 {90		t.Fatalf("Expected 4 nodes in order, got %d", len(order))91	}92 93	// A should be first94	if order[0].GetName() != "A" {95		t.Errorf("Expected A to be first, got %s", order[0].GetName())96	}97 98	// D should be last99	if order[3].GetName() != "D" {100		t.Errorf("Expected D to be last, got %s", order[3].GetName())101	}102}103 104func TestGraphCycleDetection(t *testing.T) {105	g := NewGraph()106 107	// Create a cyclic graph:108	// A -> B -> C -> A109	nodeA := NewTestNode("A")110	nodeB := NewTestNode("B")111	nodeC := NewTestNode("C")112 113	g.AddNode(nodeA)114	g.AddNode(nodeB)115	g.AddNode(nodeC)116 117	nodeB.SetParents([]Node{nodeA})118	nodeC.SetParents([]Node{nodeB})119	nodeA.SetParents([]Node{nodeC})120 121	nodeA.SetChildren([]Node{nodeB})122	nodeB.SetChildren([]Node{nodeC})123	nodeC.SetChildren([]Node{nodeA})124 125	// Test cycle detection126	_, err := g.ComputeProcessingOrder()127	if err == nil {128		t.Error("Expected cycle detection error, got nil")129	}130}131 132func TestTransitiveDependencies(t *testing.T) {133	g := NewGraph()134 135	// Create a graph with redundant edges:136	//   A137	//  / \138	// B   C139	//  \ / \140	//   D   E141	nodeA := NewTestNode("A")142	nodeB := NewTestNode("B")143	nodeC := NewTestNode("C")144	nodeD := NewTestNode("D")145	nodeE := NewTestNode("E")146 147	g.AddNode(nodeA)148	g.AddNode(nodeB)149	g.AddNode(nodeC)150	g.AddNode(nodeD)151	g.AddNode(nodeE)152 153	nodeB.SetParents([]Node{nodeA})154	nodeC.SetParents([]Node{nodeA})155	nodeD.SetParents([]Node{nodeA, nodeB, nodeC}) // A is redundant156	nodeE.SetParents([]Node{nodeC})157 158	nodeA.SetChildren([]Node{nodeB, nodeC, nodeD})159	nodeB.SetChildren([]Node{nodeD})160	nodeC.SetChildren([]Node{nodeD, nodeE})161 162	// Remove redundant edges163	g.ComputeTransitiveDependencies()164 165	// Verify D's parents (should only have B and C as parents)166	dParents := nodeD.GetParents()167	if len(dParents) != 2 {168		t.Errorf("Expected 2 parents for D after transitive reduction, got %d", len(dParents))169	}170 171	// Verify A is not a direct parent of D172	for _, parent := range dParents {173		if parent.GetName() == "A" {174			t.Error("Node A should not be a direct parent of D after transitive reduction")175		}176	}177}178