All-pairs shortest paths: Floyd-Warshall

import random

from all_pairs import all_pairs

DATA_CENTRES = [(0, 1, 4), (1, 2, 3), (2, 3, 2), (3, 4, 5), (4, 5, 1), (5, 0, 7), (0, 3, 12), (1, 4, 9), (2, 5, 8),
                (4, 1, 2), (3, 0, 6), (5, 2, 3)]


def by_every_path(n, edges):
    """The slow answer: None if any cycle is negative, else the cheapest simple path for every pair."""
    out = [[] for _ in range(n)]
    for u, v, w in edges:
        out[u].append((v, w))
    table = [[0 if i == j else None for j in range(n)] for i in range(n)]
    for s in range(n):
        stack = [(s, 0, {s})]
        while stack:
            u, total, seen = stack.pop()
            for v, w in out[u]:
                if v == s and total + w < 0:
                    return None  # a negative cycle through s
                if v not in seen:
                    if table[s][v] is None or total + w < table[s][v]:
                        table[s][v] = total + w
                    stack.append((v, total + w, seen | {v}))
    return table


def test_data_centres():
    """the lesson's six data centres"""
    assert all_pairs(6, DATA_CENTRES) == [
        [0, 4, 7, 9, 13, 14], [11, 0, 3, 5, 9, 10], [8, 9, 0, 2, 7, 8],
        [6, 7, 9, 0, 5, 6], [8, 2, 4, 6, 0, 1], [7, 11, 3, 5, 10, 0],
    ]


def test_negative_edges_without_a_negative_cycle():
    """Q, R, S form a cycle of +1 with a negative edge in it; nothing leads back to P"""
    edges = [(0, 1, 3), (1, 2, -2), (2, 3, 2), (3, 1, 1)]
    assert all_pairs(4, edges) == [[0, 3, 1, 3], [None, 0, -2, 0], [None, 3, 0, 2], [None, 1, -1, 0]]


def test_negative_cycle():
    """S -> Q of -1 makes the cycle Q, R, S weigh -1"""
    assert all_pairs(4, [(0, 1, 3), (1, 2, -2), (2, 3, 2), (3, 1, -1)]) is None


def test_negative_loop():
    """a loop of -1 on vertex 1 is a negative cycle, even though nothing else is wrong"""
    assert all_pairs(3, [(0, 1, 2), (1, 2, 2), (1, 1, -1)]) is None


def test_parallel_edges_and_a_positive_loop():
    """two edges from 0 to 1 (5 and 2) and a loop of +4 on vertex 1"""
    assert all_pairs(2, [(0, 1, 5), (0, 1, 2), (1, 1, 4), (1, 0, 1)]) == [[0, 2], [1, 0]]


def test_random_graphs():
    """300 small random graphs with weights from -3 to 9, against every path and every cycle"""
    rng = random.Random(23)
    for _ in range(300):
        n = rng.randint(1, 5)
        edges = [(rng.randrange(n), rng.randrange(n), rng.randint(-3, 9)) for _ in range(rng.randint(0, 9))]
        assert all_pairs(n, edges) == by_every_path(n, edges), (n, edges)


def line_graph(rng, connected, isolated):
    """Vertices on a line, each edge as long as the gap it spans, then potentials: every distance is known."""
    n = connected + isolated
    labels = list(range(n))
    rng.shuffle(labels)
    on_line, alone = labels[:connected], labels[connected:]
    x = dict(zip(on_line, sorted(rng.sample(range(100_000), connected))))
    edges = []
    for a, b in zip(on_line, on_line[1:]):
        edges += [(a, b, x[b] - x[a]), (b, a, x[b] - x[a])]
    for _ in range(1_000):
        a, b = rng.choice(on_line), rng.choice(on_line)
        edges.append((a, b, abs(x[a] - x[b]) + rng.randint(0, 50)))
    p = {v: rng.randint(-5_000, 5_000) for v in range(n)}
    edges = [(u, v, w + p[u] - p[v]) for u, v, w in edges]
    table = [[0 if i == j else None for j in range(n)] for i in range(n)]
    for a in on_line:
        for b in on_line:
            if a != b:
                table[a][b] = abs(x[a] - x[b]) + p[a] - p[b]
    return edges, table, on_line


def test_large_graph():
    """120 vertices, about 1,200 edges, many of them negative, and 5 vertices with no edges at all"""
    rng = random.Random(29)
    edges, table, _ = line_graph(rng, 115, 5)
    rng.shuffle(edges)
    assert all_pairs(120, edges) == table


def test_large_graph_with_one_negative_cycle():
    """the same kind of graph, plus one edge that closes a cycle of weight -1"""
    rng = random.Random(31)
    edges, table, on_line = line_graph(rng, 115, 5)
    a, b = on_line[3], on_line[90]
    edges.append((b, a, -table[a][b] - 1))  # a reaches b at table[a][b], so a -> ... -> b -> a weighs -1
    rng.shuffle(edges)
    assert all_pairs(120, edges) is None

import { test, assert } from 'mysmartcopilot:test';
import { allPairs } from './all_pairs.mjs';

const DATA_CENTRES = [[0, 1, 4], [1, 2, 3], [2, 3, 2], [3, 4, 5], [4, 5, 1], [5, 0, 7], [0, 3, 12], [1, 4, 9], [2, 5, 8],
  [4, 1, 2], [3, 0, 6], [5, 2, 3]];

function byEveryPath(n, edges) {
  const out = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) out[u].push([v, w]);
  const table = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : null)));
  for (let s = 0; s < n; s++) {
    const stack = [[s, 0, new Set([s])]];
    while (stack.length) {
      const [u, total, seen] = stack.pop();
      for (const [v, w] of out[u]) {
        if (v === s && total + w < 0) return null;
        if (seen.has(v)) continue;
        if (table[s][v] === null || total + w < table[s][v]) table[s][v] = total + w;
        stack.push([v, total + w, new Set([...seen, v])]);
      }
    }
  }
  return table;
}

function seeded(seed) {
  return () => (seed = (seed * 48271) % 2147483647) / 2147483647;
}
const below = (random, k) => Math.floor(random() * k);
const between = (random, lo, hi) => lo + below(random, hi - lo + 1);
function shuffle(random, a) {
  for (let i = a.length - 1; i > 0; i--) {
    const j = below(random, i + 1);
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

function lineGraph(random, connected, isolated) {
  const n = connected + isolated;
  const labels = shuffle(random, Array.from({ length: n }, (_, i) => i));
  const onLine = labels.slice(0, connected);
  const spots = new Set();
  while (spots.size < connected) spots.add(below(random, 100000));
  const sorted = [...spots].sort((a, b) => a - b);
  const x = new Map(onLine.map((v, i) => [v, sorted[i]]));
  const raw = [];
  for (let i = 0; i + 1 < onLine.length; i++) {
    const [a, b] = [onLine[i], onLine[i + 1]];
    raw.push([a, b, x.get(b) - x.get(a)], [b, a, x.get(b) - x.get(a)]);
  }
  for (let k = 0; k < 1000; k++) {
    const a = onLine[below(random, onLine.length)];
    const b = onLine[below(random, onLine.length)];
    raw.push([a, b, Math.abs(x.get(a) - x.get(b)) + between(random, 0, 50)]);
  }
  const p = Array.from({ length: n }, () => between(random, -5000, 5000));
  const edges = raw.map(([u, v, w]) => [u, v, w + p[u] - p[v]]);
  const table = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : null)));
  for (const a of onLine) for (const b of onLine) if (a !== b) table[a][b] = Math.abs(x.get(a) - x.get(b)) + p[a] - p[b];
  return { edges, table, onLine };
}

test("the lesson's six data centres", () => {
  assert.deepEqual(allPairs(6, DATA_CENTRES), [
    [0, 4, 7, 9, 13, 14], [11, 0, 3, 5, 9, 10], [8, 9, 0, 2, 7, 8],
    [6, 7, 9, 0, 5, 6], [8, 2, 4, 6, 0, 1], [7, 11, 3, 5, 10, 0],
  ]);
});

test('Q, R, S form a cycle of +1 with a negative edge in it; nothing leads back to P', () => {
  const edges = [[0, 1, 3], [1, 2, -2], [2, 3, 2], [3, 1, 1]];
  assert.deepEqual(allPairs(4, edges), [[0, 3, 1, 3], [null, 0, -2, 0], [null, 3, 0, 2], [null, 1, -1, 0]]);
});

test('S -> Q of -1 makes the cycle Q, R, S weigh -1', () => {
  assert.equal(allPairs(4, [[0, 1, 3], [1, 2, -2], [2, 3, 2], [3, 1, -1]]), null);
});

test('a loop of -1 on vertex 1 is a negative cycle, even though nothing else is wrong', () => {
  assert.equal(allPairs(3, [[0, 1, 2], [1, 2, 2], [1, 1, -1]]), null);
});

test('two edges from 0 to 1 (5 and 2) and a loop of +4 on vertex 1', () => {
  assert.deepEqual(allPairs(2, [[0, 1, 5], [0, 1, 2], [1, 1, 4], [1, 0, 1]]), [[0, 2], [1, 0]]);
});

test('300 small random graphs with weights from -3 to 9, against every path and every cycle', () => {
  const random = seeded(23);
  for (let k = 0; k < 300; k++) {
    const n = between(random, 1, 5);
    const m = below(random, 10);
    const edges = Array.from({ length: m }, () => [below(random, n), below(random, n), between(random, -3, 9)]);
    assert.deepEqual(allPairs(n, edges), byEveryPath(n, edges), JSON.stringify([n, edges]));
  }
});

test('120 vertices, about 1,200 edges, many of them negative, and 5 vertices with no edges at all', () => {
  const random = seeded(29);
  const { edges, table } = lineGraph(random, 115, 5);
  shuffle(random, edges);
  assert.deepEqual(allPairs(120, edges), table);
});

test('the same kind of graph, plus one edge that closes a cycle of weight -1', () => {
  const random = seeded(31);
  const { edges, table, onLine } = lineGraph(random, 115, 5);
  const [a, b] = [onLine[3], onLine[90]];
  edges.push([b, a, -table[a][b] - 1]);
  shuffle(random, edges);
  assert.equal(allPairs(120, edges), null);
});