This example uses python graph-tool to convert a tangled tree into a regular tree. A tangled tree is a tree with some nodes with multiple parents, or, more precisely, a Directed Acyclic Graph with a node identified as root, in which not too many nodes have multiple parents.
Starting from this example tangled tree rooted in the node A:
Two different methods are presented: a simple algorithm yielding one of the shortest tree covering all nodes, and a more complex one that returns one of the longest. In both cases, for each node, its distance from the root is computed. The difference is that the shortest tree algorithm uses the shortest distance (by invoking the corresponding function in graph-tool), while the other one uses the longest distance (that’s a lot more difficult to compute. see this page for a description of an algorithm that leverages the topological sort of the graph).
By filtering the obtained graphs (imposing that the recursion level of a walk that starts from the root must be equal to the distance of the child node reached by an edge), the following results are obtained:
As we can see from the pictures, only the shortest (or longest) paths to the root are retained.
In some cases, longest trees are more useful than shortest. For example, if we consider nodes G, H and I, we can see that the edge from G to I is still indirectly represented in the longest tree (as a path from I to H to G). In the shortest tree instead, the information associated with the edge that goes from H to I is completely lost. Unfortunately, there are still many cases in which the information is lost forever even with longest trees (e.g. the edge from C to F).