Python topological type

Question

I have encoded a solution for non-recursive DFS, but I cannot change it to do topological sorting:

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 on how to change it?

With the recursive version, I can easily sort:

 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 also get this order in non-recursive.

Non-recursive solution:

I think this could also be a solution, tag me if I'm 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 

Answer 1

FWIW, here is some code that I processed for non-recursive topological sorting.

 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()) ) 

Answer 2

  #this algorithm gives the logic of topological sorting..if u want to run this #give adjacency mat of your choice and this algorithm works on graph elements ranging from 0 to na=[[0,0,1,0,0,0],[0,0,1,0,0,0],[0,0,0,1,1,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,1,0,0,0]] vis=[0 for i in range(0,len(a))] s=[] orderstack=[]#stores the reverse order of topological sorted elements def dfs_for_topological_sorting(a,vis,i): vis[i]=1 x=0 for j in range(0,len(a[0])): if(a[i][j]==1 and vis[j]==0): x=1 s.append(j) #print(s) dfs_for_topological_sorting(a,vis,j) if(x==0 and len(s)!=0): orderstack.append(s[len(s)-1]) if(len(s)>0): dfs_for_topological_sorting(a,vis,s.pop()) for i in range(0,len(a)): if(i not in orderstack): s.append(i) dfs_for_topological_sorting(a,vis,i) print(orderstack[len(orderstack)-1::-1]) 

Answer 3

 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