# Topological Sort Algorithm

Creating our “Directed Graph”

``````class Graph:

def __init__(self, Nodes, is_directed = False):
self.nodes = Nodes

self.is_directed = is_directed

for node in self.nodes:

if not self.is_directed:

def degree(self,node):
'''Total number of edges coming out a given node'''
return deg

for node in self.nodes:

def __len__(self):
return len(self.nodes)

def __getitem__(self, node):

"""retrives items from out Node/vertex"""

def __iter__(self):
""" This will allow us to iterate over our Graph Object"""
""" We can iterate over the keys or "Vertexs" by: """
""" using just the Object->  graph:  """

``````

Lets add out Edges and Nodes

``````all_edges = [

("A","D"),("B","D"),("C","B"),("C","A"),("E","A"),("E","D"),
("E","F"),("D","H"),("D","G"),("F","K"),("F","J"),("H","J"),
("H","I"),("G","I"),("K","J"),("J","M"),("J","L"),("I","L")

]
nodes = ["A","B","C","D","E","F","G","H","I","J","K","L","M"]

``````

Lets create a Graph Object

``````
graph1 = Graph(nodes, is_directed = True)

for u,v in all_edges:

``````

Output of Graph:

``````
A -> ['D']
B -> ['D']
C -> ['B', 'A']
D -> ['H', 'G']
E -> ['A', 'D', 'F']
F -> ['K', 'J']
G -> ['I']
H -> ['J', 'I']
I -> ['L']
J -> ['M', 'L']
K -> ['J']
L -> []
M -> []
``````

Let’s add a Deque Data Structure

``````
class Deque:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

self.items.append(item)

self.items.insert(0,item)

def removeFront(self):
return self.items.pop()

def removeRear(self):
return self.items.pop(0)

def size(self):
return len(self.items)

def _print(self):
'''print Deque Values'''
return self.items

``````

Now lets Create a Topological Function and Corresponding DFS

``````
def dfs(graph, source, stack, visited):

visited.append(source)

for neighbour in graph[source]:

if neighbour not in visited:

dfs(graph, neighbour, stack, visited)

def topological_sort_of(graph):

stack = Deque()
visited = []

for vertex in graph:

if vertex not in visited:

dfs(graph, vertex, stack, visited)

return stack
``````

Running our Topological Sort Algorithm

``````
topological_ordering = topological_sort_of(graph1)

topological_ordering._print()

``````

Topological Ordering Output:

``````
['E', 'F', 'K', 'C', 'B', 'A', 'D', 'G', 'H', 'I', 'J', 'L', 'M']

``````