Implementation of Graph DS using Python and BFS,DFS covered with iteration

This post will be mostly code. Please use proper indenting cuz Python otherwise will make your life hell. If you’re using Sublime go to, set Convert Indentation to tabs.

Gist : I have used the collections.defaultdict dict DT for implementing a dict of sets.
Vertices have been stored as adjacency list kind of elements as a dictionary. The code is raw and may have errors ( though no compilation error as of the post’s writing). Please comment for additional details. This is purely for testing purposes.


 

graph            A Graph.

 



from collections import defaultdict

#The Graph will be a dictionary of sets
class Graph():

def __init__(self, connections, directed = False):
self.graph = defaultdict(set)
self.directed = directed
self.add_connections (connections)

def add_connections(self, connections):
for node1,node2 in connections:
self.add_connection(node1,node2)

def add_connection(self, node1, node2):
self.graph[node1].add(node2)
if not self.directed:
self.graph[node2].add(node1)

def remove(self, node):
#removes all references to the node
#Use iteritems for dict items like k,v in dictname.iteritems():
for n,cons in self.graph.iteritems():
try:
#Removing from a set involves setname.remove(element)
cons.remove(node)
except KeyError:
pass
try:
#Removing from a dictionary involves rem dict_element_name
del self.graph[node]
except KeyError:
pass

def isconnected(self, node1, node2):
if node1 in self.graph[node2] or node2 in self.graph[node1]:
return True
return False

def dfs(self,start):
#If start node does not exist, return None (search is futile)
if start not in self.graph:
return None
#Start with an empty set
visited = set()

#To return unse ( which is not a set
unset = []
#Initially fill stack with start vertex
stack = [start]

#While stack is not empty keep repeating this algorithms
while stack:
#Take the first element of stack (pop means last inserted , aggressive)
vertex = stack.pop()
#If vertex has not been visited yet, add it to visited and look for all the element in graph[vertex]
if vertex not in visited:
visited.update(vertex)
unset.append(vertex)
stack.extend(self.graph[vertex] - visited)
return unset

def bfs(self, start):
if start not in self.graph:
return None
visited = set()
queue = [start]
unset = []
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.update(vertex)
unset.append(vertex)
queue.extend(self.graph[vertex] - visited)
return unset

#Should work but not tested
def findpath(self,v1, v2):
m = bfs(v1)
if v2 in m:
return m[:m.index(v2)+1]
return None

 

Advertisements

2 thoughts on “Implementation of Graph DS using Python and BFS,DFS covered with iteration

  1. You could install a quick plugin for your code, then you could post it as it appears in your code editor (I’m a fan of Sublime as well), with syntax highlighting and everything.

    Like

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