Skip to content

Latest commit

 

History

History
444 lines (345 loc) · 21.9 KB

methods.md

File metadata and controls

444 lines (345 loc) · 21.9 KB

Methods

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

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]).

core.rank_to_pit

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.

Serial orderings

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.

core.seq_dfs_from_pit — depth-first, d2u

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), or topo.ordering("dfs", upa=upa)), which puts the main stem straight after the outlet and gives it consecutive positions. This is the order of the released seq_dfs layers 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.

core.seq_bfs_from_pit — breadth-first, d2u

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.

core.seq_topo_from_source — topological sort, u2d

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.

parallel.seq_bfs_from_pit — breadth-first with threads, d2u

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.

Layerings

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.

core.layering_asap — as soon as possible

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.

core.layering_cfds — conflict-free downstream

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.

core.layering_alap — as late as possible

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.

Spatial partitions

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.

partition(topo, n_parts, level="basin")

Every basin stays whole. A dominant basin cannot be split, so it is the heaviest subregion.

partition(topo, n_parts, level="subbasin")

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.

Kernels

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.

upstream_area

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.

distance_to_outlet

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.

longest_upstream_path

Propagates the largest flow length downstream seen upstream, then subtracts the cell's own. Takes the output of distance_to_outlet.

strahler_order

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.

Supporting structures

core.d8_to_downstream

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.

core.unknown_codes

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.

core.upstream_count, core.upstream_table

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.

core.basin_labels

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.

geodist

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.

core.dfs_interval, raster.dfs_interval_geotiff

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.

raster

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.

layering.Decomposition, layering.reverse_layers

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.

api.FlowTopo

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.

Threaded forms

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.

Locality metrics

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.

Provenance

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.