Class PITFill#

class flow.pitfilling.PITFill(*args, **kwargs)[source]#

Depression filling is an important preconditioning step to many landscape evolution models.

This class implements a linearly-scaling parallel priority-flood depression-filling algorithm based on Barnes (2016) algorithm.

Note

Unlike previous algorithms, Barnes (2016) approach guarantees a fixed number of memory access and communication events per processors.

The approach proposed in goSPL handles irregular meshes, allowing for complex distributed meshes to be used as long as a clear definition of inter-mesh connectivities is available. It also creates directions over flat regions allowing for downstream flows in cases where the entire volume of a depression is filled.

For inter-mesh connections and message passing, the approach relies on PETSc DMPlex functions.

Parallel (MPI) structure — the three Barnes (2016) phases:

  1. Per-tile flood (parallel). Each rank priority-floods its own partition (fill_tile) and emits a small spillover graph linking its local depression labels by their minimum spill elevation (graph_nodes / combine_edges).

  2. Global graph solve (serial, rank 0). The per-rank graphs are gathered, labels describing the same basin across a partition border are unified (_transferIDs() → _unifyLabels()), and a single priority-flood on the combined graph (_fillFromEdges() → fill_edges) computes each depression’s final water level. The graph scales with the partition perimeter (O(sqrt(N)) per tile), so — as in Barnes (2016) — this master solve is intentionally serial and cheap even on large meshes.

  3. Apply (parallel). Each rank raises its cells to the per-label water levels (fill_depressions).

Note

Cross-rank label unification (_unifyLabels()) is a single deterministic union-find pass that collapses each connected component of the equivalence graph to its minimum label — so the depression identifiers (and the filled surface) are independent of the MPI partition. The serial graph solve uses a compact (densely re-indexed) label space and a binary-heap priority queue, so its cost tracks the number of distinct spillover basins rather than the rank-dependent raw (globally-offset) label range.

The main functions return the following parameters:

  • the elevation of the filled surface,

  • the information for each depression (e.g., a unique global ID, its spillover local points and related processor),

  • the description of each depression (total volume and maximum filled depth).

Methods

fillElevation([sed])

This function is the main entry point to perform pit filling.

fillIceElevation(hl)

This function is the main entry point to perform pit filling for glacier.

Initialise

__init__(*args, **kwargs)

The initialisation of PITFill class consists in the declaration of PETSc vectors, matrices and each partition internals edge vertices.

Public Methods

fillElevation([sed])

This function is the main entry point to perform pit filling.

fillIceElevation(hl)

This function is the main entry point to perform pit filling for glacier.

Private Methods

_buildPitDataframe(label1, label2)

Definition of a Pandas Dataframe used to find unique pit ID across processors.

_sortingPits(df)

Sorts depressions number before combining them to ensure no depression index is changed in an unsorted way.

_unifyLabels(df, label)

Collapse cross-processor depression-label equivalence pairs into one canonical id per connected component using union-find (disjoint-set), then apply the mapping to label.

_offsetGlobal(lgth)

Computes the offset between processors to ensure unique number for considered indices.

_fillFromEdges(mgraph)

Combine local meshes by joining their edges based on local spillover graphs.

_transferIDs(pitIDs)

This function transfers local depression IDs along local borders and combines them with a unique identifier.

_dirFlats()

This function finds routes to spillover points on filled depressions to ensure downstream distribution if they are overfilled.

_getPitParams(hl, nbpits)

Define depression global parameters:

_performFilling(hl, level, sed)

_pitInformation(hl, level[, sed])

This function extracts depression information available to all processors.

Public functions#

PITFill.fillElevation(sed=False)[source]#

This function is the main entry point to perform pit filling.

It relies on the following private functions:

  • _performFilling

  • _pitInformation

Parameters:

sed – boolean specifying if the pits are filled with water or sediments.

PITFill.fillIceElevation(hl)[source]#

This function is the main entry point to perform pit filling for glacier.

It relies on the following private functions:

  • _performFilling

  • _pitInformation

Parameters:

sed – boolean specifying if the pits are filled with water or sediments.

Private functions#

PITFill._buildPitDataframe(label1, label2)[source]#

Definition of a Pandas Dataframe used to find unique pit ID across processors.

Parameters:

  • label1 – depression ID in a given processor

  • label2 – same depression ID in a neighbouring mesh

Returns:

df (sorted Dataframe of pit ID between processors)

PITFill._sortingPits(df)[source]#

Sorts depressions number before combining them to ensure no depression index is changed in an unsorted way.

Parameters:

df – Pandas Dataframe containing depression numbers which have to be combined.

Returns:

df sorted pandas dataframe containing depression numbers.

Note

Superseded by _unifyLabels() (union-find). Kept for reference / the standalone sort_ids kernel; no longer on the hot path.

PITFill._unifyLabels(df, label)[source]#

Collapse cross-processor depression-label equivalence pairs into one canonical id per connected component using union-find (disjoint-set), then apply the mapping to label.

df holds the global equivalence pairs (p1, p2) with p1 < p2 (two labels that are the same depression across a tile border). Each connected component is collapsed to its MINIMUM label by keeping the smaller label as the set root — matching the previous iterative sort_ids fixpoint, but in a single deterministic O(N α(N)) pass. Determinism (root = min, independent of pair order) is what makes the result identical regardless of the domain partition.

Parameters:

  • df – Dataframe of equivalence pairs, columns p1 < p2.

  • label – local depression-label array (globally-offset ids).

Returns:

label with every label remapped to its component minimum.

PITFill._offsetGlobal(lgth)[source]#

Computes the offset between processors to ensure unique number for considered indices.

Parameters:

lgth – local length of the data to distribute

Returns:

cumulative sum and sum of the labels to add to each processor

PITFill._fillFromEdges(mgraph)[source]#

Combine local meshes by joining their edges based on local spillover graphs.

Parameters:

  • mgraph – Numpy Array containing local mesh edges information

  • ggraph – Numpy Array containing filled elevation values based on other processors values

PITFill._transferIDs(pitIDs)[source]#

This function transfers local depression IDs along local borders and combines them with a unique identifier.

Parameters:

pitIDs – local depression index.

Returns:

number of depressions.

PITFill._dirFlats()[source]#

This function finds routes to spillover points on filled depressions to ensure downstream distribution if they are overfilled.

PITFill._getPitParams(hl, nbpits)[source]#

Define depression global parameters:

  • volume of each depression

  • maximum filled depth

Parameters:

  • hl – Numpy Array of unfilled surface elevation

  • nbpits – number of depression in the global mesh

PITFill._performFilling(hl, level, sed)[source]#

This functions implements the linearly-scaling parallel priority-flood depression-filling algorithm from Barnes (2016) but adapted to unstructured meshes.

Parameters:

  • hl – local elevation.

  • level – minimal elevation above which the algorithm is performed.

  • sed – boolean specifying if the pits are filled with water or sediments.

PITFill._pitInformation(hl, level, sed=False)[source]#

This function extracts depression information available to all processors. It stores the following:

  • the information for each depression (e.g., unique global ID, its spillover local points and related processor),

  • the description of each depression (total volume and maximum filled depth).

Parameters:

  • hl – local elevation.

  • sed – boolean specifying if the pits are filled with water or sediments.