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.

Improve this question
$\endgroup$
9
  • 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 17:20

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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