Python topological sorting using lists specifying edges

Question

These lists: [1, 5, 6], [2, 3, 5, 6], [2, 5], etc. (not necessarily in any sorted order) that if x precedes y in one list, then x precedes y in each list with x and y, I want to find a list of all topologically sorted elements (so x precedes y in this list, if x is preceded by y in any other list.) There can be many solutions in which I want any of them.

What is the easiest way to implement this in Python.

Answer 1

Here is a slightly simpler version of @unutbu 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] 

Answer 2

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] 

Answer 3

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)