Stream networks and graph theory

Posted on Updated on

network

Rivers are organized as networks. They start out as small rills and rivulets and grow downstream to become large streams unless water extraction, transmission losses or evaporation dominate. In terms of graph theory, you can think of stream networks as directed acyclic graphs (DAG). The stream network of one drainage basin is a tree routed at the outlet. To be more precise, this kind of tree is an anti-arborescence or in-tree, i.e. all directions in the directed graph lead to the outlet. Usually, stream networks are binary trees, i.e. there is a maximum of two branches or parents entering each node. However, nodes may sometimes have more than two branches at confluences where three and more rivers meet. All drainage basins form a forest of trees and each tree is a so-called strongly-connected component.

Why bother with the terms of graph theory? Because it will make a couple of TopoToolbox functions much more accessible. The function klargestconncomps, for example, has an awkward name that I adopted from graph theory. What does it do? It extracts the k largest trees from a stream network. The function STREAMobj2cell takes all trees and puts each into a single element of a cell array. FLOWobj2cell does the same for an entire flow network. The computational basis of STREAMobj and FLOWobj relies on topological sorting of directed graphs. Thanks to graph theory, this trick makes flow-related computations in TopoToolbox much faster than in most common GI-systems.

Graph theory has a lot to offer for geomorphometry and I think that this potential has not yet fully been explored.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s