2
$\begingroup$

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: Illustration image of this transformation

Thanks

David

Improve this question
$\endgroup$
1
  • $\begingroup$ Please don't cross-post; that is forbidden by site rules. You should have picked only one site to post on (if you originally posted on the wrong site, you could have flagged it for moderator attention to ask them to migrate it). Now that you've cross-posted, you should pick one of them to ask to be closed. Also, please edit your question to include the image inline in the question, rather than as a link. $\endgroup$ – D.W.♦ Dec 23 '13 at 5:00
1
$\begingroup$

Your question contains the implicit assumption/premise that this transformation has a name. I don't know why you would expect it to have a special name. The transformation is not anything special or complicated and as far as I know it does not have any special name. It appears that you are just taking a tree, and making a second copy of it (with all edges reversed; with all nodes cloned), and then just gluing the two copies together (identifying both copies of each leaf).

For future reference, I don't think questions like "please tell me if this function has a special name" are a good fit for this site. This site is for technical questions that admit an objectively evaluable answer and that relate to a real problem you have. How do you expect to evaluate an answer that says "No, it doesn't have a special name"? There is no reference one can cite to back up that answer, and no objectively verifiable evidence one can provide to support such an answer. Moreover, questions about naming aren't a very good fit. How will knowing whether there is a special name help you solve a real problem? (If you were thinking "it might help me find references that help me solve problem X", then you would be better off by just describing problem X.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, I am interested in learning more about the transformation of tree DAGs (interpreted as describing decomposition/composition) into isomorphic hierarchical network DAGs (that express the same decomposition/composition). As my question says, this relates to work on creating a single model to encompass both hierarchical information and pair-wise relationships. $\endgroup$ – David Pratten Dec 23 '13 at 5:36
  • $\begingroup$ @DavidPratten, OK, but that's a different question. This is a question-and-answer site: we answer the question asked, so it's important to frame the question properly to make sure you're asking the right question (the question you actually care about). As to the substance: as others on StackOverflow have pointed out, the graphs are not isomorphic and they do not express the same "contains" relation. So, it's not clear to me what relationship between tree and network you are looking for. Perhaps you might think about how to make the desired relationship more precise. $\endgroup$ – D.W.♦ Dec 23 '13 at 5:47
  • $\begingroup$ @DW. Here is an example of the tree<->network relationship that I am curious about. Tree: Subtree rooted at B contains D, E and the subtree rooted at F. Network: Subnet B'B'' contains D, E and the subnet F'F''. There is a structural equivalence there. Perhaps the equivalence relation would be strengthened if the edges were undirected? $\endgroup$ – David Pratten Dec 23 '13 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.