Graph algorithms: BFS, DFS, topological order

A graph is nodes and edges. AI-grafen's knowledge map is a graph: 509 nodes and 850 prerequisite relations.

Two ways of going through it:

The difference is a single line: take from the front of the collection (a queue) and you get BFS, take from the back (a stack) and you get DFS.

A topological order is the most important one for this platform: an order where every node comes after all its prerequisites. That is exactly what a learning path is.

It exists if and only if the graph is acyclic. A cycle — A requires B which requires A — means that no order is possible, and that is precisely what graph_invariants.py checks.

Kahn's algorithm for a topological order:

1. Count how many incoming edges each node has (its in-degree).
2. Put every node with in-degree 0 in a queue.
3. Take a node, put it in the result, decrease the in-degree of its neighbours.
4. If a neighbour reaches 0, put it in the queue.
5. Repeat.

If the result contains fewer nodes than the graph, there is a cycle — the missing nodes are part of it. That makes Kahn's algorithm both a sorter and a cycle detector in one, which is why it is used in tools.graph_invariants.

The complexity is $O(V + E)$ for all three algorithms.

Four applications in this platform:

The last is the graph invariant: every published node has to be reachable from at least one goal.

Weighted graphs require more. If the edges have a cost — estimated time per node, for instance — BFS no longer gives the shortest path. Then you need Dijkstra (non-negative weights, with a priority queue) or, in a DAG, a topological order followed by a single pass, which is both simpler and faster.

The last is worth remembering: in a DAG the shortest and the longest path are easy — just relax the edges in topological order. In a general graph the longest path is NP-hard.

from collections import deque, defaultdict

def bfs(graph, start):
    """The visited nodes in order, plus the distance from the start."""
    visited, distance, queue = [start], {start: 0}, deque([start])
    while queue:
        n = queue.popleft()                 # popleft → BFS
        for g in graph.get(n, []):
            if g not in distance:
                distance[g] = distance[n] + 1
                visited.append(g); queue.append(g)
    return visited, distance

def dfs(graph, start):
    visited, stack = [], [start]
    seen = {start}
    while stack:
        n = stack.pop()                     # pop → DFS. The only difference.
        visited.append(n)
        for g in reversed(graph.get(n, [])):
            if g not in seen:
                seen.add(g); stack.append(g)
    return visited

def topological(graph):
    """Kahn's algorithm. Returns (order, cyclic_nodes)."""
    nodes = set(graph) | {g for gs in graph.values() for g in gs}
    indegree = dict.fromkeys(nodes, 0)
    for n in graph:
        for g in graph[n]:
            indegree[g] += 1
    queue = deque(sorted(n for n in nodes if indegree[n] == 0))
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for g in graph.get(n, []):
            indegree[g] -= 1
            if indegree[g] == 0:
                queue.append(g)
    cyclic = sorted(nodes - set(order))
    return order, cyclic

# A small learning path: the edge a → b means "a is a prerequisite for b"
course = {
    "arithmetic": ["algebra"],
    "algebra": ["equations", "functions"],
    "equations": ["derivatives"],
    "functions": ["derivatives"],
    "derivatives": ["gradient descent"],
}
order, cycles = topological(course)
print(order)
# ['arithmetic', 'algebra', 'equations', 'functions', 'derivatives', 'gradient descent']
print("cycles:", cycles or "none")

_, distance = bfs(course, "arithmetic")
print(distance)   # {'arithmetic': 0, 'algebra': 1, 'equations': 2, 'functions': 2, ...}

# A cycle shows up as the order being too short
broken = {"a": ["b"], "b": ["c"], "c": ["a"]}
order, cycles = topological(broken)
print(order, cycles)            # [] ['a', 'b', 'c']

# The longest path in a DAG — easy, thanks to the topological order
def longest_path(graph, time):
    order, _ = topological(graph)
    longest = {n: time.get(n, 0) for n in order}
    for n in order:
        for g in graph.get(n, []):
            longest[g] = max(longest[g], longest[n] + time.get(g, 0))
    return max(longest.items(), key=lambda kv: kv[1])

time = {k: 45 for k in ("arithmetic", "algebra", "equations", "functions",
                        "derivatives", "gradient descent")}
print(longest_path(course, time))    # ('gradient descent', 180) — 4 nodes at 45 min