373 lines
8.3 KiB
Go
373 lines
8.3 KiB
Go
|
package graph
|
||
|
|
|
||
|
|
import (
|
||
|
|
"testing"
|
||
|
|
|
||
|
|
"github.com/stretchr/testify/assert"
|
||
|
|
)
|
||
|
|
|
||
|
|
func TestNewDependencyGraph(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
assert.NotNil(t, graph)
|
||
|
|
assert.Equal(t, 0, len(graph.GetAllTasks()))
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestAddTask(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
task := &Task{ID: "T1", Title: "Task 1"}
|
||
|
|
err := graph.AddTask(task)
|
||
|
|
|
||
|
|
assert.NoError(t, err)
|
||
|
|
retrieved, exists := graph.GetTask("T1")
|
||
|
|
assert.True(t, exists)
|
||
|
|
assert.Equal(t, "T1", retrieved.ID)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestAddTaskNil(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
err := graph.AddTask(nil)
|
||
|
|
assert.Error(t, err)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestAddTaskDuplicate(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
task := &Task{ID: "T1", Title: "Task 1"}
|
||
|
|
graph.AddTask(task)
|
||
|
|
|
||
|
|
err := graph.AddTask(task)
|
||
|
|
assert.Error(t, err)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestAddDependency(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
|
||
|
|
err := graph.AddDependency("T2", "T1")
|
||
|
|
assert.NoError(t, err)
|
||
|
|
|
||
|
|
deps, _ := graph.GetDependencies("T2")
|
||
|
|
assert.Equal(t, 1, len(deps))
|
||
|
|
assert.Equal(t, "T1", deps[0])
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestAddDependencyNotFound(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
|
||
|
|
err := graph.AddDependency("T2", "T1")
|
||
|
|
assert.Error(t, err)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestValidateGraphNoCycles(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
graph.AddTask(&Task{ID: "T3", Title: "Task 3"})
|
||
|
|
|
||
|
|
graph.AddDependency("T2", "T1")
|
||
|
|
graph.AddDependency("T3", "T2")
|
||
|
|
|
||
|
|
err := graph.ValidateGraph()
|
||
|
|
assert.NoError(t, err)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestValidateGraphWithCycle(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
graph.AddTask(&Task{ID: "T3", Title: "Task 3"})
|
||
|
|
|
||
|
|
graph.AddDependency("T2", "T1")
|
||
|
|
graph.AddDependency("T3", "T2")
|
||
|
|
graph.AddDependency("T1", "T3") // Creates cycle
|
||
|
|
|
||
|
|
err := graph.ValidateGraph()
|
||
|
|
assert.Error(t, err)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGetTopologicalOrder(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
graph.AddTask(&Task{ID: "T3", Title: "Task 3"})
|
||
|
|
|
||
|
|
graph.AddDependency("T2", "T1")
|
||
|
|
graph.AddDependency("T3", "T2")
|
||
|
|
|
||
|
|
graph.ValidateGraph()
|
||
|
|
order, err := graph.GetTopologicalOrder()
|
||
|
|
|
||
|
|
assert.NoError(t, err)
|
||
|
|
assert.Equal(t, 3, len(order))
|
||
|
|
assert.Equal(t, "T1", order[0])
|
||
|
|
assert.Equal(t, "T2", order[1])
|
||
|
|
assert.Equal(t, "T3", order[2])
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGetReadyTasks(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
graph.AddTask(&Task{ID: "T3", Title: "Task 3"})
|
||
|
|
|
||
|
|
graph.AddDependency("T2", "T1")
|
||
|
|
graph.AddDependency("T3", "T1")
|
||
|
|
|
||
|
|
ready := graph.GetReadyTasks()
|
||
|
|
assert.Equal(t, 1, len(ready))
|
||
|
|
assert.Equal(t, "T1", ready[0])
|
||
|
|
|
||
|
|
graph.MarkCompleted("T1")
|
||
|
|
ready = graph.GetReadyTasks()
|
||
|
|
assert.Equal(t, 2, len(ready))
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestMarkCompleted(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
err := graph.MarkCompleted("T1")
|
||
|
|
|
||
|
|
assert.NoError(t, err)
|
||
|
|
status, _ := graph.GetTaskStatus("T1")
|
||
|
|
assert.Equal(t, "completed", status)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestMarkFailed(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
err := graph.MarkFailed("T1")
|
||
|
|
|
||
|
|
assert.NoError(t, err)
|
||
|
|
status, _ := graph.GetTaskStatus("T1")
|
||
|
|
assert.Equal(t, "failed", status)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGetDependencies(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
graph.AddTask(&Task{ID: "T3", Title: "Task 3"})
|
||
|
|
|
||
|
|
graph.AddDependency("T3", "T1")
|
||
|
|
graph.AddDependency("T3", "T2")
|
||
|
|
|
||
|
|
deps, _ := graph.GetDependencies("T3")
|
||
|
|
assert.Equal(t, 2, len(deps))
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGetDependents(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
graph.AddTask(&Task{ID: "T3", Title: "Task 3"})
|
||
|
|
|
||
|
|
graph.AddDependency("T2", "T1")
|
||
|
|
graph.AddDependency("T3", "T1")
|
||
|
|
|
||
|
|
dependents, _ := graph.GetDependents("T1")
|
||
|
|
assert.Equal(t, 2, len(dependents))
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestCanExecuteTask(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
|
||
|
|
graph.AddDependency("T2", "T1")
|
||
|
|
|
||
|
|
assert.False(t, graph.CanExecuteTask("T2"))
|
||
|
|
|
||
|
|
graph.MarkCompleted("T1")
|
||
|
|
assert.True(t, graph.CanExecuteTask("T2"))
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGetGraphStats(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2", Title: "Task 2"})
|
||
|
|
|
||
|
|
graph.MarkCompleted("T1")
|
||
|
|
|
||
|
|
stats := graph.GetGraphStats()
|
||
|
|
assert.Equal(t, 2, stats["total_tasks"])
|
||
|
|
assert.Equal(t, 1, stats["completed_tasks"])
|
||
|
|
assert.Equal(t, 1, stats["pending_tasks"])
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestClear(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1", Title: "Task 1"})
|
||
|
|
assert.Equal(t, 1, len(graph.GetAllTasks()))
|
||
|
|
|
||
|
|
graph.Clear()
|
||
|
|
assert.Equal(t, 0, len(graph.GetAllTasks()))
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestMultipleDependencies(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
for i := 1; i <= 5; i++ {
|
||
|
|
id := string(rune(48 + i))
|
||
|
|
graph.AddTask(&Task{ID: "T" + id, Title: "Task " + id})
|
||
|
|
}
|
||
|
|
|
||
|
|
// Chain: T1 -> T2 -> T3 -> T4 -> T5
|
||
|
|
for i := 2; i <= 5; i++ {
|
||
|
|
graph.AddDependency("T"+string(rune(48+i)), "T"+string(rune(48+i-1)))
|
||
|
|
}
|
||
|
|
|
||
|
|
ready := graph.GetReadyTasks()
|
||
|
|
assert.Equal(t, 1, len(ready))
|
||
|
|
assert.Equal(t, "T1", ready[0])
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestDiamondDependency(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
// Diamond: T1 -> (T2, T3) -> T4
|
||
|
|
graph.AddTask(&Task{ID: "T1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2"})
|
||
|
|
graph.AddTask(&Task{ID: "T3"})
|
||
|
|
graph.AddTask(&Task{ID: "T4"})
|
||
|
|
|
||
|
|
graph.AddDependency("T2", "T1")
|
||
|
|
graph.AddDependency("T3", "T1")
|
||
|
|
graph.AddDependency("T4", "T2")
|
||
|
|
graph.AddDependency("T4", "T3")
|
||
|
|
|
||
|
|
graph.ValidateGraph()
|
||
|
|
order, _ := graph.GetTopologicalOrder()
|
||
|
|
|
||
|
|
assert.Equal(t, 4, len(order))
|
||
|
|
assert.Equal(t, "T1", order[0])
|
||
|
|
assert.Equal(t, "T4", order[3])
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGetCriticalPath(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
graph.AddTask(&Task{ID: "T1"})
|
||
|
|
graph.AddTask(&Task{ID: "T2"})
|
||
|
|
graph.AddTask(&Task{ID: "T3"})
|
||
|
|
graph.AddTask(&Task{ID: "T4"})
|
||
|
|
|
||
|
|
graph.AddDependency("T2", "T1")
|
||
|
|
graph.AddDependency("T3", "T2")
|
||
|
|
graph.AddDependency("T4", "T3")
|
||
|
|
|
||
|
|
graph.ValidateGraph()
|
||
|
|
graph.GetTopologicalOrder()
|
||
|
|
|
||
|
|
path := graph.GetCriticalPath()
|
||
|
|
assert.Greater(t, len(path), 0)
|
||
|
|
assert.Equal(t, "T1", path[0])
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestComplexGraph(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
// Create 10 tasks with complex dependencies
|
||
|
|
for i := 1; i <= 10; i++ {
|
||
|
|
id := string(rune(48 + i%10))
|
||
|
|
if i >= 10 {
|
||
|
|
id = "T" + id
|
||
|
|
} else {
|
||
|
|
id = "T0" + id
|
||
|
|
}
|
||
|
|
graph.AddTask(&Task{ID: id})
|
||
|
|
}
|
||
|
|
|
||
|
|
// Add various dependencies
|
||
|
|
graph.AddDependency("T02", "T01")
|
||
|
|
graph.AddDependency("T03", "T01")
|
||
|
|
graph.AddDependency("T04", "T02")
|
||
|
|
graph.AddDependency("T04", "T03")
|
||
|
|
|
||
|
|
graph.ValidateGraph()
|
||
|
|
order, _ := graph.GetTopologicalOrder()
|
||
|
|
assert.Equal(t, 10, len(order))
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestTaskWithMetadata(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
task := &Task{
|
||
|
|
ID: "T1",
|
||
|
|
Title: "Task 1",
|
||
|
|
Metadata: map[string]interface{}{
|
||
|
|
"priority": "high",
|
||
|
|
"owner": "team-a",
|
||
|
|
},
|
||
|
|
}
|
||
|
|
|
||
|
|
graph.AddTask(task)
|
||
|
|
retrieved, _ := graph.GetTask("T1")
|
||
|
|
assert.Equal(t, "high", retrieved.Metadata["priority"])
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGetAllTasks(t *testing.T) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
for i := 1; i <= 5; i++ {
|
||
|
|
id := string(rune(48 + i))
|
||
|
|
graph.AddTask(&Task{ID: "T" + id})
|
||
|
|
}
|
||
|
|
|
||
|
|
all := graph.GetAllTasks()
|
||
|
|
assert.Equal(t, 5, len(all))
|
||
|
|
}
|
||
|
|
|
||
|
|
func BenchmarkAddTask(b *testing.B) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
for i := 0; i < b.N; i++ {
|
||
|
|
id := string(rune(48 + i%100))
|
||
|
|
graph.AddTask(&Task{ID: "T" + id})
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
func BenchmarkAddDependency(b *testing.B) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
for i := 0; i < 1000; i++ {
|
||
|
|
graph.AddTask(&Task{ID: "T" + string(rune(48+i%100))})
|
||
|
|
}
|
||
|
|
|
||
|
|
b.ResetTimer()
|
||
|
|
for i := 0; i < b.N; i++ {
|
||
|
|
from := "T" + string(rune(48+i%100))
|
||
|
|
to := "T" + string(rune(48+(i+1)%100))
|
||
|
|
graph.AddDependency(from, to)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
func BenchmarkGetReadyTasks(b *testing.B) {
|
||
|
|
graph := NewDependencyGraph()
|
||
|
|
|
||
|
|
for i := 1; i <= 100; i++ {
|
||
|
|
id := "T" + string(rune(48+i%100))
|
||
|
|
graph.AddTask(&Task{ID: id})
|
||
|
|
}
|
||
|
|
|
||
|
|
b.ResetTimer()
|
||
|
|
for i := 0; i < b.N; i++ {
|
||
|
|
graph.GetReadyTasks()
|
||
|
|
}
|
||
|
|
}
|