wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Universal Sink
        
(Message started by: johny_cage on Nov 18^th, 2007, 3:05am)

Title: Universal Sink
Post by johny_cage on Nov 18^th, 2007, 3:05am

You are having a directed graph G contains a universal sink (a vertex with in-degree |V|-1 and out-degree 0). Now, you have to find this universal sink in O(V).
And the scheme used is adjacency matrix.

Title: Re: Universal Sink
Post by towr on Nov 18^th, 2007, 7:07am

[hide]Check every vertex to see if it has out-degree 0, only the sink has that.[/hide]
But, in an adjacency matrix, that would take O(V²)
So I suppose there must be some ~~cleverererderder~~ more clever way..

Title: Re: Universal Sink
Post by johny_cage on Nov 18^th, 2007, 8:22am

Yups, i m also thinking, there should be some way to do it in O(V)....

Title: Re: Universal Sink
Post by Grimbal on Nov 18^th, 2007, 11:12am

i=j=0
while( j<n ){
if( there is an edge from i to j ) i++;
else j++;
}
-> the universal sink is i.

Title: Re: Universal Sink
Post by johny_cage on Nov 18^th, 2007, 11:32am

hey Grimbal,

plz elaborate your answer more, as what is i and j???
and if u want to say i and j are vertices then please tell how they are going to initialize, and what if there exist no [bold]Universal Sink[/bold]. Then, the while loop used never terminate....

so, please elaborate your answer....

Title: Re: Universal Sink
Post by towr on Nov 18^th, 2007, 12:15pm

on 11/18/07 at 11:32:17, johny_cage wrote:

what if there exist no Universal Sink. Then, the while loop used never terminate....

If there is no universal sink, then the premise of the problem is broken. (It is stated G does contain a universal sink)

But you can add a condition to break when i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gifn
Because either the loop ends normally, or i will increase beyond n.

Title: Re: Universal Sink
Post by Grimbal on Nov 18^th, 2007, 12:17pm

i and j are vertices. I assumes vertices are numbered from 0 to n-1

The problem says "You are having a directed graph G contains a universal sink". So I ignored the case where there is in fact no universal sink.

What I called "a link from i to j" is a directed edge starting at i and ending at j.

Maybe it is clearer if you consider the adjacency matrix where a_ij=1 if there is an edge from i to j, 0 if not. The problem is then to locate the row s consisting of only zeros, knowing that column s has only ones, except for a_ss. The algorithm ends with i=s because it cannot end larger than s and it cannot end smaller than s. i cannot end larger than s because once it reaches s it can not increment any more. i can not end smaller than s, because when j reaches s, i will be incremented until i=s.

Title: Re: Universal Sink
Post by aditi on Nov 18^th, 2007, 7:26pm

nice solution

Title: Re: Universal Sink
Post by swami on Nov 26^th, 2007, 4:58am

I am not clear with this soln.

Suppose 'i' got incremented last when j=j1 after which 'i' did not change. 'i' is outputted as the universal sink. But the algo. doesnt seem to check incidence from 'i' to j<j1

Am i missing something? Can someone throw some light on this?

Title: Re: Universal Sink
Post by Grimbal on Nov 26^th, 2007, 8:00am

It doesn't check that there is one. The only claim is that if there is an universal sink, then it finds it.

If there is no universal sink, it might return anything, even crash on an array index out of bounds.

But it is a given that there is one, so I don't really have to verify it.

You could check whether i exceeds the bounds (in which case there is no universal sink) and do a second pass to check that the returned node is indeed an universal sink. It would still be O(n).

Title: Re: Universal Sink
Post by swami on Nov 26^th, 2007, 8:52am

No...My doubt is this

1 2 3 4 5
1 1 0 0 0 0
2 0 0 1 0 0
3 1 0 0 0 0
4 0 0 0 0 0
5 0 0 0 0 0

~~The algo will return '3' as the universal sink, while '4' or '5' shud have been the answer.~~

Title: Re: Universal Sink
Post by towr on Nov 26^th, 2007, 9:29am

on 11/26/07 at 08:52:28, swami wrote:

The algo will return '3' as the universal sink, while '4' or '5' shud have been the answer.

Neither 4 nor 5 or universal sinks as per the definition.
In fact following the definition given, there can be at most one universal sink, because all nodes (other than itself) must link to it, and it mustn't itself link to any nodes.
If there are two sinks, neither can link to the other, and so neither can be universal.

Title: Re: Universal Sink
Post by swami on Nov 26^th, 2007, 9:37am

OK.. gotit...sorry abt that