To make it more clear, suppose we have N process doing their own BFS at
the same time on this graph, so we can not just set one flag in the
node (unless we have N different flag in each node). In the same sense,
we can not "lock" the graph.
So each process itself to use a separate hashtable to ke
I am thinking on the lines of using two pointer strategy.
Something similar we use to detect loop in a link list. If graph is
implemented using linked list we can have two pointers both moving at
different speeds while traversing a graph and compare them. If they are
equal we have a loop in graph
that ok but if we write an algorithm for
the given problem how it should be if we suppose
locks allow multiprocess to do same job at a time.
On Tue, 04 Apr 2006 Kevin wrote :
>
>Locks can assure one process to do the job properly. It does not allow
>multi process to do the same job at the sam
one process one at a time is what a lock does and if locks dont solve concurreny problems, I dont know what does.Also the loop method is correct too, its upto your code terminate once V*E is reached.
On 4/4/06, Kevin <[EMAIL PROTECTED]> wrote
Locks can assure one process to do the job properly. It
Locks can assure one process to do the job properly. It does not allow
multi process to do the same job at the same time. So it is not a
preferred way in my idea.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Alg
But using the counter only allows us to know we are in a loop AFTER we
are already in it for long time. In other words, it does not help
sovling the problem: we can not finish the BFS!
So it is better to have a way to prevent us from getting into the loop
at the first place, right?
--~--~---
You can set a counter in the BFS loop and if the value of the counter
exceeds |V||E| then you know you are in a cycle.
That is exactly how I have done this kind of detection in some
programming contest problems.
--~--~-~--~~~---~--~~
You received this message bec
use locks then, both before reading the flag and writing the flag.On 4/3/06, Kevin <[EMAIL PROTECTED]
> wrote:oh, another way is have a flag in each node, true or false for visited
or not. But this may have problem is multi threads are using thisgraph, I think.
--~--~-~--~~
oh, another way is have a flag in each node, true or false for visited
or not. But this may have problem is multi threads are using this
graph, I think.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Gee
