Flow Routing#
Flow graph#
Defined in fastscapelib/flow/flow_graph.hpp
-
template<class G, class S = typename G::xt_selector, class Tag = flow_graph_fixed_array_tag>
class flow_graph# Main class used to compute or follow flow routes on the topographic surface.
- Template Parameters:
G – The grid type.
S – The xtensor container selector for data array members.
Tag – The flow graph implementation tag.
Public Types
-
using self_type = flow_graph<G, S, Tag>#
-
using operators_type = flow_operator_sequence<impl_type>#
-
using data_array_type = xt_array_t<xt_selector, data_type>#
-
using shape_type = typename data_array_type::shape_type#
-
using data_array_size_type = xt_array_t<xt_selector, size_type>#
-
using elevation_map = std::map<std::string, std::unique_ptr<data_array_type>>#
Public Functions
-
inline flow_graph(G &grid, operators_type operators)#
Flow graph constructor.
- Parameters:
grid – The grid object.
operators – The sequence of flow operators to use for updating the graph.
-
inline const std::vector<const flow_operator*> &operators() const#
Returns a vector of pointers to the flow operators objects used in this graph.
Note: the
flow_operator
base class has very limited polymorphism (i.e., only itsname
method is virtual). It is still possible to downcast the returned pointers (e.g., using the visitor pattern).
-
inline bool single_flow() const#
Returns
true
if the graph has single flow directions.
-
inline const std::vector<std::string> &graph_snapshot_keys() const#
-
inline self_type &graph_snapshot(std::string name) const#
Graph snapshot getter.
- Parameters:
name – Name of the snapshot.
-
inline const std::vector<std::string> &elevation_snapshot_keys() const#
Returns the names of the elevation snapshots.
-
inline const data_array_type &elevation_snapshot(std::string name) const#
Elevation snapshot getter.
- Parameters:
name – Name of the snapshot.
-
inline const data_array_type &update_routes(const data_array_type &elevation)#
Update flow routes from the input topographic surface.
This applies in chain the flow operators and takes snapshots (if any).
- Parameters:
elevation – The input topographic surface elevation.
- Returns:
Either the input elevation unchanged or the elevation that has been updated in order to route flow accross closed depressions.
-
inline size_type size() const#
Returns the total number of nodes in the graph (equals to the size of the grid).
-
inline shape_type grid_shape() const#
Returns the shape of the grid node arrays.
-
inline std::shared_ptr<impl_type> impl_ptr() const#
Returns a shared pointer to the flow graph implementation.
While this might be useful in some cases (e.g., Python bindings), in general accessing the implementation through
impl()
(const reference) should be preferred.
-
template<class C>
inline void set_base_levels(C &&levels)# Clear all existing base level nodes and set new ones.
- Template Parameters:
C – Any stl-compatible container type.
- Parameters:
levels – The indices of the new base level nodes.
-
inline xt_array_t<xt_selector, bool> mask() const#
Return a mask of where elements with a value
true
correspond to grid nodes that are not included in the flow graph.
-
template<class C>
inline void set_mask(C &&mask)# Set a new grid mask.
- Template Parameters:
C – Any xtensor-compatible container or expression type.
- Parameters:
mask – The new mask where elements with a value
true
correspond to grid nodes that are not included in the flow graph.
-
inline data_array_type accumulate(const data_array_type &src) const#
Traverse the flow graph in the top->down direction and accumulate locally produced quantities or fluxes.
The local quantitites or fluxes (i.e., source) may for example correspond to precipitation, surface water runoff, sediment flux, etc.
The accumulated values represent at each node of the graph the integral of the source over the node upslope contributing area.
For example, if the source units are meters (height), the units of the output accumulated values are cubic meters (volume).
- Parameters:
src – The source, must be given per area unit and have the same shape than
grid_shape
.- Returns:
The output accumulated values (array of same shape than
grid_shape
).
-
inline void accumulate(data_array_type &acc, const data_array_type &src) const#
Traverse the flow graph in the top->down direction and accumulate locally produced quantities or fluxes.
This version allows reusing a pre-allocated array to store the output.
Both
acc
andsrc
must of the same shape thengrid_shape
.- Parameters:
acc – The output accumulated values.
src – The source, must be given per area unit.
-
inline data_array_type accumulate(data_type src) const#
Traverse the flow graph in the top->down direction and accumulate locally produced quantities or fluxes.
- Parameters:
src – The spatially uniform source (scalar).
- Returns:
The output accumulated values (array of same shape than
grid_shape
).
-
inline void accumulate(data_array_type &acc, data_type src) const#
Traverse the flow graph in the top->down direction and accumulate locally produced quantities or fluxes.
Both
acc
andsrc
must of the same shape thengrid_shape
.- Parameters:
acc – The output accumulated values.
src – The spatially uniform source (scalar).
-
inline data_array_size_type basins()#
Delineate catchments (or basins).
A catchment is defined by all adjacent nodes that flow towards the same outlet (or pit) graph node.
Note
Results may be cached. All masked grid nodes have the same assigned catchment id set by the maximum limit of the integer value range. It is therefore preferable to mask the results prior to, e.g., plotting it.
- Returns:
Catchment ids (array of same shape than
grid_shape
).
Implementations#
Defined in fastscapelib/flow/flow_graph_impl.hpp
-
struct flow_graph_fixed_array_tag#
Fixed array flow graph implementation.
This implementation uses fixed shape arrays to store the graph topology (node receivers, donors, etc.).
Flow operators#
Defined in fastscapelib/flow/flow_operator.hpp
-
enum class fastscapelib::flow_direction#
Flow direction enum class.
Used as a tag to specify the kind of flow graph (i.e., single, multiple or undefined) expected as input or computed as output of a flow operator.
A
single
direction flow (directed acyclic) graph is a tree (or a forest of trees) where the total amount of matter (e.g., water, sediment) at each grid node is propagated to a unique (downslope) node neighbor. In amultiple
direction flow graph, that amount is partionned among one or more node neighbors.Use
undefined
for a flow operator that works on both single and multiple flow direction graphs or that do not use the graph (e.g., sink resolver only correcting the topographic elevation).Values:
-
enumerator undefined#
-
enumerator single#
-
enumerator multi#
-
enumerator undefined#
-
class flow_operator#
Flow operator.
It represents a logical unit that can read and/or modify in-place the flow graph and topographic elevation. It is a common type for flow routers, sink resolvers and snapshots (save intermediate graph and/or elevation states).
A flow operator may have one or more implementations, each relative to a specific flow graph implementation. Note: this class and its derived classes only contain the operators’ (static) properties and parameters (implementations are in separate classes).
Do not use this class directly (it has no implementation). Use instead its derived classes.
Subclassed by fastscapelib::flow_snapshot, fastscapelib::mst_sink_resolver, fastscapelib::multi_flow_router, fastscapelib::pflood_sink_resolver, fastscapelib::single_flow_router
Public Functions
-
inline virtual std::string name() const noexcept = 0#
Returns the name of the operator.
Public Static Attributes
-
static constexpr bool elevation_updated = false#
Whether the operator updates topographic elevation.
-
static constexpr bool graph_updated = false#
Whether the operator updates the flow graph.
-
static constexpr flow_direction in_flowdir = flow_direction::undefined#
The type of flow direction required as input of this operator.
-
static constexpr flow_direction out_flowdir = flow_direction::undefined#
The output flow direction type of this operator.
-
inline virtual std::string name() const noexcept = 0#
-
template<class FG>
class flow_operator_sequence# Immutable container of flow operators (e.g., flow routers, sink resolvers, flow snapshots) that are applied in chain when updating a flow graph.
This class is not intended to be used as a stand-alone container. It is used internally as an entity of flow_graph and can (should) be created implicitly in the flow_graph constructor.
- Template Parameters:
FG – The flow graph implementation type.
Public Functions
-
inline iterator_type begin()#
STL-compatible iterator pointing to the 1st operator.
-
inline iterator_type end()#
STL-compatible iterator pointing to the last operator.
-
inline bool elevation_updated() const#
Returns true if at least one operator in the sequence updates topographic elevation.
-
inline bool graph_updated() const#
Returns true if at least one operator in the sequence updates the flow graph.
-
inline flow_direction out_flowdir() const#
Returns the flow direction type (single, multiple or undefined) of the final state of the flow graph, after having applied all operators.
-
inline bool all_single_flow() const#
Returns true if all intermediate states of the flow graph have single flow directions.
-
inline bool snapshot_single_flow(std::string name)#
Returns true if the graph snapshot given by
name
is single flow.
-
inline const std::vector<std::string> &graph_snapshot_keys() const#
Returns the names of all flow graph snapshots to create.
-
inline const std::vector<std::string> &elevation_snapshot_keys() const#
Returns the names of all topographic elevation snapshots to create.
Flow routers#
Defined in fastscapelib/flow/flow_router.hpp
-
class single_flow_router : public fastscapelib::flow_operator#
Single direction flow router operator.
This flow operator routes all the flow passing through a grid node towards its neighbors node of steepest slope.
On a raster grid with 8-node connectivity, this is equivalent to the so-called “D8” algorithm [OCallaghanM84].
Public Functions
-
inline virtual std::string name() const noexcept override#
Returns the name of the operator.
Public Static Attributes
-
static constexpr bool graph_updated = true#
-
static constexpr flow_direction out_flowdir = flow_direction::single#
-
inline virtual std::string name() const noexcept override#
-
class multi_flow_router : public fastscapelib::flow_operator#
Multiple direction flow router operator.
This flow operator partitions the flow passing through a grid node among its downslope neighbor nodes. Flow partitioning is proportional to the local slope between a node and its neighbors (power relationship with a fixed exponent parameter).
The fraction \(f_{i,j}\) of flow routed from node \(i\) to its neighbor \(j\) is given by
\[ f_{i,j} = \frac{\max (0, S_{i, j}^p)}{\sum_{k \in N} \max (0, S_{i, k}^p)} \]where \(p\) is the slope exponent parameter, \(S_{i, j}\) is the slope between \(i\), \(j\) and \(N\) is the set of all neighbors of \(i\).
Depending on the value of the slope exponent parameter, this is equivalent to the methods described in Quinn et al. [QBCP91] or Holmgren [Hol94].
Public Functions
-
inline virtual std::string name() const noexcept override#
Returns the name of the operator.
-
inline multi_flow_router(double slope_exp)#
Create a new multi flow router operator.
- Parameters:
slope_exp – The flow partition slope exponent.
Public Members
-
double m_slope_exp = 1.0#
Public Static Attributes
-
static constexpr bool graph_updated = true#
-
static constexpr flow_direction out_flowdir = flow_direction::multi#
-
inline virtual std::string name() const noexcept override#
Sink resolvers#
Defined in fastscapelib/flow/sink_resolver.hpp
-
struct pflood_sink_resolver : public fastscapelib::flow_operator#
Priority-flood sink resolver operator.
This flow operator fills the closed depressions in the topographic surface using the priority flood algorithm +epsilon variant (Barnes et al., 2014). This variant prevents flat surfaces and hence ensure that the flow can be routed towards the outlets without disruption.
See Barnes et al. [BLM14] for a more detailed description of the algorithm.
Public Functions
-
inline virtual std::string name() const noexcept override#
Returns the name of the operator.
Public Static Attributes
-
static constexpr bool elevation_updated = true#
-
inline virtual std::string name() const noexcept override#
-
enum class fastscapelib::mst_route_method#
Method used by
mst_sink_resolver
to route flow within each closed depressions.The
basic
method is the most efficient one but does not result in a “realistic”, planar flow graph.The
carve
method mimics carving a narrow canyon within the depression.Values:
-
enumerator basic#
Connect the pit node directly to the depression spill node.
-
enumerator carve#
Revert the (unique) flow path between the spill and pit nodes.
-
enumerator basic#
-
class mst_sink_resolver : public fastscapelib::flow_operator#
Minimum Spanning Tree (MST) sink resolver operator.
This flow operator re-routes the flow trapped in closed depressions towards their spill, using an efficient algorithm that explicitly computes a graph of (inner and outer) basins and reduces it as a tree (Cordonnier et al., 2019).
It requires a single flow graph as input.
This operator also use the updated routes in closed depressions to fill these with nearly flat surfaces (a tiny slope ensure natural flow routing for the operators applied after this one).
See Cordonnier et al. [CBB19] for a more detailed description of the algorithm.
See also
Public Functions
-
inline virtual std::string name() const noexcept override#
Returns the name of the operator.
-
inline mst_sink_resolver(mst_method basin_method = mst_method::kruskal, mst_route_method route_method = mst_route_method::carve)#
Public Members
-
mst_method m_basin_method = mst_method::kruskal#
-
mst_route_method m_route_method = mst_route_method::carve#
Public Static Attributes
-
static constexpr bool graph_updated = true#
-
static constexpr bool elevation_updated = true#
-
static constexpr flow_direction in_flowdir = flow_direction::single#
-
static constexpr flow_direction out_flowdir = flow_direction::single#
-
inline virtual std::string name() const noexcept override#
Flow snapshots#
Defined in fastscapelib/flow/flow_snapshot.hpp
-
class flow_snapshot : public fastscapelib::flow_operator#
Flow snapshot operator.
A special flow operator used to save intermediate states of the flow graph and/or topographic elevation values while applying the other operators in chain.
Those saved states are accessible from the
flow_graph
object.Public Functions
-
inline virtual std::string name() const noexcept override#
Returns the name of the operator.
-
inline flow_snapshot(std::string snapshot_name, bool save_graph = true, bool save_elevation = false)#
-
inline const std::string &snapshot_name() const noexcept#
-
inline bool save_graph() const noexcept#
-
inline bool save_elevation() const noexcept#
-
inline virtual std::string name() const noexcept override#
Basin graph#
Defined in fastscapelib/flow/basin_graph.hpp
-
enum class fastscapelib::mst_method#
Algorithm used to compute the reduced graph (tree) of basins (minimum spanning tree).
Kruskal’s algorithm is rather simple and has non-linear complexity \(O(E \log V)\) where \(E\) is the number of basin connections and \(V\) is the number of basins.
Boruvka’s algorithm is more advanced and has linear complexity for planar graphs (most flow graphs are planar except, e.g., those built on raster grids with connectivity including the diagonals).
The gain in performance of Boruvka’s algorithm over Kruskal’s one is significant only for (very) large graphs.
Values:
-
enumerator kruskal#
Kruskal’s algorithm.
-
enumerator boruvka#
Boruvka’s algorithm.
-
enumerator kruskal#
-
template<class FG>
class basin_graph# Represents a graph of adjacent basins (catchments) connected via a two “pass” nodes where the water flow spills from one basin into another.
Such graph is built and used by
mst_sink_resolver
to resolve flow routing accross closed depressions in the surface topography.- Template Parameters:
FG – The flow graph implementation type (only
flow_graph_fixed_array_tag
is supported).
Public Types
-
using size_type = typename flow_graph_impl_type::size_type#
-
using data_type = typename flow_graph_impl_type::data_type#
-
using data_array_type = typename flow_graph_impl_type::data_array_type#
Public Functions
-
inline basin_graph(const flow_graph_impl_type &flow_graph_impl, mst_method basin_method)#
Create a new graph of basins from a flow graph.
Warning
A basin graph requires a flow graph with single direction flow paths as its current state. However, no validation is done here since the state of the same flow graph may later change from single to multiple direction after the basin graph has been (re)computed.
- Parameters:
flow_graph_impl – A flow graph implementation instance (fixed array).
basin_method – The algorithm used to compute the reduced tree of basins.
-
inline const std::vector<size_type> &outlets() const#
Returns a vector of node indices that represent the outlets of each of the basins in this graph.
-
inline const std::vector<size_type> &tree() const#
Returns the reduced graph (tree) of basins after applying the selected minimum spanning tree algorithm.
-
void update_routes(const data_array_type &elevation)#
Update (re-compute from-scratch) the graph and its reduced tree from the given topographic surface.
- Parameters:
elevation – The topographic surface elevation at each grid node.
-
inline size_t perf_boruvka() const#
Boruvka’s algorithm performance diagnostic.
Friends
- friend class testing::basin_graph_orient_edges_Test
-
struct edge#
Represents an edge of the graph of basins.
Public Members