def validate_graph(graph, weighted=False, nonnegative=False): if not isinstance(graph, dict): raise ValueError("Expected an adjacency dictionary") if any(not isinstance(vertex, str) for vertex in graph): raise ValueError("String vertex labels required") for vertex, neighbors in graph.items(): for edge in neighbors: if weighted: target, weight = edge if type(weight) is not int or (nonnegative and weight < 0): raise ValueError("Invalid integer edge weight") else: target = edge if target not in graph: raise ValueError("Unknown target vertex") from collections import deque def topological_order(graph): validate_graph(graph) incoming = {vertex: 0 for vertex in graph} for neighbors in graph.values(): for target in neighbors: incoming[target] += 1 pending = deque(vertex for vertex in graph if incoming[vertex] == 0) result = [] while pending: vertex = pending.popleft() result.append(vertex) for target in graph[vertex]: incoming[target] -= 1 if incoming[target] == 0: pending.append(target) if len(result) != len(graph): raise ValueError("Directed cycle prevents an ordering") return result graph = {"collect": ["clean"], "clean": ["report"], "report": [], "label": []} print(topological_order(graph)) try: topological_order({"a": ["b"], "b": ["a"]}) except ValueError as error: print(error)