Posted on Tue 05 April 2016

Implementing python graphs and topological sort

### Graphs using python

It was about yesterday that I was working on a project that involved the use of a graphs and topological sort. However, I was surprised when I saw the implementation sizes. Albeit , python uses substantially less number of LOC, this example particularly blew my mind. Ive never been able to create graphs in such an easy manner. :P :P (Im overstating cause im a bit ecstatic right now) .

Beginning with graphs, We’ll represent the graph using lists, and not matrices (saves memory you know)..

The graph refers the one shown here (Courtesy : geeksforgeeks.com) Let’s write the python code. We shall read the file, and then create the adjacency lists out of it.

```# number of vertices
vertices = 6

adj =[ [] for i in range(vertices)]

#create a function to set an edges
def set_edge(vertex_no, node_no):
globals()

set_edge(5,2)
set_edge(5,0)
set_edge(4,0)
set_edge(4,1)
set_edge(2,3)
set_edge(3,1)
```

Let’s write a toposort now. A topological sort will give the order as to which node is to be processed first in order of execution. It has to start with a node having in degree as 0. You can read here for more details

```vertices = 6
adj = [ [] for i in range(vertices) ]
visited = [False for i in range(vertices)]
output = []

def set_edge(vertex_no, node_no):
globals()

def toposort(i):
globals()
visited[i] = True
print each, visited[each]
if not visited[each]:
toposort(each)
#print "i = ", i
output.append(i)
#print output

set_edge(5,2)
set_edge(5,0)
set_edge(4,0)
set_edge(4,1)
set_edge(2,3)
set_edge(3,1)

for item in range(vertices):

if not visited[item]:
toposort(item)

output.reverse()
print output

`OUTPUT`
`[5, 4, 2, 3, 1, 0]`
```

If you want to make customised nodes, with some attributes, you can create a class.

```class Node:
def __init__(self, node_no, params):