Home / Expert Answers / Computer Science / i-have-this-python-program-python-program-to-print-topological-sorting-of-a-dag-from-collections-i-pa330

(Solved): I have this Python program #Python program to print topological sorting of a DAG from collections i ...

I have this Python program

#Python program to print topological sorting of a DAG
from collections import defaultdict

# Dictionary of the classes
classes={0: 'N/A',1: 'cs1411',2: 'math1451',3: 'engl1301',4: 'cs1412',5: 'math1452',6: 'phys1408',7: 'engl1302',8: 'cs2413',9: 'cs1382',10: 'ece2372',11: 'math2450',12: 'phys2401',13: 'cs2350',14: 'cs2365',15: 'engr2392',16: 'pols1301',17: 'math2360',18: 'engl2311',19: 'cs3361',20: 'cs3364',21: 'math3342',22: 'pols2306',23: 'cs3365',24: 'cs3375',25: 'cs3383',26: 'cs4365',27: 'cs4352',28: 'cs4354',29: 'cs4366'}

#Class to represent a graph
class Graph:
def __init__(self,vertices):
self.graph = defaultdict(list) #dictionary containing adjacency List
self.V = vertices #No. of vertices

# function to add an edge to graph
def addEdge(self,u,v):

# neighbors generator given key
def neighbor_gen(self,v):
for k in self.graph[v]:
yield k

# non recursive topological sort
def nonRecursiveTopologicalSortUtil(self, v, visited,stack):

# working stack contains key and the corresponding current generator
working_stack = [(v,self.neighbor_gen(v))]

while working_stack:
# get last element from stack
v, gen = working_stack.pop()
visited[v] = True

# run through neighbor generator until it's empty
for next_neighbor in gen:
if not visited[next_neighbor]: # not seen before?
# remember current work
# restart with new neighbor
working_stack.append((next_neighbor, self.neighbor_gen(next_neighbor)))
# no already-visited neighbor (or no more of them)

# The function to do Topological Sort.
def nonRecursiveTopologicalSort(self):
# Mark all the vertices as not visited
visited = [False]*self.V

# result stack
stack = []

# Call the helper function to store Topological
# Sort starting from all vertices one by one
for i in range(self.V):
if not(visited[i]):
self.nonRecursiveTopologicalSortUtil(i, visited,stack)
# Print contents of the stack in reverse

g= Graph(29)
g.addEdge(classes[1], classes[0]);
g.addEdge(classes[2], classes[0]);
g.addEdge(classes[3], classes[0]);
g.addEdge(classes[4], classes[1]);
g.addEdge(classes[5], classes[2]);
g.addEdge(classes[6], classes[2]);
g.addEdge(classes[7], classes[3]);
g.addEdge(classes[8], classes[4]);
g.addEdge(classes[9], classes[1]);
g.addEdge(classes[10], classes[2]);
g.addEdge(classes[11], classes[5]);
g.addEdge(classes[12], classes[6]);
g.addEdge(classes[13], classes[4]);
g.addEdge(classes[13], classes[10]);
g.addEdge(classes[14], classes[8]);
g.addEdge(classes[15], classes[0]);
g.addEdge(classes[16], classes[0]);
g.addEdge(classes[17], classes[5]);
g.addEdge(classes[18], classes[3]);
g.addEdge(classes[18], classes[7]);
g.addEdge(classes[19], classes[8]);
g.addEdge(classes[20], classes[8]);
g.addEdge(classes[20], classes[9]);
g.addEdge(classes[20], classes[17]);
g.addEdge(classes[21], classes[11]);
g.addEdge(classes[22], classes[0]);
g.addEdge(classes[23], classes[8]);
g.addEdge(classes[23], classes[14]);
g.addEdge(classes[23], classes[21]);
g.addEdge(classes[24], classes[13]);
g.addEdge(classes[25], classes[9]);
g.addEdge(classes[26], classes[23]);
g.addEdge(classes[27], classes[20]);
g.addEdge(classes[27], classes[24]);
g.addEdge(classes[28], classes[20]);
g.addEdge(classes[29], classes[26]);

print("The following is a Topological Sort of the given graph")

it is classes at school and their prerequisites listed in the graph section.

I need help with this code.

It is supposed to print the post numbers in topological order, but it just printing 28-0.

Can someone help?

We have an Answer from Expert

View Expert Answer

Expert Answer

We have an Answer from Expert

Buy This Answer $5

Place Order

We Provide Services Across The Globe