Cycle detection: directed and undirected graphs

"""Both brute forces of the lesson. The work is counted, not timed, so every computer prints the same."""


def reaches(adj, start, goal, skip=-1):
    """A plain search from start; skip is a cable the search may not use. Returns (found, list entries read)."""
    seen, stack, reads = {start}, [start], 0
    while stack:
        u = stack.pop()
        if u == goal:
            return True, reads
        for v, cable in adj[u]:
            reads += 1
            if cable != skip and v not in seen:
                seen.add(v)
                stack.append(v)
    return False, reads


def loop_cable_slow(n, cables):
    """Takes each cable out in turn; if its two routers stay connected, the cable lies on a loop."""
    adj = [[] for _ in range(n)]
    for i, (a, b) in enumerate(cables):
        adj[a].append((b, i))
        adj[b].append((a, i))
    total = 0
    for i, (a, b) in enumerate(cables):
        found, reads = reaches(adj, a, b, skip=i)
        total += reads
        if found:
            return (a, b), total
    return None, total


def circular_cell_slow(names, refs):
    """Searches from every cell to see whether its references lead back to it."""
    index = {name: i for i, name in enumerate(names)}
    adj = [[(index[r], None) for r in refs.get(name, [])] for name in names]  # references have no cable number
    total = 0
    for i, name in enumerate(names):
        for v, _ in adj[i]:  # can a cell this one refers to lead back here?
            found, reads = reaches(adj, v, i)
            total += reads + 1
            if found:
                return name, total
    return None, total


print("Problem A: take each cable out and search again")
print("example 1:", loop_cable_slow(5, [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)])[0], "lies on a loop")
print("example 2:", loop_cable_slow(4, [(0, 1), (1, 2), (1, 3)])[0])
print("example 3:", loop_cable_slow(2, [(0, 1), (0, 1)])[0], "lies on a loop")
print("routers in a line, no loop   list entries read")
for n in (500, 1_000, 2_000):
    print(f"{n:>26,}   {loop_cable_slow(n, [(i, i + 1) for i in range(n - 1)])[1]:>17,}")

print()
print("Problem B: search from every cell for a way back")
sheet = ["A1", "B1", "C1", "D1"]
formulas = {"A1": ["B1", "C1"], "B1": ["D1"], "C1": ["D1"]}
print("example 1:", circular_cell_slow(sheet, formulas)[0])
print("example 2:", circular_cell_slow(sheet, {**formulas, "D1": ["A1"]})[0], "is on a circular reference")
print("example 3:", circular_cell_slow(["E1"], {"E1": ["E1"]})[0], "is on a circular reference")
print("cells in a chain, no loop    list entries read")
for n in (500, 1_000, 2_000):
    names = [f"A{i + 1}" for i in range(n)]
    chain = {names[i]: [names[i + 1]] for i in range(n - 1)}
    print(f"{n:>26,}   {circular_cell_slow(names, chain)[1]:>17,}")
print("twice the size, four times the reads: about 10^10 for A and 5 x 10^9 for B at 100,000")

Problem A: take each cable out and search again
example 1: (1, 2) lies on a loop
example 2: None
example 3: (0, 1) lies on a loop
routers in a line, no loop   list entries read
                       500             249,001
                     1,000             998,001
                     2,000           3,996,001

Problem B: search from every cell for a way back
example 1: None
example 2: A1 is on a circular reference
example 3: E1 is on a circular reference
cells in a chain, no loop    list entries read
                       500             124,750
                     1,000             499,500
                     2,000           1,999,000
twice the size, four times the reads: about 10^10 for A and 5 x 10^9 for B at 100,000