Topological sort python
20,715
Solution 1
FWIW, here is some code I worked up for a non-recursive topological sort.
from collections import defaultdict, namedtuple
from itertools import islice
Results = namedtuple('Results', ['sorted', 'cyclic'])
def topological_sort(dependency_pairs):
'Sort values subject to dependency constraints'
num_heads = defaultdict(int) # num arrows pointing in
tails = defaultdict(list) # list of arrows going out
heads = [] # unique list of heads in order first seen
for h, t in dependency_pairs:
num_heads[t] += 1
if h in tails:
tails[h].append(t)
else:
tails[h] = [t]
heads.append(h)
ordered = [h for h in heads if h not in num_heads]
for h in ordered:
for t in tails[h]:
num_heads[t] -= 1
if not num_heads[t]:
ordered.append(t)
cyclic = [n for n, heads in num_heads.items() if heads]
return Results(ordered, cyclic)
if __name__ == '__main__':
print( topological_sort('aa'.split()) )
print( topological_sort('ah bg cf ch di ed fb fg hd he ib'.split()) )
Solution 2
from collections import defaultdict, deque
class Graph:
def __init__(self, directed=False, nodes=None, edges=None):
self.graph = defaultdict(list)
self.directed = directed
self.add_nodes(nodes)
self.add_edges(edges)
@property
def nodes(self):
if not self.directed:
return list(self.graph.keys())
elif self.directed:
nodes = set()
nodes.update(self.graph.keys())
for node in self.graph.keys():
for neighbor in self.graph[node]:
nodes.add(neighbor)
return list(nodes)
def add_node(self, node):
if node not in self.nodes:
self.graph[node] = list()
def add_nodes(self, nodes):
if nodes is None:
return None
for node in nodes:
self.add_node(node)
@property
def edges(self):
edges = list()
for source, neighbors in self.graph.items():
for neighbor in neighbors:
edges.append((source, neighbor))
return edges
def add_edge(self, edge):
node1, node2 = edge
self.graph[node1].append(node2)
if not self.directed:
self.graph[node2].append(node1)
def add_edges(self, edges):
if edges is None:
return None
for edge in edges:
self.add_edge(edge)
def topological_util(self, node, visited, label):
visited[node] = True
for edge in self.graph[node]:
if not visited[edge]:
self.topological_util(edge, visited, label)
label.appendleft(node)
def topological_sort(self):
visited = dict.fromkeys(self.nodes, False)
# store all nodes in topological order, the index is the position
label = deque()
for node in self.nodes:
if not visited[node]:
self.topological_util(node, visited, label)
return label
Author by
badc0re
Updated on November 06, 2020Comments
-
badc0re over 3 years
I coded a solution for DFS non-recursive, but i can't modify it to make a topological sort:
def dfs(graph,start): path = [] stack = [start] while stack != []: v = stack.pop() if v not in path: path.append(v) for w in reversed(graph[v]): if w not in path and not w in stack: stack.append(w) return path
Any ideas how to modify it?
With the recursive version i can easy have the sorting:
def dfs_rec(graph,start,path): path = path + [start] for edge in graph[start]: if edge not in path: path = dfs_rec(graph, edge,path) print start return path
Input:
>>> graph = { 1: [2, 3], 2: [4, 5, 6], 3: [4,6], 4: [5,6], 5: [6], 6: [] } >>> dfs_rec(graph,1,[]) 6 5 4 2 3 1 [1, 2, 4, 5, 6, 3] >>> dfs(graph,1) [1, 2, 4, 5, 6, 3] >>> graph = { 1: [3], 3: [5,6], 5: [4], 4: [7], 7: [], 6: [] } >>> print dfs_rec(graph,1,[]) 7 4 5 6 3 1 [1, 3, 5, 4, 7, 6] >>> print dfs(graph,1) [1, 3, 5, 4, 7, 6]
so i need to get this ordering in the non-recursive also.
Non-recursive solution:
I think that this also could be the solution, mark me if i am wrong.
def dfs(graph,start): path = [] stack = [start] label = len(graph) result = {} while stack != []: #this for loop could be done in other ways also for element in stack: if element not in result: result[element] = label label = label - 1 v = stack.pop() if v not in path: path.append(v) for w in reversed(graph[v]): if w not in path and not w in stack: stack.append(w) result = {v:k for k, v in result.items()} return path,result
Input:
graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]} print dfs(graph,1)
Output:
([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1}) 1 / 3 /\ 5 6 / 4 / 7
-
ovgolovin about 11 yearsCould you give an example of input?
-
Eric about 11 yearsWhat's the problem here? In both cases, the return value of
dfs_rec
matches that ofdfs
. What results do you want instead? -
badc0re about 11 yearsYes the result matches, but in dfs_rec when the recursion ends it gives me the (by print start) the topological ordering of the graph, so now i want to make a topological ordering on the non-recursive function (dfs) but i could not succeed in doing it.
-
Eric about 11 yearsSo you want both functions to return
[7, 4, 5, 6, 3, 1]
in the second case? -
badc0re about 11 years[6, 5, 4, 2, 3, 1] and [7, 4, 5, 6, 3, 1] for dfs(graph,1) the non-recursive function. As you can see i already have it for the first function dfs_rec.
-
Rob Cowie about 11 yearsUnless this is an academic exercise don't reinvent the wheel, use NetworkX, it's awesome
-
badc0re about 11 yearsYeah it is academic exercise, of course i would probably use something that is already coded.
-