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
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()) )
#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 n
a=[[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])
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
from collections import defaultdict # importing defaultdict
def topological_sort(graph,b,a): # defininging function
T = []
visited = []
in_degree = []
for i in range(a+1):
in_degree.append(0) # initialising the degre of each vertex =0
visited.append(0) # initialising all the vertics unvisited
for i in range(1,a+1):
for j in graph[i]:
in_degree[j] = in_degree[j] + 1 # now assigning and increamenting
Queue=[] # the degre of each vertex acc.
for i in range(1,a+1):
if in_degree[i]==0:
Queue.append(i) # appending those vertices which have zero
visited[i] = 1 # degree and making it as visited
while Queue :
vertex = Queue.pop(Queue.index(min(Queue))) # poping each element in
T.append(vertex) # laxicographic order and
for j in graph[vertex]: # appending to T
if visited[j]==0:
in_degree[j] = in_degree[j] - 1
if in_degree[j] == 0:
Queue.append(j) #according to each poped vertex
visited[j] = 1 #as key in graph check whether
return T #in list corresponding to key
# as value,is it not visited and
#decreasing its value when it
#becomes zero,append it to queue
#and mark it as visited
graph=defaultdict(list)
a,b=list(map(int,input().split())) #a=no. of vertices
for i in range(b): #b=no. of edges
p,q=list(map(int,input().split()))
graph[p].append(q) # we take input in graph as DAG
ss=topological_sort(graph,b,a) # calling function
for i in ss:
print(i,end=" ")
'''Input
5 6
1 2
1 3
2 3
2 4
3 4
3 5
Your Code's Output
1 2 3 4 5
Expected Correct Output
1 2 3 4 5 '''
