There is a professor Jiri Demel in Prague with Czech Technical University with a book "Graphs and their applications". Is this in any way a tribute to him? He is very wholesome guy that tought me graphs :).
A dag represents a partial ordering. (Strictly speaking you could have redundant edges in a dag which wouldn't change the partial ordering, so dag != partial order.)
upriver/downriver is the partial order relationship between nodes.
elevation is partway to a complete topological ordering -- as in, an assignment of elevations to nodes must follow the partial ordering, but there are multiple possible assignments in general, so it is a way to produce a set of elevation groupings but not the only way.
For example, if you have UP -> A -> B -> DOWN and UP -> X -> DOWN, then you could make elevation grouping {UP}, {A, X}, {B}, {DOWN} or {UP}, {A}, {B, X}, {DOWN} and both groupings satisfy the same partial ordering (and follow the same dags).
You could make a canonical elevation grouping by doing a breadth first search from the root node(s) and grouping by distance from the roots, or a different one by starting from the leaf/leaves. Though then the distinction between dags and partial orders comes in; your canonical grouping would have to be a BFS of a minimal dag without any "redundant" edges (any edge where removing it would not change the partial ordering).
You can't derive a dag or even just its partial ordering from either a topological ordering or an elevation grouping. Topological ordering A,B,C could come from A->B->C or from A->B, A->C (or the edgeless A, B, C!) Elevation grouping {A}, {B, C}, {D} could come from A->B->D, A->C->D or A->B->D, A->C.
I think you could order all of these from least information to most?:
1. topological ordering
2. elevation grouping
3. partial ordering
4. dag
No, a topological ordering is an actual ordering. It's putting all of the elements in a collection in some linear order based on dependencies between them.
The output of this language/library is a graph, not a linearization.
The river terminology is probably best described as a metaphor to help someone understand what a DAG is.
Not sure what that is, but DAGs represent "acyclic" binary relations (like "flows from x to y"), and acyclicity of a relation is a generalization of a partial order relation, which is itself a generalization of a total order relation.
Every time somebody tries to make a super-simplistic ASCII file format to make raw data "easy for humans", it either ends up sucking for humans, or sucking for computers, or both. I get it, the programmer is lazy, so the programmer finds a way to do something they find easier. But that's what gave us YAML and Markdown - the former setting us back in both data serialization and configuration formats, the latter setting us back in document formatting and layout.
It's 2025. Enough with the ASCII. As a human, if I want to map out and display a DAG, I don't want to do it in a text file. Give me a UI or give me death.
There is a professor Jiri Demel in Prague with Czech Technical University with a book "Graphs and their applications". Is this in any way a tribute to him? He is very wholesome guy that tought me graphs :).
edit: link https://kix.fsv.cvut.cz/~demel/grafy/
Unfortunately I cant find the book "Graphs and their applications".
Is there a PDF link?
There is this - https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf
But I was hoping for an English version?
and prof. Demlova too :) nice to see fellows from my alma mater here!
https://math.fel.cvut.cz/en/people/demlova/
Isn't this upriver/downriver/elevation terminology just a fancy/ignorant way of saying "topological ordering"?
A dag represents a partial ordering. (Strictly speaking you could have redundant edges in a dag which wouldn't change the partial ordering, so dag != partial order.)
upriver/downriver is the partial order relationship between nodes.
elevation is partway to a complete topological ordering -- as in, an assignment of elevations to nodes must follow the partial ordering, but there are multiple possible assignments in general, so it is a way to produce a set of elevation groupings but not the only way.
For example, if you have UP -> A -> B -> DOWN and UP -> X -> DOWN, then you could make elevation grouping {UP}, {A, X}, {B}, {DOWN} or {UP}, {A}, {B, X}, {DOWN} and both groupings satisfy the same partial ordering (and follow the same dags).
You could make a canonical elevation grouping by doing a breadth first search from the root node(s) and grouping by distance from the roots, or a different one by starting from the leaf/leaves. Though then the distinction between dags and partial orders comes in; your canonical grouping would have to be a BFS of a minimal dag without any "redundant" edges (any edge where removing it would not change the partial ordering).
You can't derive a dag or even just its partial ordering from either a topological ordering or an elevation grouping. Topological ordering A,B,C could come from A->B->C or from A->B, A->C (or the edgeless A, B, C!) Elevation grouping {A}, {B, C}, {D} could come from A->B->D, A->C->D or A->B->D, A->C.
I think you could order all of these from least information to most?: 1. topological ordering 2. elevation grouping 3. partial ordering 4. dag
No, a topological ordering is an actual ordering. It's putting all of the elements in a collection in some linear order based on dependencies between them.
The output of this language/library is a graph, not a linearization.
The river terminology is probably best described as a metaphor to help someone understand what a DAG is.
Not sure what that is, but DAGs represent "acyclic" binary relations (like "flows from x to y"), and acyclicity of a relation is a generalization of a partial order relation, which is itself a generalization of a total order relation.
Every time somebody tries to make a super-simplistic ASCII file format to make raw data "easy for humans", it either ends up sucking for humans, or sucking for computers, or both. I get it, the programmer is lazy, so the programmer finds a way to do something they find easier. But that's what gave us YAML and Markdown - the former setting us back in both data serialization and configuration formats, the latter setting us back in document formatting and layout.
It's 2025. Enough with the ASCII. As a human, if I want to map out and display a DAG, I don't want to do it in a text file. Give me a UI or give me death.