CODEWITHSUNDEEP
pythonalgorithm
Neil G
Neil G

Reputation: 33202

Python topological sort using lists indicating edges

Given lists: [1, 5, 6], [2, 3, 5, 6], [2, 5] etc. (not necessarily in any sorted order) such that if x precedes y in one list, then x precedes y in every list that have x and y, I want to find the list of all elements topologically sorted (so that x precedes y in this list if x precedes y in any other list.) There might be many solutions, in which case I want any of them.

What is the easiest way to implement this in Python.

Upvotes: 6

Views: 1852

Answers (3)

Aric
Aric

Reputation: 25289

Here is a slightly simpler version of @unutbu's networkx solution:

import networkx as nx
data=[[1, 5, 6], [2, 3, 5, 6], [2, 5], [7]]
G = nx.DiGraph()
for path in data:
    G.add_nodes_from(path)
    G.add_path(path)
ts=nx.topological_sort(G)
print(ts)
# [7, 2, 3, 1, 5, 6]

Upvotes: 8

unutbu
unutbu

Reputation: 879231

Using networkx, and in particular, networkx.topological_sort:

import networkx as nx

data=[[1, 5, 6], [2, 3, 5, 6], [2, 5], [7]]
G=nx.DiGraph()
for row in data:
    if len(row)==1:
        G.add_node(row[0])
    else:
        for v,w in (row[i:i+2] for i in xrange(0, len(row)-1)):
            G.add_edge(v,w)


ts=nx.topological_sort(G)
print(ts)
# [2, 3, 1, 5, 6]

Upvotes: 6

Neil G
Neil G

Reputation: 33202

My solution (using some code from @unutbu)

import collections

retval = []
data = [[1,2,3], [4,5,6], [2, 5], [3, 6], [1, 7]]
in_edges = collections.defaultdict(set)
out_edges = collections.defaultdict(set)
vertices = set()
for row in data:
    vertices |= set(row)
    while len(row) >= 2:
        w = row.pop()
        v = row[-1]
        in_edges[w].add(v)
        out_edges[v].add(w)
def process(k):
    vertices.remove(k)
    retval.append(k)
    for target in out_edges[k]:
        in_edges[target].remove(k)
    for target in out_edges[k]:
        if not in_edges[target]:
            process(target)
    out_edges[k] = set()

while vertices:  # ideally, this should be a heap
    for k in vertices:
        if not in_edges[k]:
            process(k)
            break

print(retval)

Upvotes: 0

Related Questions