Author |
Topic: Reconstruct tree from triples (Read 3074 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Reconstruct tree from triples
« on: Dec 8th, 2012, 12:31pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reconstruct tree from triples
« Reply #1 on: Dec 8th, 2012, 2:28pm » |
Quote Modify
|
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.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Reconstruct tree from triples
« Reply #2 on: Dec 8th, 2012, 10:50pm » |
Quote Modify
|
on Dec 8th, 2012, 2:28pm, towr wrote:| but do we have all n^3 triples? |
|
There is no such assumption, and the triples should not determine a unique tree.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Reconstruct tree from triples
« Reply #3 on: Dec 10th, 2012, 8:56am » |
Quote Modify
|
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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reconstruct tree from triples
« Reply #4 on: Dec 10th, 2012, 11:03pm » |
Quote Modify
|
on Dec 10th, 2012, 8:56am, 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.
|
| « Last Edit: Dec 10th, 2012, 11:12pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Reconstruct tree from triples
« Reply #5 on: Dec 11th, 2012, 2:28am » |
Quote Modify
|
on Dec 10th, 2012, 11:03pm, 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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reconstruct tree from triples
« Reply #6 on: Dec 11th, 2012, 9:15am » |
Quote Modify
|
on Dec 11th, 2012, 2:28am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Reconstruct tree from triples
« Reply #7 on: Dec 12th, 2012, 7:59am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Reconstruct tree from triples
« Reply #8 on: Dec 12th, 2012, 9:38am » |
Quote Modify
|
on Dec 12th, 2012, 7:59am, 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 ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reconstruct tree from triples
« Reply #9 on: Dec 12th, 2012, 11:28am » |
Quote Modify
|
Yes, I guess I hadn't quite though it through far enough..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print