All about programming in GNU/LINUX

Algorithms using python:Graph Algorithms-1:Depth First search

Firstly hello to all the readers !!After the last and its previous post on node.js , Here is the first post of the series of posts to come related to algorithms using python.In this post Ill be discussing about popular tree traversal algorithm Depth First Search . Using python makes the implementation of the algorithm relatively easy because of the availability of numerous built in data structures like hashes(dictionaries) ……….In this this blog post ill be using dictionaries as the main data structure for most of the operations .I’ve tried my best to enhance the degree of detailing in the post so that folks with even least acquaintance with python can understand the code . So then what are we waiting for??? Lets begin 😛

1.REPRESENTATION OF GRAPH USING DICTIONARIES IN PYTHON

A graph will represented using a JSON like structure . here is an example …

Consider the following graph

Image

Here node A is connected to nodes B,C and E and this is represented as described below

{

‘A’:{‘B’:1,’C’:1 }

}

Using the similar approach here is the representation of the complete graph

{

‘A’:{‘B’:1,’C’:1,’E’:1},

‘B’:{‘A’:1,’D’:1,’F’},

‘C’:{‘A’:1,’G’:1},

‘D’:{},

‘E’:{‘A’:1,’F’:1},

‘F’:{‘B’:1,’E’:1},

‘G’:{}

}

  • Declaration of a dictionary

Declaring an empty dictionary in python very simple , the line below illustrates it

      example_dictionary = {}             

Now lets see given tuples containing the pair of codes between which there exists an edge , how to convert them into graph

representation given above and store them in dictionaries ,Here is the tuple representation of connected nodes of the above graph

[(‘A’,’B’),(‘A’,’C’),(‘A’,’E’),(‘B’,’D’),(‘B’,’F’),(‘C’,’G’),(‘E’,’F’)]

def make_link(G,node1,node2):
	if node1 not in G:
		G[node1]= { }
	(G[node1])[node2]= 1 
	if node2 not in G:
		G[node2]= {}
	(G[node2])[node1]= 1 
	return G 
anil_akg rediff

connections = [('a','g'),('a','d'),('d','g'),('g','c')]
G = {}
for x,y in connections:make_link(G,x,y)

print G 

         

Here are the key points that could help you understand the above operations on dictionary G

G= {} #initializes the empty dictionary
G['A'] = {} #Creates a key 'A' in the dictionaries and assigns the key to a value of another empty hash
(G['A'])['B'] = 1 #Creates a Sub-Hash for key 'A' of the hash,Sub-hash is {'B':1}
print G

Here is the screen shot with the above mentioned operations , this will help you understand the process of representing a Graph similar to JSON using dictionaries .

Image

2.Concept of Depth first search

As wikipedia quotes “Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Now let us traverse the above graph using Depth-First-Search.Lets start from node ‘A’ and then move to any of its neighbouring nodes,lets say ndoe ‘C’ , mark these nodes when you visit them for the first time , ‘C’ has only one neighbour ‘G’,so move to node ‘G’ .’G’ has no neighbours so now start backtracking,move to the previous node , that is node ‘C’,node has no more unvisited neighbours , ‘G’ has already been visited.So now backtrack to ‘A’ ,since ‘C’ has already been visited now move on to an unvisited node of ‘A’ , lets say ‘B’ , this process repeats till all the nodes of the graph are visited ,Here is the python code to achieve the some

def make_link(g,node1,node2): #function to construct the graph in JSOn like format 
	if node1 not in G:
		G[node1]={}
	(G[node1])[node2]=1
	if node2 not in G:
		G[node2]={}
	(G[node2])[node1]=1

G={} #initializing the empty grapgh
connections = [('A','B'),('A','C'),('A','E'),('B','D'),('B','F'),('C','G'),('E','F')] #tuples representing the connections

for x,y in connections:make_link(G,x,y) #constructing the graph using tuple representation 

print G

def dfs(G,node,traversed):
	traversed[node]=True #mark the traversed node 
	print "traversal:"+ node 
	for neighbour_nodes in G[node]: #take a neighbouring node 
		if neighbour_nodes not in traversed: #condition to check whether the neighbour node is already visited
			dfs(G,neighbour_nodes,traversed) #recursively traverse the neighbouring node 

def start_traversal(G):
	traversed = {} #dictionary to mark the traversed nodes 
	for node in G.keys(): #G.keys() returns a node from the graph in its iteration
		if node not in traversed: #you start traversing from the root node only if its not visited 
			dfs(G,node,traversed); #for a connected graph this is called only once 

start_traversal(G)

The comments in the code explains everything . The worst case time complexity of DFS is of order n*m , ‘n’ is the number of nodes and ‘m’ is no of edges .We’ll thats it for now,hope that this post helped you understand the implementation of D.F.S in python 😀 see you folks soon with more exciting posts,this is the link to the code from my GITHUB profile

Advertisements

2 responses

  1. Lex

    That was incredibly helpful. The lecture explanation on Udacity went right over my head.

    June 7, 2014 at 3:19 pm

  2. Pingback: Client Server communication using nodeJS and AngularJS:Posting data to the Node-Express server using AngularJS | hackintoshrao

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s