Graphs and graph search

Ridgeline's wholesale deliveries now cover a small network of places: the roastery, the cafe, a warehouse, and cafes, bakeries and hotels around town, connected by roads with known drive times. Theo wants answers to questions such as: which customers can the van reach without passing the bridge that is closed for repairs? What is the route with the fewest stops from the roastery to the Alder Hotel? And what is the quickest route in minutes? None of these fits a list or a tree, because places connect to each other in every direction. They are questions about a graph.

Graphs model anything made of things and connections between them: road networks, social networks, links between web pages, dependencies between tasks and the flow of goods through a supply chain. This lesson introduces graph vocabulary, two standard ways to store a graph, and the three fundamental graph algorithms: breadth-first search, depth-first search and Dijkstra's shortest-path algorithm, all built from the stacks, queues, sets and heaps of earlier lessons.

Graph vocabulary

A graph is a set of vertices (also called nodes) and a set of edges, each connecting two vertices. In an undirected graph, edges work both ways, like a two-way road. In a directed graph, each edge has a direction, like a one-way street or a task that must come before another. A weighted graph gives each edge a number, such as a drive time or a distance. Two vertices joined by an edge are neighbors, and the number of edges at a vertex is its degree. A path is a sequence of vertices joined by edges, and a cycle is a path that returns to where it started. Trees, from lesson 9, are simply connected graphs with no cycles.

Storing a graph

The most common representation in Python is an adjacency list: a dictionary that maps each vertex to its neighbors. For an unweighted graph, the neighbors can be a list or a set; for a weighted graph, a dictionary from neighbor to weight. An adjacency list uses space proportional to the number of vertices plus edges, written O(V + E), and lists a vertex's neighbors quickly, which is what graph algorithms need most.

The alternative is an adjacency matrix, a V by V grid where entry [i][j] holds the weight of the edge from vertex i to vertex j, or nothing if there is none. Checking whether a particular edge exists is O(1), but the matrix needs O(V²) space even if most pairs are not connected. Road networks, like most real graphs, are sparse, with far fewer edges than possible pairs, so adjacency lists are the usual choice.

from collections import defaultdict

roads = [("Roastery", "Cafe", 6), ("Roastery", "Warehouse", 9), ("Cafe", "Lakeview Cafe", 12),
         ("Warehouse", "Bayside Bakery", 7), ("Bayside Bakery", "Alder Hotel", 10),
         ("Lakeview Cafe", "Alder Hotel", 15), ("Warehouse", "Pine St Deli", 14),
         ("Pine St Deli", "Hilltop Market", 8), ("Cafe", "Warehouse", 5)]

graph = defaultdict(dict)
for a, b, minutes in roads:
    graph[a][b] = minutes             # undirected: add both directions
    graph[b][a] = minutes

print(sorted(graph["Warehouse"].items()))
print("degree of Cafe:", len(graph["Cafe"]))
print("vertices:", len(graph), "edges:", sum(len(n) for n in graph.values()) // 2)

[('Bayside Bakery', 7), ('Cafe', 5), ('Pine St Deli', 14), ('Roastery', 9)]
degree of Cafe: 3
vertices: 8 edges: 9

def build_graph(edges):
    graph = {}
    for a, b in edges:
        graph[a] = [b]
    return graph

print(build_graph([('Roastery', 'Cafe'), ('Cafe', 'Warehouse')]))

Breadth-first search

Breadth-first search (BFS) explores a graph outward from a starting vertex in layers: first the start, then all its neighbors, then all their unvisited neighbors, and so on. A queue keeps the layers in order, exactly as in the level-order tree traversal of lesson 9, and a set of visited vertices stops the search from going round in cycles. Because BFS reaches every vertex by the smallest possible number of edges, it finds the route with the fewest stops in an unweighted graph. Recording each vertex's parent, the vertex it was discovered from, lets you rebuild the route afterward.

from collections import deque

graph = {
    "Roastery": ["Cafe", "Warehouse"], "Cafe": ["Roastery", "Lakeview Cafe", "Warehouse"],
    "Warehouse": ["Roastery", "Cafe", "Bayside Bakery", "Pine St Deli"],
    "Lakeview Cafe": ["Cafe", "Alder Hotel"], "Bayside Bakery": ["Warehouse", "Alder Hotel"],
    "Alder Hotel": ["Lakeview Cafe", "Bayside Bakery"], "Pine St Deli": ["Warehouse", "Hilltop Market"],
    "Hilltop Market": ["Pine St Deli"],
}

def fewest_stops(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        place = queue.popleft()
        if place == goal:
            route = []
            while place is not None:          # walk the parents back to the start
                route.append(place)
                place = parent[place]
            return route[::-1]
        for nxt in graph[place]:
            if nxt not in parent:             # parent doubles as the visited set
                parent[nxt] = place
                queue.append(nxt)
    return None

print(fewest_stops(graph, "Roastery", "Alder Hotel"))
print(fewest_stops(graph, "Hilltop Market", "Lakeview Cafe"))

['Roastery', 'Cafe', 'Lakeview Cafe', 'Alder Hotel']
['Hilltop Market', 'Pine St Deli', 'Warehouse', 'Cafe', 'Lakeview Cafe']

Each vertex is added to the queue at most once and each edge is examined at most twice, so BFS runs in O(V + E) time. Marking a vertex as visited when it is added to the queue, rather than when it is removed, matters: otherwise the same vertex could be queued many times through different neighbors.

def stops_from(graph, start):
    return {place: 1 for place in graph[start]}

print(stops_from(net, 'Roastery'))

Depth-first search

Depth-first search (DFS) explores as far as possible along one branch before backing up and trying the next, like walking a maze by keeping one hand on the wall. It can be written recursively, with the call stack doing the bookkeeping, or with an explicit stack, as below. DFS also runs in O(V + E), but it does not find the fewest stops. Its strengths are other questions: whether a vertex can be reached at all, how a graph splits into connected pieces, whether it contains a cycle, and putting tasks in dependency order.

def reachable(graph, start, closed=frozenset()):
    """Every place reachable from start without using a closed place."""
    seen, stack = {start}, [start]
    while stack:
        place = stack.pop()
        for nxt in graph[place]:
            if nxt not in seen and nxt not in closed:
                seen.add(nxt)
                stack.append(nxt)
    return seen

graph = {
    "Roastery": ["Cafe", "Warehouse"], "Cafe": ["Roastery", "Lakeview Cafe", "Warehouse"],
    "Warehouse": ["Roastery", "Cafe", "Bayside Bakery", "Pine St Deli"],
    "Lakeview Cafe": ["Cafe", "Alder Hotel"], "Bayside Bakery": ["Warehouse", "Alder Hotel"],
    "Alder Hotel": ["Lakeview Cafe", "Bayside Bakery"], "Pine St Deli": ["Warehouse", "Hilltop Market"],
    "Hilltop Market": ["Pine St Deli"],
}
everywhere = reachable(graph, "Roastery")
with_closure = reachable(graph, "Roastery", closed={"Pine St Deli"})
print(len(everywhere), "places reachable")
print("cut off by the closure:", sorted(everywhere - with_closure))

8 places reachable
cut off by the closure: ['Hilltop Market', 'Pine St Deli']

Swapping the stack for a queue turns this code into BFS; the difference between the two searches is entirely the order in which waiting vertices are taken. With Pine St Deli closed, Hilltop Market can no longer be reached, so Theo knows to call that customer before loading the van.

Ordering tasks: topological sort

Directed graphs often describe dependencies. Before a batch can be bagged, it must be roasted; before roasting, the green beans must be weighed and the roaster preheated; labels must be printed before bagging. A topological order lists the tasks so that every task comes after all the tasks it depends on. One classic method, Kahn's algorithm, repeatedly takes a task with no unfinished prerequisites, using a queue and a count of remaining prerequisites for each task. If tasks are left over at the end, the dependencies contain a cycle, and no valid order exists.

from collections import deque

needs = {                                    # task -> tasks that must happen first
    "weigh beans": [], "preheat roaster": [], "print labels": [],
    "roast": ["weigh beans", "preheat roaster"],
    "cool": ["roast"],
    "bag": ["cool", "print labels"],
}

def task_order(needs):
    waiting = {task: len(before) for task, before in needs.items()}
    unlocks = {task: [] for task in needs}
    for task, before in needs.items():
        for b in before:
            unlocks[b].append(task)
    ready = deque(sorted(t for t, n in waiting.items() if n == 0))
    order = []
    while ready:
        task = ready.popleft()
        order.append(task)
        for nxt in unlocks[task]:
            waiting[nxt] -= 1
            if waiting[nxt] == 0:
                ready.append(nxt)
    if len(order) < len(needs):
        raise ValueError("the dependencies contain a cycle")
    return order

print(task_order(needs))

['preheat roaster', 'print labels', 'weigh beans', 'roast', 'cool', 'bag']

Shortest paths with Dijkstra's algorithm

BFS counts stops, but Theo cares about minutes, and a route with more stops can be quicker. In a weighted graph with no negative weights, Dijkstra's algorithm, published by Edsger Dijkstra in 1959, finds the quickest route from a start to every other vertex. It keeps the best known time to each vertex and repeatedly settles the unsettled vertex with the smallest known time, which is exactly the job of the priority queue from lesson 10. When a vertex is settled, its time is final, and the algorithm checks whether going through it improves the times of its neighbors.

import heapq

graph = {
    "Roastery": {"Cafe": 6, "Warehouse": 9}, "Cafe": {"Roastery": 6, "Lakeview Cafe": 12, "Warehouse": 5},
    "Warehouse": {"Roastery": 9, "Cafe": 5, "Bayside Bakery": 7, "Pine St Deli": 14},
    "Lakeview Cafe": {"Cafe": 12, "Alder Hotel": 15}, "Bayside Bakery": {"Warehouse": 7, "Alder Hotel": 10},
    "Alder Hotel": {"Lakeview Cafe": 15, "Bayside Bakery": 10},
    "Pine St Deli": {"Warehouse": 14, "Hilltop Market": 8}, "Hilltop Market": {"Pine St Deli": 8},
}

def quickest(graph, start, goal):
    best = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        minutes, place = heapq.heappop(heap)
        if place == goal:
            route = []
            while place is not None:
                route.append(place)
                place = parent[place]
            return minutes, route[::-1]
        if minutes > best[place]:
            continue                                  # an out-of-date entry: skip it
        for nxt, drive in graph[place].items():
            t = minutes + drive
            if t < best.get(nxt, float("inf")):
                best[nxt] = t
                parent[nxt] = place
                heapq.heappush(heap, (t, nxt))
    return None

print(quickest(graph, "Roastery", "Alder Hotel"))
print(quickest(graph, "Lakeview Cafe", "Hilltop Market"))

(26, ['Roastery', 'Warehouse', 'Bayside Bakery', 'Alder Hotel'])
(39, ['Lakeview Cafe', 'Cafe', 'Warehouse', 'Pine St Deli', 'Hilltop Market'])

The skipped out-of-date entries are the lazy deletion idea from lesson 10: instead of updating a vertex's entry in the heap, the code pushes a new, better entry and ignores the old one when it surfaces. With a binary heap, Dijkstra's algorithm runs in O((V + E) log V). Mapping apps use refined versions of it, with extra tricks to search millions of road segments quickly. If some weights can be negative, such as a route that earns a refund, Dijkstra's algorithm can give wrong answers, and slower algorithms such as Bellman-Ford are needed.

def unreachable(graph, start):
    return sorted(p for p in graph if p not in graph[start] and p != start)

print(unreachable(net, 'Roastery'))