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

        riddles >> cs >> Reconstruct tree from triples
        
(Message started by: Barukh on Dec 8th, 2012, 12:31pm)
Title: Reconstruct tree from triples
Post by Barukh on Dec 8th, 2012, 12:31pm
You are given 2 sets of triples with information about relations between nodes of a tree:

The first set contains triples (u, v, w), meaning that the path from node u to node w passes through v.

The second set contains triples (u, v, w), meaning that the path from node u to node w does not pass through v.

Device an algorithm which creates a tree consistent with the above sets, or returns false if the triples are inconsistent.
Title: Re: Reconstruct tree from triples
Post by towr on Dec 8th, 2012, 2:28pm
How many of the possible triples do we have? I'm guessing at least every node must be represented in at least one triple, but do we have all n^3 triples? (Which would be a bit redundant, admittedly.)
Title: Re: Reconstruct tree from triples
Post by Barukh on Dec 8th, 2012, 10:50pm

on 12/08/12 at 14:28:36, towr wrote:
but do we have all n^3 triples?

There is no such assumption, and the triples should not determine a unique tree.
Title: Re: Reconstruct tree from triples
Post by birbal on Dec 10th, 2012, 8:56am
Do we know the number of total nodes in the tree? Assuming total number of nodes are n, this may work.

1. Make a graph of n nodes connected with 0 edges.
2. From the first set, start making edges - for a tuple (u, v, w), add one edge from u->v and another from v->w.
3. Try to convert the graph to a tree following second set of tuples. for example if we have a subgraph like
{(u->v->w), (x->y->w)}, w being the common node here. It can be merged in many ways like (u->v->x->y->w) or (x->y->u->v->w)...etc.
The challenge here is to see if any configuration is possible, which is consistent with 2nd set of tuples and results into a tree.
Title: Re: Reconstruct tree from triples
Post by towr on Dec 10th, 2012, 11:03pm

on 12/10/12 at 08:56:51, birbal wrote:
3. Try to convert the graph to a tree following second set of tuples.
Before this, I'd remove redundancy from the graph.  If there's an edge a->b, but also a longer path a-> .. ->b, then remove the edge from a->b
We know from the first set of tuples that we need a path between all successive nodes on the longer path anyway, so the direct edge is redundant.
I think this step should leave us with a forest, i.e. some number of unconnected trees.

Then the second set of tuples is only necessary to determine how to tie these different connected components of the graph together and to check our forest is valid. Because if they disagree with how we created the trees in the previous step, then they conflict directly with the first set of tuples.
One way to tie things together: if we have that a->b->c is disallowed, put a,c in a different subtree than b.
Title: Re: Reconstruct tree from triples
Post by birbal on Dec 11th, 2012, 2:28am

on 12/10/12 at 23:03:51, towr wrote:
Before this, I'd remove redundancy from the graph.  If there's an edge a->b, but also a longer path a-> .. ->b, then remove the edge from a->b
We know from the first set of tuples that we need a path between all successive nodes on the longer path anyway, so the direct edge is redundant.
I think this step should leave us with a forest, i.e. some number of unconnected trees.

Then the second set of tuples is only necessary to determine how to tie these different connected components of the graph together and to check our forest is valid. Because if they disagree with how we created the trees in the previous step, then they conflict directly with the first set of tuples.
One way to tie things together: if we have that a->b->c is disallowed, put a,c in a different subtree than b.

Yes this is required. Have you verified the solution we are arriving at will work everytime.
Also we need to take care of all possible merges of the nodes.
Title: Re: Reconstruct tree from triples
Post by towr on Dec 11th, 2012, 9:15am

on 12/11/12 at 02:28:40, birbal wrote:
Also we need to take care of all possible merges of the nodes.
I don't think that's necessary as a separate step.
Title: Re: Reconstruct tree from triples
Post by Grimbal on Dec 12th, 2012, 7:59am
The first step doesn't necessarily result in a definite set of trees.

If we have (a,b,d) and (a,c,d), we know we have a-b-c-d or a-c-b-d, but we don't know which one.  With more triplets, it can get quite complicated.  It is not obvious to check whether this can resolve to an actual tree that satisfies the second set of constraints.

Already the triplets (a,b,c) and (a,c,b) together cannot resolve to a tree.
Title: Re: Reconstruct tree from triples
Post by birbal on Dec 12th, 2012, 9:38am

on 12/12/12 at 07:59:22, Grimbal wrote:
The first step doesn't necessarily result in a definite set of trees.

If we have (a,b,d) and (a,c,d), we know we have a-b-c-d or a-c-b-d, but we don't know which one.  With more triplets, it can get quite complicated.  It is not obvious to check whether this can resolve to an actual tree that satisfies the second set of constraints.

Already the triplets (a,b,c) and (a,c,b) together cannot resolve to a tree.


Yes, it will give us a graph with 4 nodes (a,b,c,d) and 4 edges (a->b, a->c, b->d, c->d).
In the next step, we can choose any of the two configutations a-b-c-d or a-c-b-d such that it does not conflict with seconds set of rules. Does it makes sense ?
Title: Re: Reconstruct tree from triples
Post by towr on Dec 12th, 2012, 11:28am
Yes, I guess I hadn't quite though it through far enough..


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