Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
While implementing BFS, we enque the neighbours of the present node into the queue. Then we deque each of them and again run a BFS on them sequentially. Because we have a parallel processing available, we can execute them in parallel instead of sequential. But we need to keep the common information like visited nodes etc with each of the process.
If the graph is unweighted we can use BFS to find the shortest path between the source node and anyother node with the following code. I am using distributed computation to process every node's neighbours. However, we have to make sure that we move to next level only once all the nodes at previous level are done.
BFS(G)
{
For v in Vertices
v.d = 0;
v.prev = null;
v.discovered = 0;
// 0 for not yet discovered, 1 for discovered, 2 for completed processing neighbours
v.level = 0;
s.prev = 0;
s.discovered = 1;
s.d = 0;
s.level = 0;
Q.enque(s);
level = 0;
while(!IsEmpty(Q))
if(Q(NextNode).level == level)
v = deque(Q);
else
wait(); //This waits untill all the child threads are exited.
Process_Parallel(v);
}
Process_Parallel(Node v)
{
for every neighbour u of v:
if(u.discovered == 0)
u.d = v.d+1;
u.discovered = 1;
u.prev = v;
u.level = v.level+1;
}
Thanks Divya,
Well a good implementation. However, how do we do it for weighted graph. I have an idea, why not do a topological sorting on nodes and then apply BFS as to the trick is, only add a node to the queue when it has exhausted all it's incoming edges, that means all the parents have already been calculated for the minimum distance.
The same code with small change will work for weighted directed graph as long as there is no cycle in the graph.
Process_Parallel(Node v){
for every neighbour u of v:
if(u.discovered == 0 || u.d > v.d+weight(uv))
u.d = v.d+weight(uv);
u.discovered = 1;
u.prev = v;
u.level = v.level+1;
}
Hi Divya,
I am afraid that it will not work.
Just consider this example..
n1-->n2 (5)
n1-->n3 (1)
n2-->n5 (2)
n3-->n4 (1)
n4-->n2 (1)
now according to your node, you will calculate the minimum length of n2 as 5 and put it on level two (or 1 depending on whether you start the leveling from 0 or 1). From there you would move on and calculate the optimum length of n5 as 5+2=7. However, on level three you see that n4 has a link to n2 and this is the optimum path to n2 with cost 3(1+1+1). You change this value, however all the nodes that were the child of n2 were calculated with the previous optimum value of n2 (5) which will give incorrect results.
So we have to consider the topology here in a way that we only add a node to queue when all the parents have calculated their optimum path. This will assurance to a node that it will have the optimum value and it can safely proceed with the child nodes.
So, in our example N2 should only be added to queue after N4. That's nothing but the topological sort mixed with BFS. (only if their are no cycles)
Thanks
I guess for bfs, we do not put the node into queue, for each node, create a new thread to continue the processing, the parameter contains the cost to the current node so far
I don't think you can use traditional BFS for weighted graph. The difference in weighted graphs is that a longer path can still end up incurring less cost(distance). Distance should be only updated if it's less than the current distance. If the graph doesn't have cycles then you can still use while(!Empty(Q)) to check for completion.
Single source shortest path problem - Bellman Ford's algorithm, which is in essense a BFS.
for each u in V(G), d[u]=infinity;
d[s] = 0;
for(i=0; i<|E(G)|-1; i++) {
/* parallelize the following loop */
for(each edge (u, v) in E(G)) {
/* critical section */
mutex_lock();
if(d[v]>d[u] + w(u,v)) {
d[v] = d[u] + w(u,v);
}
mutext_unlock();
}
}
Optimization should be done as to the use of lock, so that it does not become a performance choke point. For large graph, one lock is obviously not enough, but one lock for each vertex seems too much. We can use one lock to guard a given amount of vertices, for example 16.
on a single machine:
1. I would say use Dijkstra to find shortest path (based on BFS)
2. we need to mark on each note when we pass it
when moving to make it parallel
Assumption: parallel here would mean that few searches on the same graph can be done simultaneously , meaning, each search can touch the same node (altough coming from different path)
This mean that instead of making when touching it on the node itself, each thread/process, - should hold a hash table if this node is visited.
How would you start the "parallelism" - let's say we have N threads/machines. and the first node in the graph has C children, we would give N%C for each process to work on, although working on the same graph
The keyword in this problem is PARALLEL. Every student knows how to implement simple DFS in a graph.
We can use Breadth first search to find the shortest path between two nodes if the graph is unweighted graph. However, if the graph is weighted will the BFS still work? I think we can't use BFS for weighted graphs. Can someone correct me if I am wrong here.
"Parallel" is ambiguous and a decent algorithm completely depends on the what underlying "parallel machine" you have. The mention of C & OpenMP narrows it down a bit, though, I suppose.
- Anonymous October 12, 2011