Strongly connected components

import random

from scc import scc_sizes

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


def slow_sizes(n, edges):
    """Reachability from every vertex, then mutual reachability: right, and O(V (V + E))."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    reach = []
    for s in range(n):
        seen, stack = {s}, [s]
        while stack:
            for w in adj[stack.pop()]:
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        reach.append(seen)
    groups = {frozenset(v for v in reach[s] if s in reach[v]) for s in range(n)}
    return len(groups), max((len(g) for g in groups), default=0)


def test_lesson_graph():
    """the ten pages of the lesson: five components, the largest of three pages"""
    assert scc_sizes(10, PAGES) == (5, 3)


def test_small_cases():
    """one vertex, a loop, a repeated edge, a chain and a two-way link"""
    assert scc_sizes(1, []) == (1, 1)
    assert scc_sizes(1, [(0, 0)]) == (1, 1)
    assert scc_sizes(2, [(0, 1), (0, 1)]) == (2, 1)
    assert scc_sizes(5, [(0, 1), (1, 2), (2, 3), (3, 4)]) == (5, 1)
    assert scc_sizes(3, [(0, 1), (1, 0)]) == (2, 2)


def test_random_against_reachability():
    """200 random graphs of up to 12 vertices, against a slow mutual-reachability check"""
    rng = random.Random(21)
    for _ in range(200):
        n = rng.randint(1, 12)
        edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(rng.randint(0, 2 * n))]
        assert scc_sizes(n, edges) == slow_sizes(n, edges), (n, edges)


def test_long_cycle_and_long_path():
    """a single cycle of 100,000 vertices, and a path of 100,000 vertices"""
    n = 100_000
    assert scc_sizes(n, [(i, (i + 1) % n) for i in range(n)]) == (1, n)
    assert scc_sizes(n, [(i, i + 1) for i in range(n - 1)]) == (n, 1)

import { test, assert } from 'mysmartcopilot:test';
import { sccSizes } from './scc.mjs';

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

/** Reachability from every vertex, then mutual reachability: right, and O(V (V + E)). */
function slowSizes(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) adj[u].push(v);
  const reach = [];
  for (let s = 0; s < n; s++) {
    const seen = new Set([s]);
    const stack = [s];
    while (stack.length) {
      for (const w of adj[stack.pop()]) {
        if (!seen.has(w)) {
          seen.add(w);
          stack.push(w);
        }
      }
    }
    reach.push(seen);
  }
  const groups = new Set();
  let largest = 0;
  for (let s = 0; s < n; s++) {
    const members = [...reach[s]].filter((v) => reach[v].has(s)).sort((a, b) => a - b);
    groups.add(members.join(','));
    largest = Math.max(largest, members.length);
  }
  return [groups.size, largest];
}

test('the ten pages of the lesson: five components, the largest of three pages', () => {
  assert.deepEqual(sccSizes(10, PAGES), [5, 3]);
});

test('one vertex, a loop, a repeated edge, a chain and a two-way link', () => {
  assert.deepEqual(sccSizes(1, []), [1, 1]);
  assert.deepEqual(sccSizes(1, [[0, 0]]), [1, 1]);
  assert.deepEqual(sccSizes(2, [[0, 1], [0, 1]]), [2, 1]);
  assert.deepEqual(sccSizes(5, [[0, 1], [1, 2], [2, 3], [3, 4]]), [5, 1]);
  assert.deepEqual(sccSizes(3, [[0, 1], [1, 0]]), [2, 2]);
});

test('200 random graphs of up to 12 vertices, against a slow mutual-reachability check', () => {
  let seed = 21;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  const pick = (k) => Math.floor(random() * k);
  for (let t = 0; t < 200; t++) {
    const n = 1 + pick(12);
    const edges = Array.from({ length: pick(2 * n + 1) }, () => [pick(n), pick(n)]);
    assert.deepEqual(sccSizes(n, edges), slowSizes(n, edges), JSON.stringify([n, edges]));
  }
});

test('a single cycle of 100,000 vertices, and a path of 100,000 vertices', () => {
  const n = 100000;
  const cycle = [];
  const path = [];
  for (let i = 0; i < n; i++) cycle.push([i, (i + 1) % n]);
  for (let i = 0; i < n - 1; i++) path.push([i, i + 1]);
  assert.deepEqual(sccSizes(n, cycle), [1, n]);
  assert.deepEqual(sccSizes(n, path), [n, 1]);
});