Author |
Topic: Graph Roots (Read 1636 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Graph Roots
« on: Dec 10th, 2003, 3:46am » |
 Quote  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: 
Posts: 13730
|
|
Re: Graph Roots
« Reply #1 on: Dec 10th, 2003, 4:37am » |
Quote 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 Modify
|
on Dec 10th, 2003, 4:37am, towr wrote: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:
Posts: 13730
|
|
Re: Graph Roots
« Reply #3 on: Dec 10th, 2003, 11:00am » |
Quote 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
Gender:
Posts: 1291
|
|
Re: Graph Roots
« Reply #4 on: Dec 10th, 2003, 10:41pm » |
Quote 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:
Posts: 1001
|
|
Re: Graph Roots
« Reply #5 on: Dec 10th, 2003, 11:22pm » |
Quote 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 
::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Graph Roots
« Reply #7 on: Dec 11th, 2003, 12:40am » |
Quote 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
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Graph Roots
« Reply #9 on: Dec 11th, 2003, 4:03am » |
Quote 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
|
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  ).
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:
Posts: 1001
|
|
Re: Graph Roots
« Reply #11 on: Dec 20th, 2003, 3:15am » |
Quote 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 
|
|
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 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 |
|
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:
Posts: 1001
|
|
Re: Graph Roots
« Reply #13 on: Dec 21st, 2003, 10:33pm » |
Quote Modify
|
Dudidu,
i appreciate anyone helping me out (unless ofcourse if you are a Vogon  )
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 root)
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 come
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
Gender:
Posts: 949
|
|
Re: Graph Roots
« Reply #14 on: Dec 22nd, 2003, 9:59am » |
Quote 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:
Posts: 1001
|
|
Re: Graph Roots
« Reply #15 on: Dec 23rd, 2003, 11:51am » |
Quote 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print