Skip to content

Instantly share code, notes, and snippets.

@pervognsen
Last active December 23, 2018 08:38
Show Gist options
  • Save pervognsen/ab5a85c56fe7240d701cc286481b36c5 to your computer and use it in GitHub Desktop.
Save pervognsen/ab5a85c56fe7240d701cc286481b36c5 to your computer and use it in GitHub Desktop.
def chain_decomposition(graph):
up = {}
down = {}
order = {} # Assumes Python 3.6+ insertion-ordered dictionaries
def dfs(v):
order[v] = len(order)
down[v] = []
for w in graph[v]:
if w in up:
if order[w] < order[v] and up[v] != w:
down[w].append(v)
else:
up[w] = v
dfs(w)
roots = []
for v in graph:
if v not in up:
roots.append(v)
up[v] = None
dfs(v)
visited = set()
chains = []
for v in order:
visited.add(v)
for w in down[v]:
chain = [v]
while w not in visited:
visited.add(w)
chain.append(w)
w = up[w]
chain.append(w)
chains.append(chain)
return chains
graph = {
1: [2, 3, 4],
2: [3, 5, 1],
3: [4, 5, 1, 2],
4: [1, 3],
5: [6, 9, 10, 2, 3],
6: [7, 8, 5],
7: [8, 6],
8: [6, 7],
9: [10, 5],
10: [5, 9],
}
chains = chain_decomposition(graph)
print(chains) # [[1, 4, 3, 2, 1], [1, 3], [2, 5, 3], [5, 10, 9, 5], [6, 8, 7, 6]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment