Connectivity and Connected Components

from collections import deque


def adjacency(pairs, vertices):
    graph = {v: [] for v in vertices}
    for a, b in pairs:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v].sort()
    return graph


def components(graph):
    """Every component, as a list of sorted vertex lists."""
    seen = set()
    found = []
    reads = 0
    for start in sorted(graph):
        if start in seen:
            continue
        piece = {start}
        seen.add(start)
        queue = deque([start])
        while queue:
            v = queue.popleft()
            for w in graph[v]:
                reads += 1
                if w not in seen:
                    seen.add(w)
                    piece.add(w)
                    queue.append(w)
        found.append(sorted(piece))
    return found, reads


EDGES = [("A", "B"), ("B", "C"), ("A", "C"),      # a triangle
         ("D", "E"),                              # a pair
         ("F", "G"), ("G", "H"), ("H", "F"), ("H", "I")]   # a triangle with a tail
VERTICES = "ABCDEFGHIJ"                           # J is isolated

GRAPH = adjacency(EDGES, VERTICES)
found, reads = components(GRAPH)

print("the graph has %d vertices and %d edges" % (len(GRAPH), len(EDGES)))
print("components found:", len(found))
for i, piece in enumerate(found, 1):
    word = "vertex" if len(piece) == 1 else "vertices"
    print("   component %d (%d %s): %s" % (i, len(piece), word, " ".join(piece)))
print()
print("every vertex is in exactly one component:",
      sorted(v for piece in found for v in piece) == sorted(VERTICES))
print("the isolated vertex J is its own component:", ["J"] in found)
print("adjacency entries read in total:", reads, "= 2E for E =", len(EDGES))
print("so finding ALL components costs one traversal's work, O(V + E).")

from collections import deque


def adjacency(pairs, vertices):
    graph = {v: [] for v in vertices}
    for a, b in pairs:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v].sort()
    return graph


def label_components(graph):
    """Give every vertex its component number. One pass, then O(1) questions."""
    label = {}
    number = 0
    for start in sorted(graph):
        if start in label:
            continue
        label[start] = number
        queue = deque([start])
        while queue:
            v = queue.popleft()
            for w in graph[v]:
                if w not in label:
                    label[w] = number
                    queue.append(w)
        number += 1
    return label, number


EDGES = [("A", "B"), ("B", "C"), ("A", "C"), ("D", "E"),
         ("F", "G"), ("G", "H"), ("H", "F"), ("H", "I")]
GRAPH = adjacency(EDGES, "ABCDEFGHIJ")
label, count = label_components(GRAPH)

print("component number of each vertex:")
print("   " + "  ".join("%s:%d" % (v, label[v]) for v in sorted(label)))
print("components:", count)
print()
for a, b in (("A", "C"), ("A", "D"), ("F", "I"), ("J", "A")):
    print("   %s and %s connected to each other: %s"
          % (a, b, label[a] == label[b]))
print()
print("one O(V + E) pass makes every later question O(1).")

from collections import deque


def is_connected_count(n, edges):
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    seen = {0}
    queue = deque([0])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in seen:
                seen.add(w)
                queue.append(w)
    return len(seen) == n


n = 6
print("on %d vertices, the minimum for a connected graph is %d edges" % (n, n - 1))
print()

too_few = [(0, 1), (1, 2), (2, 3), (3, 4)]          # 4 edges, 5 is the minimum
a_tree = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]   # exactly 5
one_more = a_tree + [(0, 5)]                        # 6 edges: a cycle appears

for name, edges in (("4 edges", too_few), ("5 edges, a path", a_tree),
                    ("6 edges, the path closed", one_more)):
    print("   %-26s connected: %-5s   edges %d, V-1 = %d"
          % (name, is_connected_count(n, edges), len(edges), n - 1))

print()
print("4 edges on 6 vertices cannot be connected, whatever the arrangement:",
      len(too_few) < n - 1)
print("5 edges and connected means a tree, so no cycle:", len(a_tree) == n - 1)
print("adding the 6th edge closed a cycle and kept it connected.")

from collections import deque


def reachable(out_edges, start, keys):
    seen = {start}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for w in out_edges.get(v, []):
            if w not in seen:
                seen.add(w)
                queue.append(w)
    return seen


def classify(vertices, arcs):
    out = {v: [] for v in vertices}
    both = {v: [] for v in vertices}
    for a, b in arcs:
        out[a].append(b)
        both[a].append(b)
        both[b].append(a)

    strong = all(len(reachable(out, v, vertices)) == len(vertices)
                 for v in vertices)
    weak = len(reachable(both, vertices[0], vertices)) == len(vertices)
    if strong:
        return "strongly connected"
    if weak:
        return "weakly connected"
    return "disconnected"


cycle = (["A", "B", "C"], [("A", "B"), ("B", "C"), ("C", "A")])
chain = (["A", "B", "C"], [("A", "B"), ("B", "C")])
apart = (["A", "B", "C", "D"], [("A", "B"), ("C", "D")])

for name, (vs, arcs) in (("a directed cycle A->B->C->A", cycle),
                         ("a chain A->B->C", chain),
                         ("A->B and C->D", apart)):
    print("%-30s %s" % (name, classify(vs, arcs)))

print()
print("in the chain, C cannot reach A, so it is not strongly connected,")
print("but ignoring the arrows it is one piece, so it is weakly connected.")