An interface for flow network traversals

[wkearn]

Most of the computations on FLOWobj and STREAMobj that we need to perform consist of one or more traversals of the flow network. Since these are both represented as topologically sorted edge lists, the traversal amounts to a for loop in the forward direction for a downstream traversal and in the backward direction for an upstream traversal.

The computations within the for loop typically involve an update step of the form

$$ d_v = d_v \oplus d_u \otimes w_{uv} $$

where $\oplus$ and $\otimes$ are the addition and multiplication operations in a semiring, in which the edge weights $w_{uv}$ are valued. This is a downstream traversal where $u$ is the source and $v$ is the target of the edge. Upstream traversals look the same, but the source is updated with information from the target:

$$ d_u = d_u \oplus d_v \otimes w_{uv} $$

These update steps with topologically sorted edges in a directed acyclic graph solve linear equations of the form $X = AX + B$ where matrix multiplication and addition take place within the semiring.

Algorithms used in TopoToolbox and the corresponding semirings are listed below. If we were using a language that provided more robust generic programming facilities, we might be able to use this structure to create a generic stream traversal where users could specify the semiring, and libtopotoolbox would run the traversal operation with that semiring. This is not really possible in C. What we can do instead is implement traversals for the semirings that we need, and then call the appropriate semiring traversal routine.

Flow network traversals

I have listed the functions as they are named in topotoolbox3, the direction of the traversal, the semirings that they use in the form $(S, \oplus, \otimes)$ where $S$ is the underlying set.

FLOWobj:

• dbentropy: upstream, $([0,1], +, \times)$
• dependencemap: upstream, $(\{0,1\}, \vee, \wedge)$
• drainagebasins: upstream, $(\{0,1\}^k, \vee, \wedge)$, with $k$ outlets.
• flowacc: downstream, $(\mathbb{R}^+, +, \times)$
• flowdistance: upstream/downstream, $(\mathbb{R}^+, \min/\max, +)$
• flowtime: upstream, $(\mathbb{R}^+, \min, +)$
• imposemin: downstream, $(\mathbb{R}, \min, +)$
• influencemap: downstream, $(\{0,1\}, \vee, \wedge)$
• propagatevaluesupstream: upstream, this could be a lot of different semirings.
• streamorder: downstream, Shreve stream order is $(\mathbb{N}, +, \times)$. Strahler stream order is a more complicated one.

STREAMobj

• cummaxupstream, upstream, $(\mathbb{R}, \max, +)$
• cumsum, upstream/downstream, $(\mathbb{R}, +, \times)$
• cumtrapz, upstream, $(\mathbb{R}, \max, +)$
• distance, upstream/downstream, $(\mathbb{R}, \min/\max, +)$
• imposemin, downstream, $(\mathbb{R}, \min, +)$
• meanupstream, downstream, $(\mathbb{R}, +, \times)$
• mincosthydrocon, upstream/downstream, $(\mathbb{R}, \min/\max, +)$ and $(\mathbb{R}, +, \times)$
• netdist, upstream/downstream, $(\mathbb{R},\min, +)$
• trunk, upstream, $(\{0,1\}, \vee, \wedge)$

I may have missed a few, and a lot of other functions use the propagatevaluesupstream variant that does not update the values. Some, including conncomps and klargestconncomps are also network traversals, but are currently implemented using linear algebra routines. However, we can see that we only need to implement traversals using a few different semirings to implement the majority of the FLOWobj and STREAMobj analysis functions.

• $(\mathbb{R}, +, \times)$ (also works for constrained intervals of $\mathbb{R}$)
• $(\mathbb{N}, +, \times)$
• $(\{0,1\}, \vee, \wedge)$
• the propagatevaluesupstream variant
• $(\mathbb{R}, \min, +)$
• $(\mathbb{R}, \max, +)$
• The Strahler stream order

I suggest we implement these in the file currently known as streamquad.c. We can replace the implementations of streamquad_trapz_* with implementations of traverse_up_*_add_mul. The recently added traverse_up_u32_and should be modified to traverse_up_u32_or_and to use the bitwise or operation and reflect its underlying semiring more accurately. traverse_down_f32_max_add already implements the downstream $\mathbb{R},\max, +)$ semiring. flow_accumulation_edgelist and drainagebasins could also be replaced with appropriate traversal implementations.

The streamquad.c traversals are designed for use with 1-indexed STREAMobj. I think we should make these 0 indexed, so they match our flow network interface (such as in flow_accumulation.c), and we should adjust the indices as needed in Python and MATLAB.

[wschwanghart]

Very cool, @wkearn! This seems a great way to formalize these operations into a unifying framework.