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)

graphimage

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

#create adj lists
adj =[ [] for i in range(vertices)]

#create a function to set an edges
def set_edge(vertex_no, node_no):
    globals()
    adj[vertex_no].append(node_no)

set_edge(5,2)
set_edge(5,0)
set_edge(4,0)
set_edge(4,1)
set_edge(2,3)
set_edge(3,1)
# print adj

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()
    adj[vertex_no].append(node_no)

def toposort(i):
    globals()
    visited[i] = True
    for each in adj[i]:
        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)
# print adj


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):
        initialize your node_no , params


Then append the node into the adj list

comments powered by Disqus