graph_test.go

package graph

import (
	"reflect"
	"testing"
)

func TestBFS(t *testing.T) {
	// 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, 3 -> 4
	g := FromEdges(5, [][2]int{
		{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4},
	})

	got := []int{}
	g.BFS(0, func(v int) { got = append(got, v) })

	// BFS levels: [0], [1,2], [3], [4]
	// 1 and 2 may appear in either order; just check the set of visited
	// vertices and that 0 is first and 4 is last.
	if len(got) != 5 {
		t.Fatalf("BFS visited %d vertices, want 5: %v", len(got), got)
	}
	if got[0] != 0 || got[4] != 4 {
		t.Errorf("BFS order looks wrong: %v", got)
	}
}

func TestDFS(t *testing.T) {
	g := FromEdges(6, [][2]int{
		{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5},
	})

	rec := []int{}
	g.DFSRec(0, func(v int) { rec = append(rec, v) })

	itr := []int{}
	g.DFSIter(0, func(v int) { itr = append(itr, v) })

	if !reflect.DeepEqual(rec, itr) {
		t.Errorf("DFSRec %v vs DFSIter %v should match", rec, itr)
	}
	if len(rec) != 6 {
		t.Errorf("expected to visit 6 vertices, got %d", len(rec))
	}
}

func TestTopoDAG(t *testing.T) {
	// 5 -> 2, 5 -> 0, 4 -> 0, 4 -> 1, 2 -> 3, 3 -> 1
	g := FromEdges(6, [][2]int{
		{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1},
	})
	order, ok := g.TopologicalSort()
	if !ok {
		t.Fatal("expected DAG to be topologically sortable")
	}
	if len(order) != 6 {
		t.Fatalf("topo length = %d", len(order))
	}
	pos := make(map[int]int, len(order))
	for i, v := range order {
		pos[v] = i
	}
	for u := 0; u < g.Vertices(); u++ {
		for _, v := range g.Neighbors(u) {
			if pos[u] >= pos[v] {
				t.Errorf("topological order violated for edge %d->%d", u, v)
			}
		}
	}
}

func TestTopoCycle(t *testing.T) {
	g := FromEdges(3, [][2]int{
		{0, 1}, {1, 2}, {2, 0},
	})
	if _, ok := g.TopologicalSort(); ok {
		t.Error("expected cycle to be detected")
	}
}

func TestDijkstra(t *testing.T) {
	g := NewWeighted(5)
	for _, e := range [][3]int{
		{0, 1, 10},
		{0, 2, 3},
		{1, 3, 2},
		{2, 1, 4},
		{2, 3, 8},
		{2, 4, 2},
		{3, 4, 9},
	} {
		g.AddEdge(e[0], e[1], e[2])
	}

	dist, prev := g.Dijkstra(0)
	want := []int{0, 7, 3, 9, 5}
	if !reflect.DeepEqual(dist, want) {
		t.Errorf("dist = %v, want %v", dist, want)
	}

	path := ReconstructPath(prev, 0, 3)
	if !reflect.DeepEqual(path, []int{0, 2, 1, 3}) {
		t.Errorf("path 0->3 = %v", path)
	}
}

func TestDijkstraUnreachable(t *testing.T) {
	g := NewWeighted(3)
	g.AddEdge(0, 1, 1)
	dist, prev := g.Dijkstra(0)
	if dist[2] != Inf {
		t.Errorf("dist[2] = %d, want Inf", dist[2])
	}
	if p := ReconstructPath(prev, 0, 2); p != nil {
		t.Errorf("path to unreachable = %v, want nil", p)
	}
}