0
$\begingroup$

I am looking for a term:

How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences in the tree?

The resulting tree will contain all edges and nodes from the original DAG and a number of nodes multiple times.

A -> B
|    |
v    v
C -> D

Will be turned into:

A -> B -> D
|
v
C
|
v
D

If you need clarifications, please ask.

$\endgroup$
  • 1
    $\begingroup$ So the resulting tree is supposed to contain every path of the original DAG or how exactly does one construct your resulting tree? $\endgroup$ – rex123 Nov 5 '19 at 12:28
  • 1
    $\begingroup$ @rex123 I'm thinking OP might be talking about the tree $T$ of all reachable paths starting from a selected vertex $A$ in an input DAG. Each node correspond to a path that starts from $A$ and each edge in $T$ correspond to the relationship that a path extends to become another one. $\endgroup$ – Apiwat Chantawibul Nov 5 '19 at 12:39
  • 1
    $\begingroup$ If one try to list all paths in DAG without the common starting point condition, there might be two paths that one can not extends to become another. $\endgroup$ – Apiwat Chantawibul Nov 5 '19 at 12:41
  • 1
    $\begingroup$ Haven't seen or read an explicit name for that kind of tree. Maybe name it tree of all paths? $\endgroup$ – rex123 Nov 5 '19 at 16:07
  • 1
    $\begingroup$ The thing is, as you said yourself, this kind of tree is very redundant and essentially any graph or DAG already contains the information of all paths implicitly in it. So maybe you should ask what problem you eventually want to solve. $\endgroup$ – rex123 Nov 5 '19 at 17:20
1
$\begingroup$

I am not aware of any standard name for that kind of tree. One of the wonderful things about language is that we can describe things we don't already have a name for; there are many more interesting concepts than there are pre-existing widely-recognized names. I recommend that, if you find in your writing you need a concise name for it, you choose a name that seems suitable to you, and define it before first use.

$\endgroup$

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.