Implementing graph search

Question

I am very new in Python, I would like to know if the style presented below attends a good implementation in Python.

import numpy as np
from collections import deque
def BFS(theGraph,source):
 n=len(theGraph)
 explored=np.empty(n,bool)
 for i in range(0,n):
 explored[i]=False
 explored[source]=True
 queue = deque([source])
 while len(queue)!=0:
 v=queue.popleft() 
 print "theNode: ", v 
 for i in theGraph[v]:
 if(not explored[i]):
 explored[i]=True
 queue.append(i)
 return explored 
def DFS(theGraph,source):
 n=len(theGraph)
 explored=np.empty(n,bool)
 for i in range(0,n):
 explored[i]=False
 explored[source]=True
 stack = [source]
 while len(stack)!=0:
 v=stack.pop() 
 print "theNode: ", v 
 for i in theGraph[v]:
 if(not explored[i]):
 explored[i]=True
 stack.append(i)
 return explored
def DFSrec(theGraph,explored,source):
 explored[source]=True
 print "theNode: ",source
 for i in theGraph[source]:
 if(not explored[i]): 
 DFSrec(theGraph,explored,i)
 return explored 
n=6 #number of nodes
theGraph=[set() for i in range(n)]
theGraph[0].add(1)
theGraph[0].add(2)
theGraph[1].add(0)
theGraph[1].add(3)
theGraph[2].add(0)
theGraph[2].add(4)
theGraph[3].add(1)
theGraph[3].add(5)
theGraph[4].add(2)
theGraph[4].add(5)
theGraph[5].add(3)
theGraph[5].add(4)
print theGraph
print "DFS: "
print DFS(theGraph,0)
explored=np.empty(n,bool)
for i in range(0,n):
 explored[i]=False
print "DFSrec: "
print DFSrec(theGraph,explored,0)
print "BFS: " 
print BFS(theGraph,0) 

Answer 1

There are some things that you could do to improve your code:

• First of all, your functions clearly lack documentation. Unless you know a little bit about graph theory, it is quite hard to guess that BFS and DFS stand for "Breadth-First Search" and "Depth-First Search". While the names may appear to be long, using the names breadth_first_search and depth_first_search would be really clearer.

• Also, docstrings to document what your functions do would be great. For example, you could write what theGraph is supposed to be since there is no obvious Graph structure to be used around. Documenting your functions, what are the parameters, what is the return type and what may be the preconditions and postconditions really matters :)

• Also, your code is too dense. You should add more spaces where it improves readability. My advice to follow the guidelines in the PEP 8, the Python style guide. These guidelines are really good to write readable code.

• By the way, the PEP 8 says that you shouldn't check the len of a collections to know whether there are elements in or not. Therefore, you should change this line:

  while len(queue)!=0:
  

  ...to this one:

  while queue:
  

• These lines:

  explored=np.empty(n,bool)
  for i in range(0,n):
   explored[i]=False
  

  ...can be reduced to a one-liner thanks to numpy.zeros:

  explored=np.zeros(n,bool)
  

  And since you don't use n except for constructing excepted, you may as well get rid of n and use numpy.zeros_like to construct expected:

  explored = np.zeros_like(theGraph, bool)
  

• While it is good for modules to have examples of how the module works, you generally do not want these examples to be run, unless when you explicitly run the module as a stand-alone. If you want your code to be a module, put the example part of the code in what we could call a "main block" (I don't know whether there is an official name):

  if __name__ == '__main__':
   n=6 #number of nodes
   theGraph=[set() for i in range(n)]
   theGraph[0].add(1)
   theGraph[0].add(2)
   # Rest of your example
   # code goes here...