Cracking the Coding Interview – 4.2 Route in directed graph

Here we are solving another exercise from the Cracking the Coding Interview. It says:

4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

First we need to represent the graph. When I was in high-school we used to represent graphs (I implemented in pascal) as a matrix of n*n elements. m[k,q] = 1 if there is a vertices from k to q. This representation is not suitable for large graphs (especially if they have small number of vertices ) but will do just well for our exercise:

class dag:
	
	def __init__(self, _matrix):
		self.matrix=_matrix

	def get_adj(self, node):
		result=[]
		for i,val in enumerate(self.matrix[node]):
			if val == 1:
				result.append(i)
		return result

	def nb_nodes(self):
		return len(self.matrix)

Before implementing our function hasPath(dag, nodeK, nodeQ) lets write a test:

			
def test():
	m = [[1,0,0,1],
		 [0,1,1,1],
	 	 [0,1,1,0],
	 	 [0,0,1,1]]	
	d =  dag(m)
	assert (hasPath(d,0,2))
	assert (hasPath(d,0,1))
	assert (hasPath(d,2,3))
	assert (hasPath(d,2,0)==False)
	assert (hasPath(d,1,0)==False)
	print 'Test Ok'

And now the required function. We will traverse the graph starting from the first node and stop when we encounter the second node.
There are 2 graph traversal strategies:

  • Depth First Search: DFS involves searching a node and all its children before proceeding to its siblings.
  • Breadth First Search: BFS involves searching a node and its siblings before going on to any children.

We will do DFS for the sake of this exercise: We will use a queue (FIFO) to keep nodes that need to be visited. We put the first node in the queue. Then we pop a node from the queue, visit it and put all its children in the queue. We also need to remember which nodes have been visited to avoid cycles.

So here it is:

def hasPath(dag,start, end):
	q=[start]
	visited = [0] * dag.nb_nodes()
	while len(q)>0:
		node = q.pop()
		visited[node]=1
		if end==node:
			return True
		q= q+ [x for x in dag.get_adj(node) if visited[x]==0]
	return False

Update – let’s make it more pythonic

by taking into account mebubo ‘s comments:

class dag:
	def __init__(self, _matrix):
		self.matrix=_matrix

	def get_adj(self, node):
               return [i for (i, val) in enumerate(self.matrix[node]) if val]

def hasPath(dag,start, end):
	q=[start]
	visited = [0] * dag.nb_nodes()
	while len(q)>0:
		node = q.pop()
		visited[node]=1
		if end==node:
			return True
		q= q+ [x for x in dag.get_adj(node) if not visited[x]]
	return False
Advertisements
This entry was posted in Cracking the coding interview - a python experience and tagged , , . Bookmark the permalink.

4 Responses to Cracking the Coding Interview – 4.2 Route in directed graph

  1. mebubo says:

    It is more pythonic to use “if val” “if not visited[x]” instead of explicit comparisons. bool(1) == True; bool(0) == False; bool([]) == False.

    You could use a list comprehension in get_adj:

    return [i for (i, val) in enumerate(self.matrix[node]) if val]

  2. mebubobo says:

    You could even use “while q” instead of “while len(q)>0”! 🙂

  3. mayathebee says:

    If you use a queue (FIFO principle), then you are doing BFS, not DFS. That is because you will always insert siblings before the children of the siblings. Hence, siblings are visited before the children, which results in a breadth-first search.

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