Compute distances with min plus

Download the complete SQL script, including dataset setup for a fresh database.

Build shortest distances using sparse matrix products, then check every answer against native BFS. Run the setup once and execute the whole script in one SQL session.

Relax distances until they stop changing

min_plus adds an edge’s weight to its neighbour’s distance, then takes the smallest contribution. In this unweighted graph each edge costs 1. The seed starts at zero and every other node at positive infinity.

SELECT warren.vector_from_query('example_social', 'distance',
    'SELECT 1::bigint, 0::float8', fill := 'Infinity'::float8);

DO $$
DECLARE changed double precision;
BEGIN
    FOR iteration IN 1..100 LOOP
        PERFORM warren.vector_map('example_social', 'next_distance', 'distance', persist := false);
        PERFORM warren.spmv('example_social', 'distance', 'next_distance', 'min_plus',
            transpose := true, accumulate := 'min', persist := false);
        PERFORM warren.vector_map('example_social', 'changed',
            'CASE WHEN distance <> next_distance THEN 1 ELSE 0 END', persist := false);
        changed := warren.vector_reduce('example_social', 'changed', 'sum');
        PERFORM warren.vector_map('example_social', 'distance', 'next_distance');
        RAISE NOTICE 'Round %: % distances improved', iteration, changed;
        IF changed = 0 THEN RETURN; END IF;
    END LOOP;
    RAISE EXCEPTION 'Distances did not converge within 100 rounds';
END $$;

SELECT value AS shortest_distance, count(*) AS people
FROM warren.vector_values('example_social', 'distance', NULL::bigint)
GROUP BY value ORDER BY value;

SELECT count(*) AS mismatches
FROM warren.vector_values('example_social', 'distance', NULL::bigint) d
FULL JOIN warren.bfs('example_social', ARRAY[1::bigint], NULL::integer) b USING (node_id)
WHERE d.value IS DISTINCT FROM b.depth::float8;

accumulate := 'min' keeps an existing distance unless a shorter one is found. Each round extends the search by another edge; the loop stops when no distance improves. Messages show convergence after ten rounds on this dataset: nine rounds discover nodes, and the tenth confirms stability.

The persisted distance vector contains a value for every live node. The farthest people are nine hops away. The final cross-check reports zero mismatches against BFS. Unreachable nodes would retain infinity; the example’s ring makes everyone reachable.

Choose the right primitive

For this unweighted task, native BFS is the simpler operation. This example exposes the algebra underneath: on a graph whose nonnegative weights represent travel times, min_plus instead relaxes travel-time distances. Use Dijkstra for a single weighted path or the sssp_vector library function for weighted distances; see compute.

next_distance and changed are transient scratch vectors. distance is persisted and can be read by later sessions. The 100-round limit protects this demonstration from an unbounded loop; a different graph may need more rounds. See vectors for lifetime and version rules.