Every construction in the package, with where it comes from and what it costs. Notation:
N |
cells in the grid, nodata included |
E |
edges in the flow graph; for D8, about N |
L |
longest downstream path, in hops |
P |
threads |
K |
largest donor count of any cell; at most 8 for D8 |
B |
number of basins (the largest basin id when the ids are not 1 .. B) |
rank[i] is the number of downstream hops from cell i to its pit.
rank[pit] = 0; the headwater farthest from the pit in hops holds the largest value in its basin, and another
headwater can hold less (on idxs_ds=[1,2,2,2] the ranks are [2,1,0,1]).
Serial memoized chain tracing. A cell being traced is marked in progress, so a cycle is detected in constant time and every cell is resolved once.
Complexity: O(N) time, O(N) space.
Each returns a topologically sorted list of cell indices, ready for one
sequential pass. d2u means position 0 is a pit; u2d means position 0 is a
headwater. The two directions are reverses of each other.
Walks each basin depth-first from its pit, finishing one tributary subtree before starting the next. A cell's receiver therefore sits only a few positions back in the sequence, which is why this ordering has the lowest simulated cache miss rate of the three.
Which donor of a confluence is taken first is a choice, and there are two:
- by cell index, the default here;
- by upstream drainage area, largest first (
seq_dfs_from_pit(idxs_ds, upa), ortopo.ordering("dfs", upa=upa)), which puts the main stem straight after the outlet and gives it consecutive positions. This is the order of the releasedseq_dfslayers of FullTopo v1.1. A sequence taken from a released raster and one taken from the default here are different, even though both are topological orders of the same network.
Every kernel gives the same answer under either, since both are topological
orders: as returned (d2u) a receiver comes before its donors, which the
flow length downstream takes; reversed (u2d) a donor comes before its
receiver, which the upstream area, the flow length upstream and the Strahler
stream order take — up to the order the floating-point sums
at a confluence are added in, which for drainage area in float32 shows at
about 4e-6 of the value on the example basin. In float64 the two orders gave
the same value for every cell of that basin, which is a measurement and not a
guarantee: addition is not associative in float64 either.
Origin: Braun and Willett (2013), Geomorphology 180–181:170–179. Complexity: O(N) time, O(N + E) space.
A cell in a cycle has no place in any of these orders: it is left out of the sequence and marked
-1 in the layerings, so a sequence shorter than the valid-cell count is how a cycle shows.
The caller must check for cycles with (layers < 0) & mask. The value such a cell ends with
means nothing, and depends on the traversal: dfs and bfs start at the pits and never reach the
cells around a cycle, so it keeps what it started from, while topo starts at the sources and the
push manners of the as-soon-as-possible and conflict-free layerings, which schedule a cell that flows
into the cycle, write into it as that cell's receiver; their pull manner and the as-late-as-possible
layering, which schedules neither, leave it as it started. A grid with a cycle has to be refused, not
read.
Starts from every pit and expands upstream one ring of donors at a time, so the output is grouped by downstream hop count.
Origin: pyflwdir (Eilander et al., 2021, Deltares). Complexity: O(N + E) time, O(N + E) space.
Counts each cell's donors, starts from the headwaters, and releases a receiver when its last donor has been output. Needs only the donor counts, never a donor list, so it is the lightest of the three in memory.
Origin: Kahn (1962), "Topological sorting of large networks." Complexity: O(N) time, O(N) space.
The same sequence as the serial breadth-first form: each frontier's donors are counted and written across threads, between them a prefix sum over the frontier's cells.
Complexity: the donor lists are built serially, O(N); the counting and the writing are O(N/P + L) over L frontiers, and the prefix sums, serial, O(N) in all. O(N + E) space. Needs numba.
Each returns one layer index per cell, -1 outside the network. The members of
a layer are mutually independent, so a layer can be processed in any order or
all at once. The index grows toward the pit. Layer 0 holds every headwater in the as-soon-as-possible
form; the conflict-free form can hold a headwater back, and the as-late-as-possible form holds only the
farthest ones.
Every headwater in layer 0, every other cell one layer beyond its last-scheduled donor. Each cell lands in the earliest layer its dependencies allow, so most cells pile into the first layers. Reaches the minimum layer count, which the longest flow path sets.
Origin: Kahn (1962). Complexity: O(N) time, O(N) space.
As soon as possible, with one added rule: a ready cell whose receiver has already been claimed by another cell in the current layer waits for the next layer. No two cells of a layer then write into the same receiver.
That is what lets a threaded push run with no atomic and stay deterministic. It is also the only one of the three under which Strahler stream order can run under push at all. The confluence rule there is a comparison and a count, not one addition, so no single atomic operation applies. It can take more layers than the plain form: a held-back cell can hold back the next, confluence after confluence (on the example basin it adds none).
Complexity: O(N + E) time, O(N) space.
Per basin, layer = max_rank_in_basin - rank, so short tributaries are held
back to later layers rather than crowding into the first ones. Reaches the same
minimum layer count as the as-soon-as-possible form but spreads the work
differently, which changes the memory-access pattern.
Complexity: O(N) time, O(N + B) space.
Each returns a subregion index per cell, -1 outside the network. Both cut
along the drainage hierarchy, so no value crosses a subregion boundary while a
kernel runs, and both put contiguity first and balance second: on its land a
subregion is one piece, the two banks of a held-back mainstem counting as
touching, and the islands are added to the subregions of nearby land.
The units, whole basins or tributary subtrees, are the nodes of a graph whose
edges are their shared raster boundaries, weighted by the length of the
boundary; a basin of a single cell takes no part. Land is the largest components of that graph, at most one per
subregion: those of at least half an equal share, and the next largest too
when these have too few units to be cut into every subregion. Every other
component is an island and goes with its nearest land, so two components
share a subregion only when there are more of them than land can hold; when
no component is that large (an archipelago), METIS divides the components,
each linked to its nearest. The land
masses get the subregions so that the heaviest is as light as can be; and each mass is cut by contiguous
weighted METIS (best of four seeds: pymetis's METIS 5.1.0, or METIS 5.2.1, the
version FullTopo v1.1 was divided with, through FLOWTOPO_METIS_LIBRARY).
A unit heavier than an equal share of its mass is a subregion of its own first, together with the small
units it cuts off. Boundary units then move from heavier to lighter
neighbouring subregions until the heaviest is within imbalance_target
(default 1.005) of an equal share, no move helps, or ten moves a node have been
made; a unit whose departure
would cut its subregion in two takes the cut-off piece with it, or does not
move, and an island moves whole, to a subregion near it.
Every basin stays whole. A dominant basin cannot be split, so it is the heaviest subregion.
When whole basins are not within imbalance_target of an equal share, basins
are opened along their mainstems, found by walking upstream from the outlet and
taking the larger tributary at each confluence, into the tributary subtrees
that drain into the mainstem -- as few as the balance needs. Each round tries
the whole basins that can hold the balance up, each opened together with those
kept so far: in every subregion over the target, the heaviest, which it cannot
shed, and the heaviest bordering it; in the lightest subregion, the heaviest,
which it cannot grow around, and the heaviest bordering it (as a basin that
walls off a piece of land). A basin heavier than an equal share times
imbalance_target in a subregion over the target can never be balanced whole,
and the heaviest such is then the only one tried. They are tried the heaviest
first, at most OPEN_TRIALS (4), and a round stops at the first that brings the
plan within the target. The best has the lowest max/mean, then the least overload (how much the subregions over the mean exceed
it, in means); it is kept only when it lowers max/mean by OPEN_MIN_GAIN
(0.01) or more, or leaves the heaviest subregion no heavier and lowers the
overload by that much -- so a basin that lightens one of two equally heavy
subregions counts. The rounds stop at the target, at a round without such a
gain, or at four basins. The first basin opened is usually the dominant one
(when it has more than one source and is heavier than an equal share times
imbalance_target it is the only one tried, and opened if that gains enough), and a further one only a basin that
holds the balance up. A tributary is never
opened further. Each mainstem cell weighs with the
tributary that enters it. Above P_min, the most upstream mainstem cell where
a tributary of another subregion enters, the mainstem stays with the
subregion of its most upstream tributaries (its trunk); from P_min down,
P_min included, it depends on several subregions and is held back to a second
stage, marked flowtopo.MAINSTEM. The mainstem takes at each confluence the
tributary with the most cells upstream (on a tie the larger upstream area, then
the smaller cell index).
Complexity: the scan of the raster for the graph is O(N), and its boundary pairs are sorted to merge them; the partition works on the graph, whose nodes are basins and tributary subtrees, far fewer than the N cells: METIS is near-linear in its size, and a balance sweep sorts its candidates and runs a bounded connectivity search for each move it tries.
| kernel | shape | manners |
|---|---|---|
upstream_area |
many-to-one accumulation, linear | serial, pull, push, atomic_push |
distance_to_outlet |
one-to-one propagation | serial, and any layering |
longest_upstream_path |
many-to-one maximum, linear | serial, pull, push, atomic_push |
strahler_order |
many-to-one, non-linear | serial, pull, push |
All four are one pass over a structure: O(N) time serial, O(N) space beyond
the structure itself. Three of them also have a threaded form in
flowtopo.parallel, O(N/P + L) over L layers. Strahler stream order has none, since
its confluence rule is a comparison rather than an addition.
push writes into the receiver and is correct only where no two cells of a
layer share one, that is, under the conflict-free downstream layering.
atomic_push handles repeated receivers through np.add.at or
np.maximum.at. pull gathers from the donors, so a cell writes only to
itself; it needs the upstream adjacency table.
Accumulates a per-cell quantity downstream. Accumulates in float32 when
cell_area is float32 and in float64 otherwise, so counting cells with an
integer array stays exact:
a float32 total past about 2e5 km² no longer moves when one 90 m cell, about
0.007 km², is added to it, so pass float64 on a continental network.
Cumulative along-stream distance to the pit. One-to-one, so each cell is
written once and any layering is safe. Needs a d2u traversal, since a
receiver must be finished before its donors.
Propagates the largest flow length downstream seen upstream, then subtracts
the cell's own. Takes the output of distance_to_outlet.
Two branches of equal order meeting raise the order by one; otherwise the largest incoming order carries through. A comparison and a count rather than an addition, so no single atomic expresses it: under a layering the conflict-free push is the one that runs it in a single pass with no atomic.
Origin: Strahler (1957), Trans. Am. Geophys. Union 38:913–920.
The flattening of the D8 raster into one downstream pointer per cell. 247 is nodata; a second nodata code can be given for a grid that uses another. A cell draining off the grid, into nodata, or nowhere becomes a pit. The columns do not wrap: on a grid that spans every longitude, a cell draining across its east or west edge becomes a pit as well, and the basin is cut there. Give such a network on a window in which it lies whole.
Origin: pyflwdir (Eilander et al., 2021, Deltares). Complexity: O(N) time, O(N) space.
Counts codes the convention does not define. A non-empty result usually means the grid follows TauDEM or GRASS, which number their directions 1 to 8; read as powers of two, every undefined code becomes a pit.
Donors per cell, and the adjacency table the pull manner reads. The table
costs N × K entries, K being the largest fan-in, at most 8 for D8.
Origin: pyflwdir (Eilander et al., 2021, Deltares), for the count and its sentinel convention. Complexity: O(N + E) time, O(N·K) space.
One-based basin label per cell, from a d2u pass: a pit opens a basin and every
other cell copies its receiver's label. The labels number the pits in the order
the pass meets them, for the network given: they are not FlowDivide's
global_basin_id or local_basin_id. Required by the as-late-as-possible
layering and by both partitions.
Complexity: O(N) time, O(N) space.
Metres per degree from the WGS-84 series expansion, and the area of a lat-lon
pixel: on the sphere of radius 6 371 000 m by default, or on the WGS84
ellipsoid with model="wgs84" (FlowTopo(..., earth="wgs84")), the exact area
of the ellipsoid's zone.
Checked against pyproj: metres per degree agree to 1e-5, the series' own
accuracy. On the sphere, the cell area matches the closed-form spherical value
on square and non-square grids alike, and summing a whole-globe grid
reproduces 4 pi R squared.
Two approximations are worth knowing about, both small on a 3 arc-second grid and larger on a coarse one.
Cell-to-cell distance is planar, not geodesic: metres per degree are evaluated once and combined with Pythagoras, rather than solving the inverse geodesic problem. Over one 90 m cell the two agree far below the resolution of the data.
The latitude at which they are evaluated is the one between the two cell centres.
The depth-first interval of every cell, numbered within its basin, from its
position in the u2d depth-first sequence, its upstream cell count and the
outlets of the basins. The traversal finishes one basin before it starts the
next, so basin k takes the positions a_k to b_k: b_k is seq_dfs at
its outlet and a_k = b_k - upg + 1, upg at the outlet. Sorted by b, the
blocks must run from 0 to n - 1 one after another (a_k = b_(k-1) + 1); a
missing outlet, or a cell given as an outlet that is not one, breaks this and
is refused. A cell's basin is the block holding its position, found by binary
search on the b_k, and dfs_in = a + b - seq_dfs, the position read
downstream to upstream within the block, and dfs_out = dfs_in + upg - 1. A
depth-first traversal finishes a cell's upstream cells before it leaves them,
so they take exactly the positions dfs_in to dfs_out, and cell q drains
through cell p exactly when dfs_in[p] <= dfs_in[q] <= dfs_out[p]. The
whole sequence read backward, n - 1 - seq_dfs (the d2u sequence), differs
from dfs_in by a + b - (n - 1), a constant within each basin, and gives the
same intervals relative to each other. A cell with upg below 1 or more
upstream cells than its basin holds before it is refused: the inputs do not
belong together. So is a position held by two cells: the n cells lie in 0 to
n - 1, so a position held twice leaves another empty, which one bit for each
position finds. These checks cannot prove that seq_dfs is a depth-first
order of the flow network, which needs the flow directions: seq_dfs and
upg must come from the same flow network. The GeoTIFF form reads and writes one region, a strip of rows
at a time, reading seq_dfs once first for the outlets' positions; the
outlets come from the region's basin table, whose basin_cell_count is
checked against upg at each outlet. Given a larger upg, it reads the
window under seq_dfs, across the antimeridian when upg spans 360 degrees.
Origin: the ancestor test of a tree numbered in depth-first pre-order. Complexity: O(N log B) time for N cells in B basins. Beyond its output, the blocks of the B basins and one bit for each cell, the array form holds 2^24 cells at a time, after copying an input that is not stored in row order; the GeoTIFF form holds one strip of rows and one bit for each cell.
read_geotiff and write_geotiff, through rasterio. GridHeader carries the
shape, dtype, nodata, geotransform and CRS, and whether the coordinates are degrees
(latlon): a projected grid in metres is read as metres.
A layering is one layer index per cell; the kernels need the opposite view,
the members of each layer. Decomposition holds that as one flat array of
cell indices plus the offsets that cut it into layers, so a layer is a
zero-copy slice, and cells inside a layer stay in ascending index order.
reverse_layers flips a u2d layering into a d2u one for the
flow length downstream kernel.
Complexity: O(N log N) to build, one stable sort; O(N) space.
The front end. Wraps a D8 network, builds each structure on first use and caches it. Cached arrays are handed out read-only, so a caller cannot damage the cache by writing to a result.
flowtopo.parallel compiles the layer traversal with numba prange:
upstream_area, distance_to_outlet and longest_upstream_path, plus
seq_bfs_from_pit, which expands each frontier across threads. Requires
numba; without it its functions raise rather than pretending to use threads.
Feeds the interleaved (cell, receiver) access stream through a simulated N-way set-associative LRU cache, so the two arrays a traversal reads compete for one cache. Default geometry: 32 KB 8-way L1, 1 MB 16-way L2, 35.75 MB 11-way L3.
serial_locality reports, for one ordering: stride statistics, the row-jump
fraction, cache-line reuse interval, receiver distance, and the simulated miss
rate per level. parallel_locality reports, for one layering: intra-layer
span, gap statistics, cache-line footprint, receiver distance, and the miss
rate on the flattened layer order, so the two are directly comparable.
The median is the upper of the two middle values and a percentile the value at the rounded rank, the definitions the paper's numbers use; the receiver distance is taken over the cells that have a receiver (a pit has none).
The reuse interval is the number of accesses between two touches of the same cache line, found through a table of 2^20 lines: exact up to 16.7 million four-byte cells, and beyond that a line whose slot another line took in between counts as new. It is not the reuse distance of the cache literature, which counts the distinct lines touched in between and is the LRU stack distance.
The simulator is checked against an LRU written independently: the two agree exactly on the example basin and on random access sequences. Six further tests pin it to cases with a known answer, including the associativity boundary — eight lines per set fit, the ninth thrashes.
Complexity: O(A · W) time for A accesses and W ways, O(capacity) space.
The representation this package works on comes from pyflwdir (D. Eilander, Deltares and the Institute for Environmental Studies, Vrije Universiteit Amsterdam; MIT licence; 10.5281/zenodo.4287337). What FlowTopo takes from it:
- the flat downstream-pointer array: for every cell, the linear index of the cell it drains into, with a pit pointing at itself. Every structure and every kernel here is derived from that one array;
- the D8 decoding conventions: codes as powers of two clockwise from east, 0 and 255 terminal, 247 nodata, and a cell draining off the grid or into nodata treated as a pit;
- the donor-count array and its sentinel convention;
- the chain-tracing rank and the breadth-first sequence builder, in the variants set out above.
No pyflwdir source is included. The code here was written against those
conventions rather than copied from them, and FlowTopo.from_d8 takes the same
array pyflwdir.from_array(d8, ftype="d8") takes, so the two read the same
rasters.
The three layerings, the conflict-free downstream rule, the propagation manners, the locality metrics and the benchmark drivers are this project's own.