3 ms·

Not all graphs are trees, but all the graphs in this article are trees. They are DAGs, which are a deduplicated representation of trees.

IshKebab 3y ago
A DAG is not a tree. It literally has graph in the name. In a tree each node has exactly one parent / incoming edge. Not the case for DAGs.
- olejorgenb 3y ago
  Guess the parent means that it's relatively straight forward to converted a DAG to a tree by duplicating nodes (or rather, sub-graphs) having multiple parents.
  - IshKebab 3y ago
    Yeah I think so but that doesn't mean a DAG is a tree.
- kazinator 3y ago
  In the area of programming languages and compilers, we usually have trees without parent links, with substructure sharing, which are DAGs. We call them trees because most of the code operating on them thinks they are. E.g. the Lisp expression (+ a (* b b)), informally called a syntax tree, is actually a DAG. Both apparent instances of the b symbol are actually graph edges leading to the same symbol object. Moreover, nothing points to its parent; that would be horrible. Other kinds of trees don't always have parent pointers. For instance search trees like red-black can be implemented with parent pointers, or without; e.g. with functional recursion.
  - IshKebab 3y ago
    > E.g. the Lisp expression (+ a (* b b)), informally called a syntax tree, is actually a DAG That is a syntax tree. Syntactically it is a tree. The fact that you have a later step that recognises that the `b` identifiers refer to the same object and turn it into a DAG doesn't mean it isn't a tree initially.
    - kazinator 3y ago
      Most of the time when the word "tree" is used in this context, it is in reference to that DAG, not the printed version. E.g. see the tree and tree-structure glossary entries in ANSI CL. https://www.lispworks.com/documentation/lw61/CLHS/Body/26_glo_t.htm https://www.lispworks.com/documentation/lw61/CLHS/Body/26_gl...

IshKebab 3y ago

A DAG is not a tree. It literally has graph in the name. In a tree each node has exactly one parent / incoming edge. Not the case for DAGs.

olejorgenb 3y ago
Guess the parent means that it's relatively straight forward to converted a DAG to a tree by duplicating nodes (or rather, sub-graphs) having multiple parents.
- IshKebab 3y ago
  Yeah I think so but that doesn't mean a DAG is a tree.
kazinator 3y ago
In the area of programming languages and compilers, we usually have trees without parent links, with substructure sharing, which are DAGs. We call them trees because most of the code operating on them thinks they are. E.g. the Lisp expression (+ a (* b b)), informally called a syntax tree, is actually a DAG. Both apparent instances of the b symbol are actually graph edges leading to the same symbol object. Moreover, nothing points to its parent; that would be horrible. Other kinds of trees don't always have parent pointers. For instance search trees like red-black can be implemented with parent pointers, or without; e.g. with functional recursion.
- IshKebab 3y ago
  > E.g. the Lisp expression (+ a (* b b)), informally called a syntax tree, is actually a DAG That is a syntax tree. Syntactically it is a tree. The fact that you have a later step that recognises that the `b` identifiers refer to the same object and turn it into a DAG doesn't mean it isn't a tree initially.
  - kazinator 3y ago
    Most of the time when the word "tree" is used in this context, it is in reference to that DAG, not the printed version. E.g. see the tree and tree-structure glossary entries in ANSI CL. https://www.lispworks.com/documentation/lw61/CLHS/Body/26_glo_t.htm https://www.lispworks.com/documentation/lw61/CLHS/Body/26_gl...