wu :: forums - Print Page


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

        riddles >> cs >> Graph Roots
        
(Message started by: Dudidu on Dec 10^th, 2003, 3:46am)

Title: Graph Roots
Post by Dudidu on Dec 10^th, 2003, 3:46am

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 1^st 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 1^st question was no).

Title: Re: Graph Roots
Post by towr on Dec 10^th, 2003, 4:37am

1) ::[hide]no, for instance G=({a,b}, {}) doesn't have a root.[/hide]::

Title: Re: Graph Roots
Post by Dudidu on Dec 10^th, 2003, 9:31am

on 12/10/03 at 04:37:51, 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) ?

Title: Re: Graph Roots
Post by towr on Dec 10^th, 2003, 11:00am

Well, finding them isn't too hard.. the efficiency bit however is..
Is suppose I could put up flags. That would give O(n²) worst case. ::[hide]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.[/hide]::
Up to 32 or 64 nodes could probably be done linearly (with some tinkering anything up to a fixed number N could probably work) ::[hide]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[/hide]::

Title: Re: Graph Roots
Post by william wu on Dec 10^th, 2003, 10:41pm

Vaguely recalling some old algorithms material, I think we can do it in linear time by [hide]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.[/hide]

Title: Re: Graph Roots
Post by TenaliRaman on Dec 10^th, 2003, 11:22pm

I was thinking the same thing william.
::[hide]
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(n²) 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 :)
[/hide]::

Title: Re: Graph Roots
Post by towr on Dec 11^th, 2003, 12:04am

what's DFS?

Title: Re: Graph Roots
Post by william wu on Dec 11^th, 2003, 12:40am

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

::
[hide]
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 G_ij 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 G^R (reversal of G), all we have to do is multiply all entries in this matrix by (-1).

[/hide]
::

Title: Re: Graph Roots
Post by towr on Dec 11^th, 2003, 12:56am

on 12/11/03 at 00:40:44, william wu wrote:

DFS is depth-first search

ah.. I know that one.. I'm just not good with abbreviations..

Title: Re: Graph Roots
Post by James Fingas on Dec 11^th, 2003, 4:03am

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)

Title: Re: Graph Roots
Post by Dudidu on Dec 11^th, 2003, 7:31am

Everybody hi,
I see that everybody started working on the 3^rd 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 (2^nd sub-question) and (maybe) the 3^rd 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...

Title: Re: Graph Roots
Post by TenaliRaman on Dec 20^th, 2003, 3:15am

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 ???

Title: Re: Graph Roots
Post by Dudidu on Dec 21^st, 2003, 1:17am

on 12/20/03 at 03:15:19, 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...
[hide]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.[/hide]
If you need more help, you know were to find me...

Title: Re: Graph Roots
Post by TenaliRaman on Dec 21^st, 2003, 10:33pm

Dudidu,
i appreciate anyone helping me out (unless ofcourse if you are a Vogon ;D)
Btw,
whatever u said is what i thought initially after seeing yours and James post!!
::[hide]
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!
[/hide]::

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.

Title: Re: Graph Roots
Post by James Fingas on Dec 22^nd, 2003, 9:59am

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).

Title: Re: Graph Roots
Post by TenaliRaman on Dec 23^rd, 2003, 11:51am

As i said, i was looking at James' solution in a wrong perspective.

Thanks for the clarification James and thanks to Dudidu as well.