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 #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