invariants

Documentation

Overview

Package invariants provides hardened assertion helpers for graph property-based tests. Each helper takes a *lpg.Graph (or related type), checks a structural invariant, and calls t.Errorf (not t.Fatalf) so a single test can validate multiple invariants and accumulate all failures in one pass.

Failure messages always include a counter-example — an offending vertex pair, component ID, or edge — so the caller can reproduce the failure from the log without a debugger.

Concurrency

These helpers are NOT safe for concurrent use with mutations on the same graph. They are intended for use after a graph is fully constructed and before it is modified again.

Index

• func AssertBipartite[N comparable, W any](t testing.TB, g graphView[N, W])
• func AssertConnected[N comparable, W any](t testing.TB, g graphView[N, W])
• func AssertDAG[N comparable, W any](t testing.TB, g graphView[N, W])
• func AssertDistanceBound[W search.Weight](t testing.TB, bfsDepths map[graph.NodeID]int, dijkstra *search.Distances[W])
• func AssertShapeEqual[N comparable, W any](t testing.TB, a, b *lpg.Graph[N, W])
• func BuildBFSDepths[W any](ctx context.Context, c *csr.CSR[W], src graph.NodeID) (map[graph.NodeID]int, error)

Functions

func AssertBipartite

func AssertBipartite[N comparable, W any](t testing.TB, g graphView[N, W])

AssertBipartite fails t when g is not 2-colourable. It performs a BFS 2-colouring over the undirected view of g (ignoring edge direction and weight). On failure the message identifies the offending edge (u, v) where both endpoints received the same colour.

func AssertConnected

func AssertConnected[N comparable, W any](t testing.TB, g graphView[N, W])

AssertConnected fails t when the underlying undirected view of g has more than one weakly connected component. On failure the message states the number of components found.

An empty graph (Order = 0) is considered vacuously connected.

func AssertDAG

func AssertDAG[N comparable, W any](t testing.TB, g graphView[N, W])

AssertDAG fails t when g contains a directed cycle (i.e. when any strongly connected component has size > 1, or a single-node SCC carries a self-loop). On failure it prints the first offending SCC (up to 5 nodes) as a counter-example.

func AssertDistanceBound

func AssertDistanceBound[W search.Weight](
	t testing.TB,
	bfsDepths map[graph.NodeID]int,
	dijkstra *search.Distances[W],
)

AssertDistanceBound fails t when any BFS hop-distance exceeds the corresponding Dijkstra weighted distance. This verifies the well-known property: on a graph with unit or positive weights, BFS hop-count ≤ weighted shortest-path distance.

bfsDepths is a map from NodeID to BFS depth produced by a call to BuildBFSDepths. dijkstra is the search.Distances result returned by search.Dijkstra from the same source node.

func AssertShapeEqual

func AssertShapeEqual[N comparable, W any](t testing.TB, a, b *lpg.Graph[N, W])

AssertShapeEqual fails t when graphs a and b do not have the same Order (vertex count), Size (edge count), or edge set. On failure the message identifies the first discrepancy found. Edge weights are intentionally ignored; only topology is compared.

func BuildBFSDepths

func BuildBFSDepths[W any](ctx context.Context, c *csr.CSR[W], src graph.NodeID) (map[graph.NodeID]int, error)

BuildBFSDepths runs BFS from src on c and returns a map from NodeID to BFS depth (number of hops). This is a convenience helper for preparing the bfsDepths argument of AssertDistanceBound.