Graphs: BFS & DFS — Programuoki

Code

The harness and the tests

Three files: the harness, the tests, and two new commands.

command	what it does
`algo net`	builds the network and compares BFS with DFS over every reachable destination
`algo dense`	adjacency list against matrix: memory and the cost of a scan

graphbench.go also carries buildTrails — the generator that makes reading trails rather than random pairs. That matters: a random-pair graph has a completely different shape and this lesson's comparison with transit would not hold.

The tests

test	what it requires
`TestBFSFindsTheShortestPath`	for every reachable node, BFS's path equals the true distance
`TestDFSFindsAPathButNotTheShortest`	DFS's path is real, never shorter, and sometimes longer
`TestBothSearchesAgreeOnReachability`	all three agree on WHAT is reachable
`TestTheTwoDFSVersionsDisagreeOnPaths`	the two DFS versions find different paths
`TestComponentsPartitionTheGraph`	the components cover every node
`TestMatrixAgreesWithList`	both representations describe the same graph

The first checks against independently computed distances — a separate bfsDistances function in the test file, not against your own BFS's answer. Checking an algorithm with itself is checking nothing.

The second and fourth again demand that something is not the case — a shape that has been familiar since lesson 7. "Fix" DFS so that it returns shortest paths and you have written BFS with extra steps, and the test says exactly that:

DFS found the shortest path every time — that is BFS, not DFS

graphbench.go CREATE

Create this file in ./

package main

import (
	"flag"
	"fmt"
	"math/rand"
	"time"

	"algo/metrics"
)

// buildTrails makes the "readers also borrowed" graph, and it is shaped
// deliberately: TRAILS, not random pairs.
//
// A reader borrows a run of books one after another, so each trail is a chain.
// Trails cross where two readers happen to pick the same book, and those
// crossings are the only junctions. That is the same shape as a transit network:
// long chains, few junctions — which is why the comparison with `transit` in step
// 8 is a comparison and not an analogy.
func buildTrails(n, trails, length int, seed int64) *Graph {
	rng := rand.New(rand.NewSource(seed))
	g := NewGraph(n)
	for t := 0; t < trails; t++ {
		v := int32(rng.Intn(n))
		for i := 0; i < length; i++ {
			w := int32(rng.Intn(n))
			g.AddEdge(v, w)
			v = w
		}
	}
	return g
}

func cmdNet(args []string) error {
	fs := flag.NewFlagSet("net", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	trails := fs.Int("trails", 0, "how many borrowing trails (default n/16)")
	length := fs.Int("length", 12, "books per trail")
	seed := fs.Int64("seed", 1, "trail seed")
	from := fs.Int("from", 0, "start node")
	to := fs.Int("to", -1, "end node (default: the farthest node BFS can reach)")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}
	n := len(items)
	if *trails == 0 {
		*trails = n / 16
	}
	g := buildTrails(n, *trails, *length, *seed)

	mean, median, max := g.Degrees()
	var cc metrics.Counter
	comps, largest := g.Components(&cc)
	fmt.Printf("nodes %d, edges %d\n", g.Nodes(), g.Edges())
	fmt.Printf("  degree: mean %.2f, median %d, max %d\n", mean, median, max)
	fmt.Printf("  components %d, largest %d (%.1f%% of the library)\n\n",
		comps, largest, 100*float64(largest)/float64(n))

	dst := int32(*to)
	if *to < 0 {
		dst = worstPair(g, int32(*from))
	}

	var bc, dc, rc metrics.Counter
	t0 := time.Now()
	bfsPath, okB := BFS(g, int32(*from), dst, &bc)
	bfsTime := time.Since(t0)
	t0 = time.Now()
	dfsPath, okD := DFS(g, int32(*from), dst, &dc)
	dfsTime := time.Since(t0)
	recPath, okR := DFSRecursive(g, int32(*from), dst, &rc)

	if !okB || !okD || !okR {
		fmt.Printf("  no path from %d to %d\n", *from, dst)
		return nil
	}
	fmt.Printf("  path from %d to %d\n\n", *from, dst)
	fmt.Printf("  %-22s %8s %14s %12s\n", "", "hops", "edges looked at", "time")
	fmt.Printf("  %-22s %8d %14d %12s\n", "BFS (queue)", len(bfsPath)-1, bc.N(), bfsTime.Round(time.Microsecond))
	fmt.Printf("  %-22s %8d %14d %12s\n", "DFS (stack)", len(dfsPath)-1, dc.N(), dfsTime.Round(time.Microsecond))
	fmt.Printf("  %-22s %8d %14d %12s\n", "DFS (recursive)", len(recPath)-1, rc.N(), "-")
	fmt.Printf("\n  DFS path is %.1fx longer than the shortest\n",
		float64(len(dfsPath)-1)/float64(len(bfsPath)-1))
	fmt.Printf("  the two DFS versions agree: %v\n", samePath(dfsPath, recPath))

	// One pair is an anecdote. Do every reachable destination.
	var equal, longer, worstRatio, sumRatio, pairs = 0, 0, 0.0, 0.0, 0
	worstB, worstD := 0, 0
	for t := 0; t < n; t++ {
		if int32(t) == int32(*from) {
			continue
		}
		var b, d metrics.Counter
		bp, ok1 := BFS(g, int32(*from), int32(t), &b)
		dp, ok2 := DFS(g, int32(*from), int32(t), &d)
		if !ok1 || !ok2 {
			continue
		}
		pairs++
		bh, dh := len(bp)-1, len(dp)-1
		if dh == bh {
			equal++
		} else {
			longer++
		}
		r := float64(dh) / float64(bh)
		sumRatio += r
		if r > worstRatio {
			worstRatio, worstB, worstD = r, bh, dh
		}
	}
	fmt.Printf("\n  every reachable destination from %d (%d of them):\n", *from, pairs)
	fmt.Printf("    DFS found the shortest path   %d (%.1f%%)\n", equal, 100*float64(equal)/float64(pairs))
	fmt.Printf("    DFS found a longer path       %d (%.1f%%)\n", longer, 100*float64(longer)/float64(pairs))
	fmt.Printf("    mean DFS/BFS hop ratio        %.2fx\n", sumRatio/float64(pairs))
	fmt.Printf("    worst case                    %d hops vs %d (%.1fx)\n", worstD, worstB, worstRatio)
	return nil
}

func samePath(a, b []int32) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

// worstPair returns the destination where DFS's path is longest relative to
// BFS's — the clearest single illustration, and the sweep below the table says
// how typical it is.
func worstPair(g *Graph, from int32) int32 {
	best, bestRatio := from, 0.0
	for t := 0; t < g.Nodes(); t++ {
		if int32(t) == from {
			continue
		}
		var b, d metrics.Counter
		bp, ok1 := BFS(g, from, int32(t), &b)
		dp, ok2 := DFS(g, from, int32(t), &d)
		if !ok1 || !ok2 {
			continue
		}
		if r := float64(len(dp)-1) / float64(len(bp)-1); r > bestRatio {
			best, bestRatio = int32(t), r
		}
	}
	return best
}

// cmdDense measures the two representations against each other.
func cmdDense(args []string) error {
	fs := flag.NewFlagSet("dense", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	trails := fs.Int("trails", 0, "how many trails (default n/16)")
	length := fs.Int("length", 12, "books per trail")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}
	n := len(items)
	if *trails == 0 {
		*trails = n / 16
	}
	g := buildTrails(n, *trails, *length, 1)

	// adjacency list: one 24-byte slice header per node, plus 4 bytes per
	// directed edge (each undirected edge is stored twice).
	const header = 24
	listBytes := n*header + 2*g.Edges()*4

	m := NewAdjMatrix(n)
	for v := 0; v < n; v++ {
		for _, w := range g.adj[int32(v)] {
			m.Set(int32(v), w)
		}
	}

	fmt.Printf("nodes %d, edges %d\n\n", n, g.Edges())
	fmt.Printf("  %-22s %14s %16s %14s\n", "", "bytes", "cells", "used")
	fmt.Printf("  %-22s %14d %16s %14s\n", "adjacency list", listBytes, "-", "-")
	fmt.Printf("  %-22s %14d %16d %13.4f%%\n", "adjacency matrix", m.Bytes(), m.Cells(),
		100*float64(2*g.Edges())/float64(m.Cells()))
	fmt.Printf("\n  the matrix is %.1fx larger\n", float64(m.Bytes())/float64(listBytes))

	// And what each costs to answer the two questions a search asks.
	var lc, mc metrics.Counter
	t0 := time.Now()
	for v := 0; v < n; v++ {
		for range g.adj[int32(v)] {
			lc.Hit()
		}
	}
	listScan := time.Since(t0)
	t0 = time.Now()
	for v := 0; v < n; v++ {
		for w := 0; w < n; w++ {
			mc.Hit()
			_ = m.Has(int32(v), int32(w))
		}
	}
	matrixScan := time.Since(t0)
	fmt.Printf("\n  visiting every neighbour of every node:\n")
	fmt.Printf("  %-22s %14d %12s\n", "adjacency list", lc.N(), listScan.Round(time.Microsecond))
	fmt.Printf("  %-22s %14d %12s\n", "adjacency matrix", mc.N(), matrixScan.Round(time.Microsecond))
	return nil
}

graph_test.go CREATE

Create this file in ./

package main

import (
	"testing"

	"algo/metrics"
)

// isPath checks that a returned path is real: it starts and ends where it should
// and every consecutive pair is an actual edge. A wrong search usually returns
// something that LOOKS like a path.
func isPath(g *Graph, p []int32, from, to int32) bool {
	if len(p) == 0 || p[0] != from || p[len(p)-1] != to {
		return false
	}
	for i := 1; i < len(p); i++ {
		found := false
		for _, w := range g.Neighbors(p[i-1]) {
			if w == p[i] {
				found = true
				break
			}
		}
		if !found {
			return false
		}
	}
	return true
}

// bfsDistances is the reference: the true hop distance to every node.
func bfsDistances(g *Graph, from int32) []int {
	d := make([]int, g.Nodes())
	for i := range d {
		d[i] = -1
	}
	d[from] = 0
	queue := []int32{from}
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]
		for _, w := range g.Neighbors(v) {
			if d[w] < 0 {
				d[w] = d[v] + 1
				queue = append(queue, w)
			}
		}
	}
	return d
}

func testGraph() *Graph { return buildTrails(1000, 62, 12, 1) }

// BFS MUST RETURN THE FEWEST HOPS. Checked against an independent distance
// computation, for every reachable destination.
func TestBFSFindsTheShortestPath(t *testing.T) {
	g := testGraph()
	const from = int32(0)
	dist := bfsDistances(g, from)
	var c metrics.Counter
	checked := 0
	for to := int32(1); int(to) < g.Nodes(); to++ {
		p, ok := BFS(g, from, to, &c)
		if dist[to] < 0 {
			if ok {
				t.Fatalf("BFS reached %d, which is not reachable", to)
			}
			continue
		}
		if !ok {
			t.Fatalf("BFS missed %d, which is %d hops away", to, dist[to])
		}
		if !isPath(g, p, from, to) {
			t.Fatalf("BFS returned something that is not a path to %d: %v", to, p)
		}
		if len(p)-1 != dist[to] {
			t.Fatalf("BFS to %d took %d hops, shortest is %d", to, len(p)-1, dist[to])
		}
		checked++
	}
	if checked < 100 {
		t.Fatalf("only %d destinations checked — the test graph is too small", checked)
	}
	t.Logf("%d reachable destinations, every one at the shortest hop count", checked)
}

// DFS MUST RETURN A REAL PATH — and it is NOT required to be the shortest.
//
// The second half is asserted so the demonstration survives: if someone
// "improves" DFS into something that returns shortest paths, they have written
// BFS with extra steps and this test says so.
func TestDFSFindsAPathButNotTheShortest(t *testing.T) {
	g := testGraph()
	const from = int32(0)
	dist := bfsDistances(g, from)
	var c metrics.Counter
	longer, equal, worst := 0, 0, 0
	for to := int32(1); int(to) < g.Nodes(); to++ {
		if dist[to] < 0 {
			continue
		}
		p, ok := DFS(g, from, to, &c)
		if !ok {
			t.Fatalf("DFS missed %d, which BFS reaches in %d hops", to, dist[to])
		}
		if !isPath(g, p, from, to) {
			t.Fatalf("DFS returned something that is not a path to %d", to)
		}
		if len(p)-1 < dist[to] {
			t.Fatalf("DFS to %d took %d hops — shorter than the shortest, which is impossible", to, len(p)-1)
		}
		if len(p)-1 == dist[to] {
			equal++
		} else {
			longer++
			if r := (len(p) - 1) / dist[to]; r > worst {
				worst = r
			}
		}
	}
	if longer == 0 {
		t.Fatal("DFS found the shortest path every time — that is BFS, not DFS")
	}
	t.Logf("DFS: shortest %d, longer %d, worst ratio %dx", equal, longer, worst)
}

// Both searches must agree on WHAT IS REACHABLE, however differently they get
// there. Reachability is a property of the graph; the path is not.
func TestBothSearchesAgreeOnReachability(t *testing.T) {
	g := testGraph()
	const from = int32(0)
	var bc, dc, rc metrics.Counter
	for to := int32(1); int(to) < g.Nodes(); to++ {
		_, b := BFS(g, from, to, &bc)
		_, d := DFS(g, from, to, &dc)
		_, r := DFSRecursive(g, from, to, &rc)
		if b != d || b != r {
			t.Fatalf("node %d: BFS %v, DFS %v, recursive DFS %v", to, b, d, r)
		}
	}
}

// LESSON 5 SAID RECURSION AND AN EXPLICIT STACK ARE THE SAME ALGORITHM, and they
// are. But "the same algorithm" does not mean "the same answer": the two
// versions visit a node's neighbours in OPPOSITE orders, so they walk different
// paths to the same places.
//
// Asserted, because it is a genuine property rather than a bug — and drill 2 is
// about making them agree.
func TestTheTwoDFSVersionsDisagreeOnPaths(t *testing.T) {
	g := testGraph()
	const from = int32(0)
	var c metrics.Counter
	differ := 0
	for to := int32(1); int(to) < g.Nodes(); to++ {
		a, ok1 := DFS(g, from, to, &c)
		b, ok2 := DFSRecursive(g, from, to, &c)
		if !ok1 || !ok2 {
			continue
		}
		if !samePath(a, b) {
			differ++
		}
	}
	if differ == 0 {
		t.Fatal("the two DFS versions returned identical paths everywhere — " +
			"check which end of the neighbour list each one takes first")
	}
	t.Logf("the two DFS versions took different paths to %d destinations", differ)
}

// Components must partition the graph: every node in exactly one piece.
func TestComponentsPartitionTheGraph(t *testing.T) {
	g := testGraph()
	var c metrics.Counter
	count, largest := g.Components(&c)
	if count < 1 || count > g.Nodes() {
		t.Fatalf("%d components for %d nodes", count, g.Nodes())
	}
	// Every node reachable from 0 must be in the largest component's size bound.
	dist := bfsDistances(g, 0)
	reachable := 0
	for _, d := range dist {
		if d >= 0 {
			reachable++
		}
	}
	if reachable > largest {
		t.Fatalf("BFS reaches %d nodes but the largest component is %d", reachable, largest)
	}
	t.Logf("%d components, largest %d, reachable from node 0: %d", count, largest, reachable)
}

// The matrix and the list must describe the SAME graph.
func TestMatrixAgreesWithList(t *testing.T) {
	g := buildTrails(500, 31, 12, 1)
	m := NewAdjMatrix(g.Nodes())
	for v := 0; v < g.Nodes(); v++ {
		for _, w := range g.Neighbors(int32(v)) {
			m.Set(int32(v), w)
		}
	}
	for v := int32(0); int(v) < g.Nodes(); v++ {
		want := map[int32]bool{}
		for _, w := range g.Neighbors(v) {
			want[w] = true
		}
		for w := int32(0); int(w) < g.Nodes(); w++ {
			if m.Has(v, w) != want[w] {
				t.Fatalf("edge %d-%d: matrix %v, list %v", v, w, m.Has(v, w), want[w])
			}
		}
	}
}

main.go MODIFY 6 lines changed

Edit this file in ./

package main

import (
	"fmt"
	"os"
)

func usage() {
	fmt.Fprint(os.Stderr, `algo — your library workbench

  algo gen  [-n N] [-seed S] [-o FILE] [-sorted|-reverse|-shuffled] [-dup-rate R]
  algo find -title TITLE [-in FILE]
  algo load [-in FILE]
  algo stats -growth [-n N]
  algo playlist -from I -to J [-in FILE]
  algo history [-n N] [-in FILE]
  algo queue [-n N]
  algo walk [-depth D] [-branch B] [-per P]
  algo depth -n N [-iterative]
  algo sweep [-scattered]
  algo std [-n N]
  algo sort [-algo A] [-order O] [-in FILE]
  algo dc [-order O] [-in FILE]
  algo stable [-n N]
  algo count [-in FILE]
  algo radix [-in FILE]
  algo index [-in FILE] [-nogrow] [-buckets N]
  algo ordered [-in FILE] [-n N]
  algo alpha [-in FILE] [-n N] [-from A -to B]
  algo tree [-in FILE]
  algo shape [-shuffled FILE] [-sorted FILE]
  algo balance [-shuffled FILE] [-sorted FILE]
  algo rotate [-in FILE]
  algo reload [-in FILE]
  algo top [-in FILE] [-k N] [-show]
  algo pq [-in FILE] [-rounds N]
  algo net [-in FILE] [-trails N] [-length L] [-from I] [-to J]
  algo dense [-in FILE] [-trails N] [-length L]
`)
}

func main() {
	if len(os.Args) < 2 {
		usage()
		os.Exit(2)
	}
	var err error
	switch os.Args[1] {
	case "gen":
		err = cmdGen(os.Args[2:])
	case "find":
		err = cmdFind(os.Args[2:])
	case "load":
		err = cmdLoad(os.Args[2:])
	case "stats":
		err = cmdStats(os.Args[2:])
	case "playlist":
		err = cmdPlaylist(os.Args[2:])
	case "history":
		err = cmdHistory(os.Args[2:])
	case "queue":
		err = cmdQueue(os.Args[2:])
	case "walk":
		err = cmdWalk(os.Args[2:])
	case "depth":
		err = cmdDepth(os.Args[2:])
	case "sweep":
		err = cmdSweep(os.Args[2:])
	case "std":
		err = cmdStd(os.Args[2:])
	case "sort":
		err = cmdSort(os.Args[2:])
	case "dc":
		err = cmdDC(os.Args[2:])
	case "stable":
		err = cmdStable(os.Args[2:])
	case "count":
		err = cmdCount(os.Args[2:])
	case "radix":
		err = cmdRadix(os.Args[2:])
	case "index":
		err = cmdIndex(os.Args[2:])
	case "ordered":
		err = cmdOrdered(os.Args[2:])
	case "alpha":
		err = cmdAlpha(os.Args[2:])
	case "tree":
		err = cmdTree(os.Args[2:])
	case "shape":
		err = cmdShape(os.Args[2:])
	case "balance":
		err = cmdBalance(os.Args[2:])
	case "rotate":
		err = cmdRotate(os.Args[2:])
	case "reload":
		err = cmdReload(os.Args[2:])
	case "top":
		err = cmdTop(os.Args[2:])
	case "pq":
		err = cmdPq(os.Args[2:])
	case "net":
		err = cmdNet(os.Args[2:])
	case "dense":
		err = cmdDense(os.Args[2:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}