Lessons · Python · graphs (things joined to things)

Things joined to things

A graph in Python is usually a dict from each node to the list of nodes it joins. Unlike a tree it can contain cycles, so every walk needs a set of what it has already seen.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

Followers, routes, dependencies, imports, friend suggestions, deadlocks. A surprising share of hard-looking problems are a graph once you notice what the nodes and the edges are.

How to think about it

Name the nodes and the edges out loud before writing anything. Then pick the walk: fewest steps means breadth-first with a queue; 'is there any route' or 'explore everything' means depth-first. Add the seen set before you add anything else.

Worked example

from collections import deque

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

d joins back to a: a cycle.

def hops(start, goal):

Fewest edges from start to goal.

    q, seen = deque([(start, 0)]), {start}

The seen set is what stops the cycle.

    while q:

        node, dist = q.popleft()

Front of the queue: nothing nearer is waiting.

        if node == goal: return dist

First arrival is by a shortest route.

        for nxt in graph[node]:

            if nxt not in seen:

Without this line, a -> b -> d -> a forever.

                seen.add(nxt); q.append((nxt, dist + 1))

    return None

No route at all.

print(hops('a', 'd'), hops('a', 'a'))

2 0

Your turn

Stop the walk revisiting a node and looping forever.

for nxt in graph[node]:
    if nxt not in :
        seen.add(nxt)
        q.append(nxt)

The trap

Depth-first finds A route, not the shortest. Reaching for it when the question says 'fewest' gives an answer that is plausible, larger than the truth, and passes small tests.

Practise graphs (things joined to things) on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.