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

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]

done 🙂

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

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.