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 or

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