Graphs

Graphs#

Python has no stdlib graph type; represent a graph as a dict[node, list[node]] (adjacency list) or dict[node, dict[node, weight]] for weighted graphs.

Representation#

graph = {
    "a": ["b", "c"],
    "b": ["d"],
    "c": ["d", "e"],
    "d": ["e"],
    "e": [],
}

BFS (shortest-hop)#

from collections import deque

def bfs(graph, start, goal):
    q = deque([(start, [start])])
    seen = {start}
    while q:
        node, path = q.popleft()
        if node == goal:
            return path
        for n in graph[node]:
            if n not in seen:
                seen.add(n)
                q.append((n, path + [n]))
    return None

DFS (recursive)#

def dfs(graph, start, goal, seen=None):
    seen = seen or set()
    seen.add(start)
    if start == goal:
        return [start]
    for n in graph[start]:
        if n not in seen:
            sub = dfs(graph, n, goal, seen)
            if sub:
                return [start] + sub
    return None

Dijkstra (shortest path, non-negative weights)#

import heapq

def dijkstra(graph, start):
    """graph: {node: {neighbor: weight}}. Returns {node: distance}."""
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist.get(node, float("inf")):
            continue
        for nb, w in graph[node].items():
            nd = d + w
            if nd < dist.get(nb, float("inf")):
                dist[nb] = nd
                heapq.heappush(pq, (nd, nb))
    return dist

Topological sort#

Use graphlib.TopologicalSorter (stdlib, 3.9+).

from graphlib import TopologicalSorter

ts = TopologicalSorter({
    "build": {"compile"},
    "test":  {"build"},
    "ship":  {"test"},
    "compile": set(),
})
list(ts.static_order())     # ['compile', 'build', 'test', 'ship']

TopologicalSorter.prepare() raises CycleError if the graph has a cycle.

References#

Contents