Kodas

Matavimo aplinka ir testai

Trys failai: matavimo aplinka, testai ir dvi naujos komandos.

komanda	ką daro
`algo net`	pastato tinklą, palygina BFS ir DFS visomis pasiekiamomis kryptimis
`algo dense`	gretimumo sąrašas prieš matricą: atmintis ir peržiūros kaina

graphbench.go taip pat turi buildTrails — generatorių, kuris kuria skaitymo pėdsakus, ne atsitiktines poras. Tai svarbu: atsitiktinių porų grafas turėtų visai kitą formą ir šios pamokos su transit sulyginti nepavyktų.

Testai

testas	ką reikalauja
`TestBFSFindsTheShortestPath`	kiekvienai pasiekiamai viršūnei BFS kelias lygus tikram atstumui
`TestDFSFindsAPathButNotTheShortest`	DFS kelias tikras, niekada ne trumpesnis, ir kartais ilgesnis
`TestBothSearchesAgreeOnReachability`	visos trys sutaria, KAS pasiekiama
`TestTheTwoDFSVersionsDisagreeOnPaths`	dvi DFS versijos randa skirtingus kelius
`TestComponentsPartitionTheGraph`	komponentės padengia visas viršūnes
`TestMatrixAgreesWithList`	abi reprezentacijos aprašo tą patį grafą

Pirmasis tikrina prieš nepriklausomai apskaičiuotus atstumus — atskira bfsDistances funkcija testų faile, ne prieš tavo pačios BFS rezultatą. Tikrinti algoritmą juo pačiu reiškia netikrinti nieko.

Antrasis ir ketvirtasis vėl reikalauja, kad kažko nebūtų — tai jau pažįstama forma iš 7–13 pamokų. Jei „pataisysi" DFS taip, kad grąžintų trumpiausius kelius, parašysi BFS su papildomais žingsniais, ir testas pasakys būtent tai:

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

graphbench.go SUKURTI

Sukurk šį failą kataloge ./

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 SUKURTI

Sukurk šį failą kataloge ./

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 MODIFIKUOTI 6 eilutės pakeistos

Redaguok šį failą kataloge ./

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)
	}
}