1JOHNSON(G):
2    // Find all elementary circuits in directed graph G
3    s = 1  // Start vertex (processes vertices in order)
4    while s < n:
5        // Build subgraph of G induced by vertices {s, s+1, ..., n}
6        Gsub = subgraph(G, {s, ..., n})
7
8        // Find strongly connected components (SCCs)
9        SCCs = TARJAN(Gsub)
10
11        // Find the SCC containing the smallest vertex
12        SCC_s = SCC containing vertex s (if any)
13
14        if SCC_s exists:
15            // Initialize blocking structures
16            for each v in SCC_s:
17                blocked[v] = false
18                B[v] = {}  // Empty set
19
20            CIRCUIT(s, s, SCC_s)
21
22        s = s + 1

1CIRCUIT(v, s, graph):
2    // v = current vertex, s = start vertex
3    f = false         // Did we find a cycle through v?
4    stack.push(v)
5    blocked[v] = true
6
7    for each w in adjacency[v]:
8        if w == s:
9            // Found a cycle! Output stack contents
10            OUTPUT(stack + [s])
11            f = true
12        else if not blocked[w]:
13            if CIRCUIT(w, s, graph):
14                f = true
15
16    if f:
17        UNBLOCK(v)    // Cycle found: unblock v for future searches
18    else:
19        // No cycle found through v
20        for each w in adjacency[v]:
21            if v not in B[w]:
22                B[w].add(v)  // Remember: if w is unblocked, unblock v too
23
24    stack.pop()
25    return f

1UNBLOCK(u):
2    blocked[u] = false
3    for each w in B[u]:
4        if blocked[w]:
5            UNBLOCK(w)   // Recursively unblock dependencies
6    B[u] = {}             // Clear the dependency set

1from collections import defaultdict
2
3def johnsons_algorithm(graph):
4    """Find all elementary cycles in a directed graph."""
5    def strong_connect(v, index_counter, stack, lowlinks, index, on_stack, sccs):
6        index[v] = index_counter[0]
7        lowlinks[v] = index_counter[0]
8        index_counter[0] += 1
9        stack.append(v)
10        on_stack[v] = True
11
12        for w in graph.get(v, []):
13            if w not in index:
14                strong_connect(w, index_counter, stack, lowlinks, index, on_stack, sccs)
15                lowlinks[v] = min(lowlinks[v], lowlinks[w])
16            elif on_stack.get(w, False):
17                lowlinks[v] = min(lowlinks[v], index[w])
18
19        if lowlinks[v] == index[v]:
20            scc = []
21            while True:
22                w = stack.pop()
23                on_stack[w] = False
24                scc.append(w)
25                if w == v:
26                    break
27            if len(scc) > 1 or (len(scc) == 1 and v in graph.get(v, [])):
28                sccs.append(scc)
29
30    def find_sccs(subgraph, vertices):
31        sccs = []
32        index = {}
33        lowlinks = {}
34        on_stack = {}
35        stack = []
36        index_counter = [0]
37        for v in vertices:
38            if v not in index:
39                strong_connect(v, index_counter, stack, lowlinks, index, on_stack, sccs)
40        return sccs
41
42    def circuit(v, s, adj, blocked, B, stack, cycles):
43        f = False
44        stack.append(v)
45        blocked[v] = True
46
47        for w in adj.get(v, []):
48            if w == s:
49                cycles.append(list(stack))
50                f = True
51            elif not blocked.get(w, False):
52                if circuit(w, s, adj, blocked, B, stack, cycles):
53                    f = True
54
55        if f:
56            unblock(v, blocked, B)
57        else:
58            for w in adj.get(v, []):
59                if v not in B[w]:
60                    B[w].add(v)
61
62        stack.pop()
63        return f
64
65    def unblock(u, blocked, B):
66        blocked[u] = False
67        for w in list(B[u]):
68            if blocked.get(w, False):
69                unblock(w, blocked, B)
70        B[u] = set()
71
72    vertices = sorted(graph.keys())
73    cycles = []
74
75    for s in vertices:
76        subgraph_vertices = [v for v in vertices if v >= s]
77        sub_adj = {v: [w for w in graph.get(v, []) if w >= s]
78                   for v in subgraph_vertices}
79
80        sccs = find_sccs(sub_adj, subgraph_vertices)
81        scc_with_s = None
82        for scc in sccs:
83            if s in scc:
84                scc_with_s = set(scc)
85                break
86
87        if scc_with_s:
88            adj = {v: [w for w in sub_adj.get(v, []) if w in scc_with_s]
89                   for v in scc_with_s}
90            blocked = {}
91            B = defaultdict(set)
92            stack = []
93            for v in scc_with_s:
94                blocked[v] = False
95            circuit(s, s, adj, blocked, B, stack, cycles)
96
97    return cycles
98
99# Usage
100graph = {
101    1: [2],
102    2: [3],
103    3: [1, 4],
104    4: [2]
105}
106
107cycles = johnsons_algorithm(graph)
108for c in cycles:
109    print(c)
110# [1, 2, 3]
111# [2, 3, 4]

1Step-by-step for graph: 1→2→3→1, 2→3→4→2
2
3Starting at s=1:
4  CIRCUIT(1, 1):
5    blocked[1] = true, stack = [1]
6    Visit 2:
7      CIRCUIT(2, 1):
8        blocked[2] = true, stack = [1, 2]
9        Visit 3:
10          CIRCUIT(3, 1):
11            blocked[3] = true, stack = [1, 2, 3]
12            Visit 1: w == s → CYCLE FOUND [1, 2, 3] ✓
13            Visit 4: CIRCUIT(4, 1)
14              blocked[4] = true, stack = [1, 2, 3, 4]
15              Visit 2: blocked → skip
16              No cycle → B[2].add(4)
17              stack = [1, 2, 3]
18            f = true → UNBLOCK(3)
19          f = true → UNBLOCK(2) → cascades to UNBLOCK(4)
20      f = true → UNBLOCK(1)
21
22Starting at s=2:
23  Subgraph: {2, 3, 4}
24  Finds cycle [2, 3, 4] ✓