toposort.py

import collections

dictionary = """ab
ac
b
xe
e
df
dx
de
c
ceb
cef
cee""".splitlines()


def build_graph(D):
    D = list(D)
    graph = []
    word1 = D.pop(0)
    while D:
        word2 = D.pop(0)
        for x, y in zip(word1, word2):
            if x == y:
                continue
            pair = (x, y)
            if pair not in graph:
                graph.append(pair)
                break
        word1 = word2
    return graph


def toposort(pairlist):
    predecessors = {}
    successors = collections.defaultdict(list)

    for a, b in pairlist:
        if a not in predecessors:
            predecessors[a] = 0
        if b not in predecessors:
            predecessors[b] = 0

        predecessors[b] += 1
        successors[a].append(b)


    answer = filter(lambda x: predecessors[x] == 0, predecessors)

    for x in answer:
        del predecessors[x]
        for y in successors[x]:
            predecessors[y] -= 1
            if predecessors[y] == 0:
                answer.append(y)
        del successors[x]

    if predecessors:
        raise Exception("Cycle")

    return answer

graph = build_graph(dictionary)
print graph
print
print toposort(graph)