This question was originally posted here: https://stackoverflow.com/q/20735339/2305618
I am surely not the first to have implemented code to perform the following graph transformation. But try as I might, I can't find a previous reference to it.
The transformation arises when creating a single graph that simultaneously models hierarchical inclusion relationships and other pairwise relationships between nodes.
The algorithm transforms a rooted directed tree DAG into an equivalent hierarchical network DAG. Equivalence in this sense - if the meaning of the tree structure is that parents 'consist of' or 'contain' their children the equivalent network structure would carry the same 'consisting of' or 'containment' information.
The tree hierarchy is represented in the network as sub-networks and sub-sub-networks. The tree's exterior nodes are copied across and each interior node X is represented by the pair: X' and X''
Does anyone know the name/reference of this transformation/ algorithm? :-)
Illustration image of this transformation: