I’m looking for some help on algorithms that may help generate a directed non-cyclic graph from a list of leaf nodes and the incomplete set of edge nodes taken to get to the leaf node.

For example, let’s say we have a node that has multiple edges to other nodes and we label the two edges from Node A “a:1”, “a:2”. At the end, we have a few leaf nodes and we’ve recorded the paths to get there as [“a:1”, “b:2”],[“a:2″,”c:1”]. Which would mean you can get there by the first edge of A and 2nd edge of B, or the 2nd edge of A and the first edge of C.

If we only describe the edge nodes, and either their full or partial unordered paths, what are some methods to generate trees that include those paths?

ex:

`leaf1 = ["a:1", "b:1"],["a:2","c:1"] leaf2 = ["a:2", "c:2"] leaf3 = ["c:3"] `

May generate something like:

or a little more cleanly,

What’s not important is unique edges, but rather if you’re ‘collecting information’ each time you pass through a node, that by the time you reach a leaf node you’ve you’ve collected the required information for all the leaf nodes. This may mean a single edge points to multiple leaf nodes as in the first example.

It seems like you would start by determining which options are subsets of one another, and then recursively start adding in the nodes which would lead to the most leaf nodes. The nodes with the most specific path would likely be the last nodes created. Or potentially creating the trees for each leaf node and then merging them together.

I couldn’t find an algorithm for this kind of generation, so even a starting point would help.