An Implementation of a Depth-first search-based algorithm for finding a Topological order for a Directed acyclic graph in Python.

``````from random import choice
from itertools import count
from dataclasses import dataclass, field
from typing import Mapping, List, TypeVar, Generic

T = TypeVar('T')
VertexId = int

@dataclass
class Vertex(Generic[T]):
value: T
id: VertexId = field(default_factory=count().__next__)

def topological_sort(adjacency_list: Mapping[VertexId, List[VertexId]]) -> List[VertexId]:
"""Return a topological ordering of ADJACENCY_LIST."""

evaluated = set()
evaluating = set()
topological_order = []

def visit(id: VertexId) -> None:
if id in evaluated:
return

if id in evaluating:
raise Exception(f"Provided adjacency list contains a cycle including {id}")

visit(neighbor_id)

evaluating.remove(id)
topological_order.insert(0, id)

visit(id)

a = Vertex(value='a') # 0
b = Vertex(value='b') # 1
c = Vertex(value='c') # 2
d = Vertex(value='d') # 3
e = Vertex(value='e') # 4
f = Vertex(value='f') # 5
a.id: [d.id],
b.id: [d.id],
c.id: [d.id],
d.id: [e.id],
e.id: [f.id],
}
print(topological_sort(adjacency_list), 'should be [(2,1,0 in any order), 3, 4, 5]')
``````