Graphs and Trees

Vertices and edges

A graph is the mathematics of "things and the connections between them". The things are called vertices and the connections edges. A vertex (plural vertices, also called a node) is one of the objects in a graph: a router, a server, a service, a person. An edge is a connection between two vertices: a cable, a dependency, a "reports to" line. In mathematical notation a graph is a pair of sets:

Read: "graph G consists of a set of vertices V and a set of edges E". Kestrel Energy's small office network, with five switches A to E, could be:

Each edge is written as the set of its two ends, because a cable between A and B is the same as one between B and A. Graph theory does not care where the vertices are drawn or how long the lines are; only which vertices are connected counts. That is why a physical network topology and a logical one can be the same graph drawn differently.

Directed and weighted graphs

Two variations cover most of IT. In a directed graph every edge has a direction, drawn as an arrow from one vertex to another: "portal depends on auth" is not the same as "auth depends on portal", and a web link goes one way. A directed edge is written as an ordered pair (u, v), from u to v.

In a weighted graph every edge carries a number: a cost, distance, delay or capacity. OSPF gives each link a cost, a delay map gives each link its latency in milliseconds. A graph can be both directed and weighted, for example when a link's cost differs per direction.

Degree and the handshake lemma

The degree of a vertex is the number of edges that touch it — for a switch, the number of other switches it is cabled to. In the office network, A, B and C have degree 2, D has degree 3 and E has degree 1. Add them: 2 + 2 + 2 + 3 + 1 = 10, which is exactly twice the 5 edges. That is no coincidence. Every edge has two ends and adds 1 to the degree of each, so:

Read: "the sum of the degrees of all vertices v in V equals two times the number of edges" (the vertical bars around a set mean "number of elements"). This is called the handshake lemma: if people at a meeting shake hands, the total number of hands shaken is twice the number of handshakes. A practical consequence: the number of vertices with an odd degree is always even. If an inventory script reports an odd sum of port-to-switch links, a link was counted from one end only.

Storing a graph in a program

Programs store graphs in two standard ways.

• An adjacency list: for each vertex, the list of its neighbors. In Python, a dictionary of lists. Compact when most vertices have few neighbors, which is the normal case in networks.
• An adjacency matrix: a square grid with one row and one column per vertex, and a 1 in row i, column j when there is an edge from i to j. For an undirected graph the grid is symmetric. It answers "are these two connected?" instantly but needs n^2 cells; see Vectors and Matrices for what matrices can do.

The example builds both from a list of cables, then checks the handshake lemma:

cables = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
switches = sorted({s for cable in cables for s in cable})

adjacency = {s: [] for s in switches}           # adjacency list
for a, b in cables:
    adjacency[a].append(b)
    adjacency[b].append(a)                      # undirected: both ways
print(adjacency)

index = {s: i for i, s in enumerate(switches)}  # adjacency matrix
matrix = [[0] * len(switches) for _ in switches]
for a, b in cables:
    matrix[index[a]][index[b]] = matrix[index[b]][index[a]] = 1
for s, row in zip(switches, matrix):
    print(s, row)

degrees = {s: len(n) for s, n in adjacency.items()}
print(degrees, "sum =", sum(degrees.values()), "edges =", len(cables))

{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C', 'E'], 'E': ['D']}
A [0, 1, 1, 0, 0]
B [1, 0, 0, 1, 0]
C [1, 0, 0, 1, 0]
D [0, 1, 1, 0, 1]
E [0, 0, 0, 1, 0]
{'A': 2, 'B': 2, 'C': 2, 'D': 3, 'E': 1} sum = 10 edges = 5

Paths, cycles and connectivity

A path is a sequence of vertices in which each consecutive pair is joined by an edge, such as A → B → D → E. Its length is the number of edges (here 3), or, in a weighted graph, the sum of the weights. A cycle is a path that returns to its start without visiting any edge or other vertex twice: A → B → D → C → A. A graph is connected when there is a path between every pair of vertices; a network that falls apart into two pieces after a cable cut was connected before and is not after.

Cycles are the reason networks are resilient (a second path when one link fails) and the reason Ethernet needs spanning trees (frames that circle forever). The fewest hops between two vertices are found with a breadth-first search, which explores the graph in rings: first all neighbors, then all neighbors of neighbors, and so on. It is explained step by step on Data Structures; on the office network:

from collections import deque

network = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"]}

def hops(graph, start):
    seen = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if n not in seen:
                seen[n] = seen[node] + 1
                queue.append(n)
    return seen

print(hops(network, "A"))
print("connected:", len(hops(network, "A")) == len(network))

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}
connected: True

The second line uses a handy test: a graph is connected exactly when a search from any one vertex reaches all of them.

Shortest paths and Dijkstra's algorithm

In a weighted graph, "fewest hops" is not what you want. A shortest path between two vertices is a path whose total edge weight is as small as possible; "shortest" may mean cheapest, fastest or lowest-latency, depending on what the weights stand for. Three fast links can beat one slow one.

Dijkstra's algorithm, published by the Dutch computer scientist Edsger Dijkstra in 1959, finds the shortest paths from one start vertex to every other vertex, provided no edge has a negative weight. The idea is greedy and simple:

1. Give the start distance 0 and every other vertex distance ∞ ("not reached yet").
2. Pick the unvisited vertex with the smallest distance and mark it visited: its distance is now final.
3. For each of its neighbors, check whether going through this vertex is cheaper than the best distance known so far; if so, lower that distance.
4. Repeat from step 2 until every reachable vertex is visited.

Why may a distance be called final in step 2? Every other route to that vertex would have to leave the visited area through a vertex that is already at least as far away, and with no negative weights the remaining edges can only add to the cost.

Worked example: Dijkstra by hand

Run the algorithm from R1 on the routers in the figure. The table shows the best known distance after each visit; a bold number is final.

Notice that the direct link R1–R2 (cost 10) loses to a four-hop path of cost 5. The program below does the same, using a priority queue (heapq) to find "the unvisited vertex with the smallest distance" quickly, and remembers each vertex's previous hop so it can print the paths:

import heapq

links = {                     # OSPF-like costs, the same in both directions
    "R1": {"R2": 10, "R3": 1},
    "R2": {"R1": 10, "R4": 1},
    "R3": {"R1": 1, "R4": 20, "R5": 2},
    "R4": {"R2": 1, "R3": 20, "R5": 1},
    "R5": {"R3": 2, "R4": 1},
}

def dijkstra(graph, source):
    dist = {source: 0}
    previous = {}
    queue = [(0, source)]
    while queue:
        d, node = heapq.heappop(queue)
        if d > dist[node]:
            continue                      # an outdated queue entry
        for neighbor, cost in graph[node].items():
            if d + cost < dist.get(neighbor, float("inf")):
                dist[neighbor] = d + cost
                previous[neighbor] = node
                heapq.heappush(queue, (d + cost, neighbor))
    return dist, previous

dist, previous = dijkstra(links, "R1")
for router in sorted(dist):
    path = [router]
    while path[-1] != "R1":
        path.append(previous[path[-1]])
    print(router, dist[router], " -> ".join(reversed(path)))

R1 0 R1
R2 5 R1 -> R3 -> R5 -> R4 -> R2
R3 1 R1 -> R3
R4 4 R1 -> R3 -> R5 -> R4
R5 3 R1 -> R3 -> R5

Where you meet it: OSPF

OSPF (Open Shortest Path First) is a link-state routing protocol: every router learns the complete map of its area and then runs Dijkstra's algorithm with itself as the start. The OSPF standard, RFC 2328, says so in section 16.1: using the Dijkstra algorithm, a tree is formed from the link-state database. The result is a shortest-path tree rooted at that router — the highlighted edges in the figure, seen from R1 — and the first hop of each path goes into the routing table. The networking page has its own Python sketch of SPF on a different topology.

Trees

In graph theory, a tree is a connected graph without cycles: there is exactly one path between any two vertices. (Programmers usually mean a rooted tree, in which one vertex is chosen as the root and every edge points from parent to child; see Data Structures.) Trees are everywhere in IT:

• File systems: folders inside folders, with the root at the top.
• DNS: the root, then top-level domains such as com, then example.com, then kestrel.example.com.
• Directory services: organizational units inside organizational units, as in Active Directory.
• Database indexes: the B-tree that keeps lookups fast.

A tree with n vertices always has exactly n - 1 edges. To see why, build the tree one vertex at a time: start with a single vertex and no edges, and attach each new vertex with exactly one edge (a second edge would create a cycle, no edge would leave it disconnected). After adding n - 1 vertices you have used n - 1 edges. Turned around, this gives a quick test: a graph is a tree exactly when it is connected and has n - 1 edges.

def is_tree(vertices, edges):
    neighbors = {v: set() for v in vertices}
    for a, b in edges:
        neighbors[a].add(b)
        neighbors[b].add(a)
    seen, stack = set(), [vertices[0]]          # walk from any vertex
    while stack:
        v = stack.pop()
        if v not in seen:
            seen.add(v)
            stack.extend(neighbors[v] - seen)
    return len(seen) == len(vertices) and len(edges) == len(vertices) - 1

switches = ["A", "B", "C", "D", "E"]
print(is_tree(switches, [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]))
print(is_tree(switches, [("A", "B"), ("A", "C"), ("B", "D"), ("D", "E")]))

False
True

The office network has 5 vertices and 5 edges, one too many for a tree: it contains the cycle A–B–D–C–A. Remove the C–D cable and what is left is a tree.

Spanning trees

A spanning tree of a connected graph is a tree that contains all of the graph's vertices and only some of its edges: just enough edges to keep everything connected, and not one more. A graph with n vertices needs n - 1 of its edges for that; the rest are left out. Most graphs have many different spanning trees.

Ethernet switches need exactly this. Redundant cables between switches create cycles, and a broadcast frame would circle such a loop forever. The Spanning Tree Protocol (STP) therefore keeps one spanning tree active and blocks the ports on every other link. Which tree? STP elects a root bridge (the switch with the lowest bridge ID), and every other switch keeps its cheapest path to that root. The result is a shortest-path tree toward the root — the same kind of tree Dijkstra's algorithm builds from a start vertex. The sketch below finds it for a meshed set of four switches in which every link has the same cost, so cheapest means fewest hops (a simplification: real STP breaks ties with bridge IDs and port IDs):

from collections import deque

links = [("SW1", "SW2"), ("SW1", "SW3"), ("SW2", "SW3"), ("SW2", "SW4"), ("SW3", "SW4")]
neighbors = {}
for a, b in links:
    neighbors.setdefault(a, []).append(b)
    neighbors.setdefault(b, []).append(a)

root = "SW1"                                  # elected root bridge
parent = {root: None}
queue = deque([root])
while queue:
    switch = queue.popleft()
    for n in sorted(neighbors[switch]):       # sorted: lowest name wins ties
        if n not in parent:
            parent[n] = switch
            queue.append(n)

tree = sorted(tuple(sorted((s, p))) for s, p in parent.items() if p)
blocked = sorted(set(tuple(sorted(link)) for link in links) - set(tree))
print("forwarding:", tree)
print("blocked:   ", blocked)
print(len(parent), "switches,", len(tree), "tree links")

forwarding: [('SW1', 'SW2'), ('SW1', 'SW3'), ('SW2', 'SW4')]
blocked:    [('SW2', 'SW3'), ('SW3', 'SW4')]
4 switches, 3 tree links

Four switches, three forwarding links: the n - 1 rule at work. If the SW1–SW2 cable fails, STP recalculates and one of the blocked links takes over.

Directed acyclic graphs and dependencies

A directed acyclic graph (DAG) is a directed graph in which you can never follow the arrows and come back to where you started: it has no directed cycles. Dependencies are the classic example. Kestrel's customer portal depends on an API and an authentication service, and both of those depend on the database. A cycle here would be a real problem — A waits for B, B waits for A, and neither can ever start.

A topological sort lists the vertices of a DAG so that every vertex comes after everything it depends on. It is the answer to "in which order can I start these services?" or "in which order must these packages be built?" — and it exists exactly when the graph has no cycle. Python's standard library has one in graphlib; asking for the vertices in "rounds" shows which services can start in parallel:

from graphlib import TopologicalSorter

depends_on = {
    "portal": {"api", "auth"},
    "api": {"database"},
    "auth": {"database"},
    "database": set(),
}
ts = TopologicalSorter(depends_on)
ts.prepare()
order = []
while ts.is_active():
    ready = sorted(ts.get_ready())
    order.append(ready)
    ts.done(*ready)
print(order)

[['database'], ['api', 'auth'], ['portal']]

If someone adds a dependency from the database back to the portal, the graph gets a cycle and prepare() raises a graphlib.CycleError naming the vertices involved — far better than a deployment that hangs.

DAGs turn up throughout IT: service start-up order (systemd unit dependencies), build systems and package managers, CI/CD pipeline stages, task schedulers, spreadsheets that recalculate cells in dependency order, and git history, where every commit points to its parent commits (see parent links). A merge commit has two parents, so git history is a DAG rather than a tree.