How to build a tree from a set of path fragments for leaf nodes

Question

I am looking for an algorithm to construct a possible top down tree structure when the only input data is path decisions (in random order) for the leaf nodes.

The path decisions is notaded with [nodeID]+ if the leaf node has passed through that node and [nodeID]- if the leaf node has not passed through that node. Example input:

One possible tree structure from the example input above would be:

The output should be a list of nodes and the node respective parent, like this:

As you can see the possible positions for each leaf node is not limited to one, since the input data is not complete paths. Leaf1 in the example can be a child of node D or node I.

There can be any number of leafs you get path data from, but only one single line of path data per leaf. There can be leafs you get no data from at all and you are not aware of how many total leafs there is in the tree. All nodes mentioned in path data should be present in the output table and only the calculated root shouldn’t have any parent assigned.

I guess one must somehow combine the facts from each Leaf paths, like from Leaf1 you know: A and E must not be in parallell lines, and from Leaf2 you know that A and I must not be in parallell lines, and so on ...

Preferable javascript but other language or pseudo code is also welcomed!

is there at most one input line per leaf, or can there be several input lines that correspond to the same leaf? — tucuxi
In your example, you show none of the leaf nodes and there need to be at least 5 of them. But you have data for 4. Is your data supposed to be for some of the leaf nodes, or all of them? — btilly
@btilly there are many different possible trees that can be constructed using the fragmented path info from the 4 leaf nodes. I only showed one possible ”solution”. The leafs are supposed to sit below the end nodes, and in this example there are only 4, not 5. I need an algorithm that build a tree structure where all leaf paths is valid. In the example there are only 4 paths. Input table and export table is the only important things (the tree is there for visualization only.) — Plarsen
There are more than 4 leafs, but only path data from 4 leafs. — Plarsen

btilly btilly · Accepted Answer · 2019-06-26T17:29:02

Since nobody answered, I'll give some partial thoughts.

You start with:

1: [A+, E+, H-]
2: [B-, A+, I+, D-]
3: [K+, G+, E+, C-]
4: [H+, A-, G-]

First, search for nodes that only appear with a +. Make those roots. Scanning this, we can do that for nodes E, I, and K. So our answer starts with:

E
E I
I K

And our path data is simplified to:

1: [A+, H-]
2: [B-, A+, D-]
3: [G+, C-]
4: [H+, A-, G-]

And now we have a partition operation. For this we make a graph where 2 nodes are connected iff they appear together with a +. We then separate nodes by connected components, and separate leaves into partitions where there is a + (any leaf without a partition can be made a leaf right there in the tree and then dropped). Deleting any - that is taken care of by this separation. In our case this is a totally disconnected graph which puts each node into its own partition and divides the path data into 3 groups (note, we lose all - rules which are explained by the partitioning):

1: [A+]
2: [A+]

3: [G+]

4: [H+]

And now we solve each problem, coming to a final solution of:

E
E I
I K
K A
K B
K C
K D
K G
K H

I believe that this approach will only fail to make progress in the case where no tree is possible. If there is a tree to be found, it will find one.

How to build a tree from a set of path fragments for leaf nodes

1 Answers