wu :: forums
« wu :: forums - Graph Roots »

Welcome, Guest. Please Login or Register.
Dec 23rd, 2024, 8:32am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Icarus, ThudnBlunder, william wu, Eigenray, SMQ, towr, Grimbal)
   Graph Roots
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Graph Roots  (Read 1655 times)
Dudidu
Full Member
***





   


Posts: 227
Graph Roots  
« on: Dec 10th, 2003, 3:46am »
Quote Quote Modify Modify

Given a directed graph G=(V,E), a root of it, is a node such that every other node v[in]V is reachable from it.
1) Does every directed graph has a root ?
2) Devise an algorithm that given a directed graph finds a root (you can add here 'if exists' if your answer to the 1st question was no).
3) Devise an algorithm that given a directed graph finds all the roots (you can add here 'if exists' if your answer to the 1st question was no).
« Last Edit: Dec 10th, 2003, 3:47am by Dudidu » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Graph Roots  
« Reply #1 on: Dec 10th, 2003, 4:37am »
Quote Quote Modify Modify

1) ::no, for instance G=({a,b}, {}) doesn't have a root.::
« Last Edit: Dec 10th, 2003, 4:39am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member
***





   


Posts: 227
Re: Graph Roots  
« Reply #2 on: Dec 10th, 2003, 9:31am »
Quote Quote Modify Modify

on Dec 10th, 2003, 4:37am, towr wrote:
1) ::<Hide>::
towr, this is (of course) correct - not every graph must have a root.  
So... can you find a/all root/s (efficiently) ?
« Last Edit: Dec 10th, 2003, 9:33am by Dudidu » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Graph Roots  
« Reply #3 on: Dec 10th, 2003, 11:00am »
Quote Quote Modify Modify

Well, finding them isn't too hard.. the efficiency bit however is..
Is suppose I could put up flags. That would give O(n2) worst case. ::just travel from each node back along each edge, and put up a flag of untill you reach a node in which either there is allready a flag from the node you're processing, or no edges left to go further up. At most you visit each node for each node, and in the end check which nodes have flags set from all nodes.::
Up to 32 or 64 nodes could probably be done linearly (with some tinkering anything up to a fixed number N could probably work) ::since the flags fit in one register, and you can do nifty stuff, like giving of your flags and letting the next node carry them further. But I don't want to get into that now::
« Last Edit: Dec 11th, 2003, 1:03am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Graph Roots  
« Reply #4 on: Dec 10th, 2003, 10:41pm »
Quote Quote Modify Modify

Vaguely recalling some old algorithms material, I think we can do it in linear time by running DFS on the reversed graph while recording postvisit information about the nodes, and then running DFS on the original graph, visiting nodes according to decreasing postvisit number, and outputting the strongly connected components of the graph. Essentially a topological sort; and the nodes in the source strongly connected component are the roots. The details and proof are lengthy to describe IIRC. Maybe I'll say more later.
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Graph Roots  
« Reply #5 on: Dec 10th, 2003, 11:22pm »
Quote Quote Modify Modify

I was thinking the same thing william.
::
However we need not do a topo sort on the graph as such, if my thinking is corect.IIRC topo sort can be done on a directed graph IFF it has a node with indegree zero since we essentially start with this node(or this is the root node).So all we need to do in the problem posed by Dudidu is to find the nodes with indegree zero. One can easily find an O(n2) time algorithm for this but i have not succeeded in bettering this efficiency.
 
Now i am expecting someone to make a post and show that i am wrong Smiley
::
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Graph Roots  
« Reply #6 on: Dec 11th, 2003, 12:04am »
Quote Quote Modify Modify

what's DFS?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Graph Roots  
« Reply #7 on: Dec 11th, 2003, 12:40am »
Quote Quote Modify Modify

DFS is depth-first search, the slimy tentacle that thrusts and retracts and thrusts and retracts and thrusts and retracts.
 
::

Tenali, I was thinking of a general topological sort in which we first reduce the graph to a directed acyclic graph (DAG) of strongly connected components (SCCs) , and then do a topological sort on that (I mentioned SCCs hastily in my previous post). (For those who don't know, an SCC is a subset of the vertices for which every node can reach every other node in the subset. It's like a very neighbourly subcommunity.) After the strongly connected components have been shrunken to single nodes, we do the topological sort, and then every node inside the source SCC will be a root.  
 
It doesn't suffice to look for nodes of indegree zero, because there could be none -- every node could be part of a strongly connected component. Then you couldn't do a topological sort. However, there could very well still be root nodes in the graph. Thus we need to first decompose the graph into a DAG of SCCs, and then pinpoint the source SCC.
 
The total algorithm should run in linear time because DFS runs in O(|V| + |E|) time, and all I'm doing is DFS twice. I think the graph reversal could also be done in linear time by manipulating the adjacency matrix of G's edges. For instance, if we adopt the convention that Gij is  
 
1 if there is an edge from i to j,  
-1 if there is an edge from j to i, and  
0 if there is no edge between i and j
 
then to construct the adjacency matrix for GR (reversal of G), all we have to do is multiply all entries in this matrix by (-1).
 

::
« Last Edit: Dec 11th, 2003, 12:43am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Graph Roots  
« Reply #8 on: Dec 11th, 2003, 12:56am »
Quote Quote Modify Modify

on Dec 11th, 2003, 12:40am, william wu wrote:
DFS is depth-first search
ah.. I know that one.. I'm just not good with abbreviations..
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Graph Roots  
« Reply #9 on: Dec 11th, 2003, 4:03am »
Quote Quote Modify Modify

All right; I've got a completely new method (that works, as opposed to my earlier methods, which were so bad I didn't even bother to post them). It consists of three stages, each running in O(V+E) time (=O(E) time for graphs that do have roots):
 
i) The first stage finds a candidate root R such that if there are any roots in the graph, then R is a root.
 
ii) The second stage checks to see whether or not R is a root.
 
iii) The third stage finds all the other roots.
 
I'll leave the second and third stages as exercises for you (I'm sure you'll find them easy), but for the first stage (which is surprisingly simple!), I'll just direct you to the following observation:
 
Lemma: If there is a path from V to W, then (W is a root) => (V is a root)
« Last Edit: Dec 11th, 2003, 4:04am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
Dudidu
Full Member
***





   


Posts: 227
Re: Graph Roots   NoSourceSCC.jpg
« Reply #10 on: Dec 11th, 2003, 7:31am »
Quote Quote Modify Modify

Everybody hi,
I see that everybody started working on the 3rd sub-question (why waste time on sub-questions that are immediatly solved by other sub-questions Wink).
Quote:
Vaguely recalling some old algorithms material...
William hi,
Your solution is excellent since it uses many techniques that can be used on other related graph problems (I'll post a problem that uses these techniques soon).
However, for my opinion these techniques (e.g. creating a DAG of SCCs, topological sort...) is not so trivial to come up with if you haven't learned them somewhere before. Thus, I find it too powerfull for this problem.
One remark though, it should be emphasized (for my opinion) that there may not be a source SCC (and thus there may not be a root - see figure below of SCC's that don't have a source SCC).
 
Quote:
I've got a completely new method...
James, well done !
This is more similar to what I was looking for (i.e. more intuitive). Still, explaining how to find a the root R on the first stage is needed (2nd sub-question) and (maybe) the 3rd stage also need to be explained (its easy but still not trivial).
 
P.S. James, you don't have to explain it yourself, I just "thrown" it as a challenge...
IP Logged

TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Graph Roots  
« Reply #11 on: Dec 20th, 2003, 3:15am »
Quote Quote Modify Modify

James,
i need help with the first part of your solution please!!
can't seem to find a way to find R without doing some exhaustive search  Huh
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Dudidu
Full Member
***





   


Posts: 227
Re: Graph Roots  
« Reply #12 on: Dec 21st, 2003, 1:17am »
Quote Quote Modify Modify

on Dec 20th, 2003, 3:15am, TenaliRaman wrote:
James,
i need help with the first part of your solution please!!
can't seem to find a way to find R without doing some exhaustive search Huh
TenaliRaman hi,
I know I'm not James but I help you with this...
Prove to yourself that the following claim is correct: If you run DFS on the graph G and T is the last tree constructed by the DFS (and R is the root of this tree (T)) then if the graph G has a root, R must be a root of G.  
After proving this claim, the algorithm for finding a root is quite stright forward.

If you need more help, you know were to find me...
« Last Edit: Dec 21st, 2003, 1:18am by Dudidu » IP Logged
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Graph Roots  
« Reply #13 on: Dec 21st, 2003, 10:33pm »
Quote Quote Modify Modify

Dudidu,
i appreciate anyone helping me out (unless ofcourse if you are a Vogon Grin)
Btw,
whatever u said is what i thought initially after seeing yours and James post!!
::
1>run a DFS
2>find the root of the DFS tree i.e R
3>simply backtrace from R and find the other roots. (this is actually James' Lemma)
 
to show that we have covered all possible roots.Assume that there is one more root Q that we haven't got.now if Q is  a root then Q must have a path to R, which means that we have already covered Q during backtracing. Contradiction!
::
 
i thought this was over.However if you look at the steps James gives, "i think" he has a different technique to it.
 
He says in first stage "find a root R"
and in his second stage "check whether R is a root or not" (why this stage if R is a rootHuh)
now in third stage "find other root"  
this means that the third stage should use the Lemma James gives but he says to use it for the first stage ... how comeHuh
 
Maybe i am seeing this in totally wrong perspective or maybe james has an alternative technique.
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Graph Roots  
« Reply #14 on: Dec 22nd, 2003, 9:59am »
Quote Quote Modify Modify

I think Dudidu and I have the same solution. Here's my explanation:
 
1) Pick any vertex Q. Mark all vertices going forward (BFS or DFS--it doesn't matter which one) from Q. If you reach all vertices from Q, then Q is a root. If you don't, then Q is not a root, and none of the marked vertices are either.
 
2) Now consider only the vertices you haven't yet marked. Pick a vertex Q, and mark all unmarked vertices going forward from Q. If you reach all vertices, then R = Q may be a root. Otherwise, Q is not a root and neither are any of the marked vertices.
 
3) Repeat step 2 as needed. Eventually this must terminate (after picking at most V vertices Q), and the last Q picked is R. Proof that R must be a root if there is a root:
 
For every vertex M that is marked before you picked the final Q, you marked all vertices downstream from M. Since not all vertices were downstream from M, M cannot be a root.
 
For every vertex N that was not marked until after you picked the final Q = R, R is upstream of N, so if N is a root, then R is a root.
 
So all the roots are in N, and R is upstream of all of N.
 
And yes, backtracing from R gives all roots (if there are multiple roots).
IP Logged

Doc, I'm addicted to advice! What should I do?
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Graph Roots  
« Reply #15 on: Dec 23rd, 2003, 11:51am »
Quote Quote Modify Modify

As i said, i was looking at James' solution in a wrong perspective.
 
Thanks for the clarification James and thanks to Dudidu as well.
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board