Weighted Graphs — Programuoki

Code

The harness and the one hard limit

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

command	what it does
`algo route`	one route: BFS against Dijkstra, and the two frontiers
`algo frontier`	the same over every destination — so the ratio is a claim, not an anecdote

The tests

test	what it requires
`TestBothFrontiersReturnTheSameCost`	both frontiers return an identical cost for every destination, and the path adds up to it
`TestFewestHopsIsNotCheapest`	BFS's route is never cheaper and sometimes dearer
`TestTheHeapHoldsStaleEntries`	the heap holds more entries than it settles nodes
`TestDijkstraIsWrongOnNegativeWeights`	with a negative edge the answer is wrong

The first matters most, not for what it checks but for what it licenses. Step 5 compares two frontiers — and the comparison only means anything if they give the same answer. So that is checked first.

The third protects step 2's decision:

629 pushes settled 562 nodes: 67 stale entries skipped (1.12 pushes per node)

1.12 pushes per node. If you ever get exactly 1.00, you have implemented decrease-key — a different structure with a different cost — and the test will say so.

The fourth test — Dijkstra's one hard limit

In step 2 the proof rested on an assumption: no edge is negative. Here is what happens without it.

   0 ──1── 2               the direct route, cost 1
   0 ──2── 1 ──(−5)── 2    the detour, cost 2 + (−5) = −3

Dijkstra answered 1; the true cheapest route costs -3

Node 2 is reached at 1 and settled before node 1 is popped at all — so the cheaper detour is never considered.

There is no error, no loop, no slowdown. Just a wrong answer, delivered with exactly as much confidence as a right one. In lesson 11 the degenerate tree was slow and correct; this is the other way round.

The test requires it to stay that way — so that nobody "fixes" Dijkstra by pretending it handles negative costs. Other algorithms do that (Bellman–Ford), and they cost more.

wgraphbench.go CREATE

Create this file in ./

package main

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

	"algo/metrics"
)

// buildWeightedTrails is lesson 14's generator with a cost on every edge: the
// number of DAYS the reader waited before the next book. Same seed, same trails,
// same shape — only the weights are new.
func buildWeightedTrails(n, trails, length int, seed int64) *WGraph {
	rng := rand.New(rand.NewSource(seed))
	g := NewWGraph(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, int32(1+rng.Intn(60))) // 1..60 days
			v = w
		}
	}
	return g
}

func cmdRoute(args []string) error {
	fs := flag.NewFlagSet("route", 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 pair where hops and cost disagree most)")
	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 := buildWeightedTrails(n, *trails, *length, *seed)

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

	var bc, hc, sc metrics.Counter
	bfsPath, okB := BFSW(g, int32(*from), dst, &bc)
	t0 := time.Now()
	heapPath, heapCost, heapSettled, okH := DijkstraHeap(g, int32(*from), dst, &hc)
	heapTime := time.Since(t0)
	t0 = time.Now()
	_, scanCost, scanSettled, okS := DijkstraScan(g, int32(*from), dst, &sc)
	scanTime := time.Since(t0)

	if !okB || !okH || !okS {
		fmt.Printf("no route from %d to %d\n", *from, dst)
		return nil
	}

	fmt.Printf("nodes %d, edges %d, weights = days between borrows (1..60)\n", g.Nodes(), g.Edges())
	fmt.Printf("route from %d to %d\n\n", *from, dst)

	fmt.Printf("  %-26s %8s %10s\n", "", "hops", "days")
	fmt.Printf("  %-26s %8d %10d\n", "BFS (fewest hops)", len(bfsPath)-1, g.PathCost(bfsPath))
	fmt.Printf("  %-26s %8d %10d\n", "Dijkstra (fewest days)", len(heapPath)-1, heapCost)
	fmt.Printf("\n  the cheapest route takes %d more hops and saves %d days\n",
		(len(heapPath)-1)-(len(bfsPath)-1), g.PathCost(bfsPath)-heapCost)

	fmt.Printf("\n  %-26s %14s %12s %12s\n", "same answer, two frontiers", "queue work", "settled", "time")
	fmt.Printf("  %-26s %14d %12d %12s\n", "binary heap (lesson 13)", hc.N(), heapSettled, heapTime.Round(time.Microsecond))
	fmt.Printf("  %-26s %14d %12d %12s\n", "linear min-scan", sc.N(), scanSettled, scanTime.Round(time.Microsecond))
	fmt.Printf("\n  identical cost: %v (%d vs %d)\n", heapCost == scanCost, heapCost, scanCost)
	fmt.Printf("  work ratio %.1fx", float64(sc.N())/float64(hc.N()))
	if heapTime > 0 {
		fmt.Printf(", time ratio %.1fx", float64(scanTime)/float64(heapTime))
	}
	fmt.Println()
	return nil
}

// mostDisagreeing finds the destination where the fewest-hops route and the
// cheapest route differ most in days — the clearest illustration that a hop
// count is not a cost.
func mostDisagreeing(g *WGraph, from int32) int32 {
	best, bestGap := from, int32(-1)
	for t := 0; t < g.Nodes(); t++ {
		if int32(t) == from {
			continue
		}
		var a, b metrics.Counter
		bp, ok1 := BFSW(g, from, int32(t), &a)
		_, cost, _, ok2 := DijkstraHeap(g, from, int32(t), &b)
		if !ok1 || !ok2 {
			continue
		}
		if gap := g.PathCost(bp) - cost; gap > bestGap {
			best, bestGap = int32(t), gap
		}
	}
	return best
}

// cmdFrontier is the two-frontier comparison across every reachable
// destination, so the ratio is a claim rather than an anecdote.
func cmdFrontier(args []string) error {
	fs := flag.NewFlagSet("frontier", 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")
	from := fs.Int("from", 0, "start node")
	rounds := fs.Int("rounds", 5, "repeat the whole sweep this many times, for the timings")
	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 := buildWeightedTrails(n, *trails, *length, 1)

	var hc, sc metrics.Counter
	var heapTime, scanTime time.Duration
	pairs, agree := 0, 0
	var hopsDiffer int
	for r := 0; r < *rounds; r++ {
		var rhc, rsc metrics.Counter
		pairs, agree, hopsDiffer = 0, 0, 0
		for t := 0; t < n; t++ {
			if int32(t) == int32(*from) {
				continue
			}
			t0 := time.Now()
			hp, hcost, _, ok1 := DijkstraHeap(g, int32(*from), int32(t), &rhc)
			heapTime += time.Since(t0)
			t0 = time.Now()
			_, scost, _, ok2 := DijkstraScan(g, int32(*from), int32(t), &rsc)
			scanTime += time.Since(t0)
			if !ok1 || !ok2 {
				continue
			}
			pairs++
			if hcost == scost {
				agree++
			}
			var bcc metrics.Counter
			if bp, ok := BFSW(g, int32(*from), int32(t), &bcc); ok && len(bp) != len(hp) {
				hopsDiffer++
			}
		}
		hc, sc = rhc, rsc // one round's counts; they are identical every round
	}
	heapTime /= time.Duration(*rounds)
	scanTime /= time.Duration(*rounds)
	fmt.Printf("nodes %d, edges %d, %d reachable destinations from %d\n\n", g.Nodes(), g.Edges(), pairs, *from)
	fmt.Printf("  %-26s %16s %12s\n", "", "queue work", "time")
	fmt.Printf("  %-26s %16d %12s\n", "binary heap (lesson 13)", hc.N(), heapTime.Round(time.Millisecond))
	fmt.Printf("  %-26s %16d %12s\n", "linear min-scan", sc.N(), scanTime.Round(time.Millisecond))
	fmt.Printf("\n  identical cost on %d of %d destinations\n", agree, pairs)
	fmt.Printf("  work ratio  %.1fx\n", float64(sc.N())/float64(hc.N()))
	fmt.Printf("  time ratio  %.1fx\n", float64(scanTime)/float64(heapTime))
	fmt.Printf("\n  BFS's route differed from Dijkstra's on %d of %d (%.1f%%)\n",
		hopsDiffer, pairs, 100*float64(hopsDiffer)/float64(pairs))
	return nil
}

wgraph_test.go CREATE

Create this file in ./

package main

import (
	"testing"

	"algo/metrics"
)

func testWGraph() *WGraph { return buildWeightedTrails(1000, 62, 12, 1) }

// isWPath checks a path is real and that its edges add up to the reported cost.
func isWPath(g *WGraph, p []int32, from, to, cost int32) bool {
	if len(p) == 0 || p[0] != from || p[len(p)-1] != to {
		return false
	}
	total := int32(0)
	for i := 1; i < len(p); i++ {
		found := false
		for _, e := range g.Neighbors(p[i-1]) {
			if e.To == p[i] {
				total += e.Cost
				found = true
				break
			}
		}
		if !found {
			return false
		}
	}
	return total == cost
}

// THE TWO FRONTIERS MUST AGREE. Swapping the priority queue changes how long the
// search takes and nothing else — which is what makes the comparison in step 5
// meaningful at all.
func TestBothFrontiersReturnTheSameCost(t *testing.T) {
	g := testWGraph()
	var hc, sc metrics.Counter
	checked := 0
	for to := int32(1); int(to) < g.Nodes(); to++ {
		hp, hcost, _, ok1 := DijkstraHeap(g, 0, to, &hc)
		_, scost, _, ok2 := DijkstraScan(g, 0, to, &sc)
		if ok1 != ok2 {
			t.Fatalf("node %d: heap found %v, scan found %v", to, ok1, ok2)
		}
		if !ok1 {
			continue
		}
		checked++
		if hcost != scost {
			t.Fatalf("node %d: heap cost %d, scan cost %d", to, hcost, scost)
		}
		if !isWPath(g, hp, 0, to, hcost) {
			t.Fatalf("node %d: the heap's path does not add up to %d", to, hcost)
		}
	}
	if checked < 100 {
		t.Fatalf("only %d destinations checked", checked)
	}
	t.Logf("%d destinations, identical cost every time; heap queue work %d, scan %d (%.1fx)",
		checked, hc.N(), sc.N(), float64(sc.N())/float64(hc.N()))
}

// FEWEST HOPS IS NOT CHEAPEST. Lesson 14's answer is never better than
// Dijkstra's and is often worse — asserted so the distinction survives.
func TestFewestHopsIsNotCheapest(t *testing.T) {
	g := testWGraph()
	var bc, hc metrics.Counter
	worse, equal := 0, 0
	var worstGap int32
	for to := int32(1); int(to) < g.Nodes(); to++ {
		bp, ok1 := BFSW(g, 0, to, &bc)
		_, cost, _, ok2 := DijkstraHeap(g, 0, to, &hc)
		if !ok1 || !ok2 {
			continue
		}
		bcost := g.PathCost(bp)
		if bcost < cost {
			t.Fatalf("node %d: BFS route costs %d, cheaper than the cheapest (%d)", to, bcost, cost)
		}
		if bcost == cost {
			equal++
		} else {
			worse++
			if gap := bcost - cost; gap > worstGap {
				worstGap = gap
			}
		}
	}
	if worse == 0 {
		t.Fatal("the fewest-hops route was always the cheapest — then the weights are doing nothing")
	}
	t.Logf("BFS route: cheapest %d, more expensive %d, worst excess %d days", equal, worse, worstGap)
}

// LAZY DELETION MEANS THE HEAP HOLDS MORE ENTRIES THAN THERE ARE NODES. If a
// version of this settles exactly one entry per node, it is doing decrease-key,
// which is a different structure with a different cost.
func TestTheHeapHoldsStaleEntries(t *testing.T) {
	g := testWGraph()
	var c metrics.Counter
	pushes, settled := 0, 0
	// Re-run the search counting pushes by hand.
	const inf = int32(1) << 30
	dist := make([]int32, g.Nodes())
	done := make([]bool, g.Nodes())
	for i := range dist {
		dist[i] = inf
	}
	dist[0] = 0
	h := NewNodeHeap(g.Nodes())
	h.Push(0, 0, &c)
	pushes++
	for h.Len() > 0 {
		v, d, _ := h.Pop(&c)
		if done[v] {
			continue
		}
		done[v] = true
		settled++
		for _, e := range g.Neighbors(v) {
			if nd := d + e.Cost; nd < dist[e.To] {
				dist[e.To] = nd
				h.Push(e.To, nd, &c)
				pushes++
			}
		}
	}
	if pushes <= settled {
		t.Fatalf("%d pushes for %d settled nodes — no stale entries, so this is not lazy deletion", pushes, settled)
	}
	t.Logf("%d pushes settled %d nodes: %d stale entries skipped (%.2f pushes per node)",
		pushes, settled, pushes-settled, float64(pushes)/float64(settled))
}

// THE HONEST LIMIT, ASSERTED. Dijkstra requires non-negative weights. Given a
// negative edge it does not slow down or error — it returns a WRONG answer,
// because it settles a node before a cheaper route to it has been found.
//
// The graph, searching from 0 to 2:
//
//	0 --1--- 2          the direct route, cost 1
//	0 --2--- 1 --(-5)--- 2   the detour, cost 2 + (-5) = -3
//
// Node 2 is reached at 1 and SETTLED before node 1 is ever popped, so the
// cheaper detour is never considered. The order in which nodes are settled is
// the whole of Dijkstra's argument, and a negative edge destroys it: settling a
// node no longer means its distance is final.
func TestDijkstraIsWrongOnNegativeWeights(t *testing.T) {
	g := NewWGraph(3)
	g.AddEdge(0, 2, 1)
	g.AddEdge(0, 1, 2)
	g.AddEdge(1, 2, -5)

	var c metrics.Counter
	_, cost, _, ok := DijkstraHeap(g, 0, 2, &c)
	if !ok {
		t.Fatal("no route found at all")
	}
	const truth = int32(-3)
	if cost == truth {
		t.Fatal("Dijkstra returned the true optimum on a negative edge — " +
			"that is luck, not correctness, and the demonstration is gone")
	}
	t.Logf("Dijkstra answered %d; the true cheapest route costs %d", cost, truth)
}

func BenchmarkDijkstraHeap(b *testing.B) {
	g := testWGraph()
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		DijkstraHeap(g, 0, 999, &c)
	}
}

func BenchmarkDijkstraScan(b *testing.B) {
	g := testWGraph()
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		DijkstraScan(g, 0, 999, &c)
	}
}

func BenchmarkDijkstraHeapAllPairs(b *testing.B) {
	g := testWGraph()
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for to := int32(1); int(to) < g.Nodes(); to += 10 {
			DijkstraHeap(g, 0, to, &c)
		}
	}
}

func BenchmarkDijkstraScanAllPairs(b *testing.B) {
	g := testWGraph()
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for to := int32(1); int(to) < g.Nodes(); to += 10 {
			DijkstraScan(g, 0, to, &c)
		}
	}
}

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]
  algo route [-in FILE] [-from I] [-to J]
  algo frontier [-in FILE] [-from I]
`)
}

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:])
	case "route":
		err = cmdRoute(os.Args[2:])
	case "frontier":
		err = cmdFrontier(os.Args[2:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}