This is the payoff. A package manager must install dependencies before the packages that need them. A topological sort produces exactly such an order: for every edge u -> v, u appears before v.
We use Kahn's algorithm:
When several nodes are ready at once, many valid orders exist. To stay deterministic, always break ties by insertion order of nodes (the order they first appeared via add_edge).
Implement topological_sort() returning the ordered list.
g.add_edge("a", "b")
g.add_edge("a", "c")
g.add_edge("b", "d")
g.add_edge("c", "d")
g.topological_sort() -> ["a", "b", "c", "d"]
from collections import deque
class Graph:
def __init__(self):
self.adj = {}
def add_edge(self, u, v):
if u not in self.adj:
self.adj[u] = []
if v not in self.adj:
self.adj[v] = []
self.adj[u].append(v)
def nodes(self):
return list(self.adj.keys())
def neighbors(self, u):
return self.adj.get(u, [])
def bfs(self, start):
seen = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nb in self.adj.get(node, []):
if nb not in seen:
seen.add(nb)
queue.append(nb)
return order
def dfs(self, start):
order = []
seen = set()
def visit(node):
if node in seen:
return
seen.add(node)
order.append(node)
for nb in self.adj.get(node, []):
visit(nb)
visit(start)
return order
def topological_sort(self):
"""Return a valid install order via Kahn's algorithm.
For every edge u -> v, u must appear before v. When several nodes are
ready at once, break ties by insertion order of nodes.
"""
# TODO: compute in-degree for every node, collect the in-degree-0
# nodes as "available", then repeatedly take the earliest-inserted
# available node, output it, and decrement its neighbors' in-degrees,
# adding any that reach 0. Return the output list.
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
This is the payoff. A package manager must install dependencies before the packages that need them. A topological sort produces exactly such an order: for every edge u -> v, u appears before v.
We use Kahn's algorithm:
When several nodes are ready at once, many valid orders exist. To stay deterministic, always break ties by insertion order of nodes (the order they first appeared via add_edge).
Implement topological_sort() returning the ordered list.
g.add_edge("a", "b")
g.add_edge("a", "c")
g.add_edge("b", "d")
g.add_edge("c", "d")
g.topological_sort() -> ["a", "b", "c", "d"]
Press Run Tests or ⌘↩ to check your solution.