chain.py

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]]