Skip to content

Instantly share code, notes, and snippets.

@jbartolozzi
Forked from kachayev/topological.py
Created July 22, 2016 17:56
Show Gist options
  • Save jbartolozzi/e5165f3134cb859dbd67d6f750882e92 to your computer and use it in GitHub Desktop.
Save jbartolozzi/e5165f3134cb859dbd67d6f750882e92 to your computer and use it in GitHub Desktop.
Topological sort with Python (using DFS and gray/black colors)
# Simple:
# a --> b
# --> c --> d
# --> d
graph1 = {
"a": ["b", "c", "d"],
"b": [],
"c": ["d"],
"d": []
}
# 2 components
graph2 = {
"a": ["b", "c", "d"],
"b": [],
"c": ["d"],
"d": [],
"e": ["g", "f", "q"],
"g": [],
"f": [],
"q": []
}
# cycle
graph3 = {
"a": ["b", "c", "d"],
"b": [],
"c": ["d", "e"],
"d": [],
"e": ["g", "f", "q"],
"g": ["c"],
"f": [],
"q": []
}
from collections import deque
GRAY, BLACK = 0, 1
def topological(graph):
order, enter, state = deque(), set(graph), {}
def dfs(node):
state[node] = GRAY
for k in graph.get(node, ()):
sk = state.get(k, None)
if sk == GRAY: raise ValueError("cycle")
if sk == BLACK: continue
enter.discard(k)
dfs(k)
order.appendleft(node)
state[node] = BLACK
while enter: dfs(enter.pop())
return order
# check how it works
print topological(graph1)
print topological(graph2)
try: topological(graph3)
except ValueError: print "Cycle!"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment