Author |
Topic: Universal Sink (Read 12175 times) |
|
johny_cage
Full Member
Gender: 
Posts: 155
|
 |
Universal Sink
« on: Nov 18th, 2007, 3:05am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Universal Sink
« Reply #1 on: Nov 18th, 2007, 7:07am » |
Quote Modify
|
Check every vertex to see if it has out-degree 0, only the sink has that.
But, in an adjacency matrix, that would take O(V2)
So I suppose there must be some cleverererderder more clever way..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Universal Sink
« Reply #2 on: Nov 18th, 2007, 8:22am » |
Quote Modify
|
Yups, i m also thinking, there should be some way to do it in O(V)....
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Universal Sink
« Reply #3 on: Nov 18th, 2007, 11:12am » |
Quote Modify
|
i=j=0
while( j<n ){
if( there is an edge from i to j ) i++;
else j++;
}
-> the universal sink is i.
|
| « Last Edit: Nov 18th, 2007, 12:18pm by Grimbal » |
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Universal Sink
« Reply #4 on: Nov 18th, 2007, 11:32am » |
Quote Modify
|
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....
|
| « Last Edit: Nov 18th, 2007, 11:32am by johny_cage » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Universal Sink
« Reply #5 on: Nov 18th, 2007, 12:15pm » |
Quote Modify
|
on Nov 18th, 2007, 11:32am, 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  n
Because either the loop ends normally, or i will increase beyond n.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Universal Sink
« Reply #6 on: Nov 18th, 2007, 12:17pm » |
Quote Modify
|
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 aij=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 ass. 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.
|
| « Last Edit: Nov 18th, 2007, 12:20pm by Grimbal » |
IP Logged |
|
|
|
aditi
Newbie
Posts: 17
|
|
Re: Universal Sink
« Reply #7 on: Nov 18th, 2007, 7:26pm » |
Quote Modify
|
nice solution
|
|
IP Logged |
|
|
|
swami
Newbie
Gender:
Posts: 17
|
|
Re: Universal Sink
« Reply #8 on: Nov 26th, 2007, 4:58am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Universal Sink
« Reply #9 on: Nov 26th, 2007, 8:00am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
swami
Newbie
Gender:
Posts: 17
|
|
Re: Universal Sink
« Reply #10 on: Nov 26th, 2007, 8:52am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 26th, 2007, 9:38am by swami » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Universal Sink
« Reply #11 on: Nov 26th, 2007, 9:29am » |
Quote Modify
|
on Nov 26th, 2007, 8:52am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
swami
Newbie
Gender:
Posts: 17
|
|
Re: Universal Sink
« Reply #12 on: Nov 26th, 2007, 9:37am » |
Quote Modify
|
OK.. gotit...sorry abt that
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print