Network Navigation
dblodgett@usgs.gov
Source:vignettes/articles/network_navigation.Rmd
network_navigation.RmdNavigation Modes
Network navigation traverses connections according to a set of rules.
There are four primary modes: upstream or downstream, and along the main
path only or including branches. In hydroloom, these are
upmain, downmain, up, and
down. Additional rules — a maximum distance, for example —
can be applied to any of the four.
hydroloom provides two functions for network
navigation.
-
navigate_network_dfs()requires the “flownetwork” representation of a hydrologic network (seeto_flownetwork()) and returns ids encountered along the requested navigation as a list of contiguous paths. -
navigate_hydro_network()requires the nhdplus representation of a hydrologic network (see the topological sort based network attributes article) and returns ids encountered along the requested navigation as a single vector.
Both functions accept the same navigation mode names:
upmain, downmain, up, and
down. navigate_hydro_network() also accepts
the NHDPlus shorthand UM, DM, UT,
and DD.
The two functions use different implementations.
navigate_network_dfs() runs a depth-first search over
upmain and downmain attributes on each
flownetwork connection. navigate_hydro_network() relies on
topo_sort, levelpath, and other nhdplus
attributes.
The rest of this vignette uses the new_hope sample
dataset included with hydroloom. A map and basic summary information are
shown below.
library(hydroloom)
library(sf)
hy_net <- sf::read_sf(system.file("extdata/new_hope.gpkg",
package = "hydroloom"))
nrow(hy_net)
#> [1] 746
class(hy_net)
#> [1] "sf" "tbl_df" "tbl" "data.frame"
names(hy_net)
#> [1] "COMID" "GNIS_ID" "GNIS_NAME" "LENGTHKM" "REACHCODE"
#> [6] "WBAREACOMI" "FTYPE" "FCODE" "StreamLeve" "StreamOrde"
#> [11] "StreamCalc" "FromNode" "ToNode" "Hydroseq" "LevelPathI"
#> [16] "Pathlength" "TerminalPa" "ArbolateSu" "Divergence" "StartFlag"
#> [21] "TerminalFl" "DnLevel" "UpLevelPat" "UpHydroseq" "DnLevelPat"
#> [26] "DnMinorHyd" "DnDrainCou" "DnHydroseq" "FromMeas" "ToMeas"
#> [31] "RtnDiv" "VPUIn" "VPUOut" "AreaSqKM" "TotDASqKM"
#> [36] "geom"
class(hy(hy_net, clean = TRUE))
#> [1] "hy_node" "hy" "tbl_df" "tbl" "data.frame"
names(hy(hy_net, clean = TRUE))
#> [1] "id" "length_km"
#> [3] "aggregate_id" "wbid"
#> [5] "feature_type" "feature_type_code"
#> [7] "stream_level" "stream_order"
#> [9] "stream_calculator" "fromnode"
#> [11] "tonode" "topo_sort"
#> [13] "levelpath" "pathlength_km"
#> [15] "terminal_topo_sort" "arbolate_sum"
#> [17] "divergence" "start_flag"
#> [19] "terminal_flag" "dn_stream_level"
#> [21] "up_levelpath" "up_topo_sort"
#> [23] "dn_levelpath" "dn_minor_topo_sort"
#> [25] "dn_topo_sort" "aggregate_id_from_measure"
#> [27] "aggregate_id_to_measure" "da_sqkm"
#> [29] "total_da_sqkm"
# map utilities
map_prep <- \(x, tol = 100) {
sf::st_geometry(x) |> # no attributes
sf::st_transform(3857) |> # basemap projection
sf::st_simplify(dTolerance = tol) # cleaner rendering
}
pc <- list(flowline = list(col = NA)) # to hide flowlines in basemap
oldpar <- par(mar = c(0, 0, 0, 0)) # par is reset in cleanup
hydrogeofetch::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
plot(map_prep(hy_net), col = "blue", add = TRUE)
NHDPlus-based network navigation
The nhdplus data model carries network attributes —
levelpath chief among them — that provide a shortcut to
“main” navigations. Flowlines from an upstream headwater down to the
outlet of a given levelpath share the same
levelpath id. Each feature also carries
up_levelpath and dn_levelpath, the
levelpath of the flowline upstream and downstream along the
main path.
levelpath is the key to the algorithm, but
navigate_hydro_network() also draws on
topo_sort, dn_toposort,
dn_minor_hydro, length_km, and
pathlength_km.
When working with data that uses the nhdplus data model,
navigate_hydro_network() runs with no pre-processing.
Below, all four navigation modes are demonstrated using the sample data
as it is provided in NHDPlusV2.
First, we can extract some key features that will help illustrate the network navigation functionality. In line comments illustrate what is being done.
# work in hydroloom attribute names for demo sake
hy_net <- hy(hy_net)
# the smallest topo_sort is the most downstream
outlet <- hy_net[hy_net$topo_sort == min(hy_net$topo_sort), ]
# features with the levelpath of the outlet are the mainpath,
# or mainstem of the network
main_path <- hy_net[hy_net$levelpath == outlet$levelpath, ]
# the largest topo sort along the main path is its headwater flowline
headwater <- main_path[main_path$topo_sort == max(main_path$topo_sort), ]
# basemap
par(mar = c(0, 0, 0, 0))
hydrogeofetch::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
# plot the elements prepped above
plot(map_prep(hy_net), col = "dodgerblue2", add = TRUE, lwd = 0.5)
plot(map_prep(outlet), col = "magenta", add = TRUE, lwd = 4)
plot(map_prep(headwater), col = "magenta", add = TRUE, lwd = 4)
plot(map_prep(main_path), col = "darkblue", add = TRUE, lwd = 1.5)
The path extracted above can be reproduced with a network navigation,
which is the more direct path for most applications. Below,
navigate_hydro_network() runs from a starting location,
with the distance parameter limiting how far the navigation
extends from the start point.
# this is just the ids
path <- navigate_hydro_network(hy_net,
start = outlet$id,
mode = "UM")
# filter the source data to get the id's representation
path <- hy_net[hy_net$id %in% path, ]
# pathlength_km is the distance from the furthest downstream network outlet
# it is used within navigate_hydro_network to filter to a given distance.
pathlength <- max(path$pathlength_km) - min(path$pathlength_km)
half_path <- navigate_hydro_network(hy_net,
start = outlet$id,
mode = "UM",
distance = pathlength / 2)
half_path <- hy_net[hy_net$id %in% half_path, ]
par(mar = c(0, 0, 0, 0))
hydrogeofetch::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
plot(map_prep(hy_net), col = "dodgerblue2", add = TRUE, lwd = 0.5)
plot(map_prep(half_path), col = "magenta", add = TRUE, lwd = 3)
plot(map_prep(path), col = "darkblue", add = TRUE, lwd = 2)
Next, look at up and down navigation —
“upstream with tributaries” and “downstream with diversions”, or “UT”
and “DD” in NHDPlus. For this demonstration, the start point is the top
of the half path found above. In practice, the start would be a known
location like a gage site.
start <- half_path[half_path$topo_sort == max(half_path$topo_sort), ]
up <- navigate_hydro_network(hy_net,
start = start$id,
mode = "up")
up <- hy_net[hy_net$id %in% up, ]
down <- navigate_hydro_network(hy_net,
start = start$id,
mode = "down")
down <- hy_net[hy_net$id %in% down, ]
par(mar = c(0, 0, 0, 0))
hydrogeofetch::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
plot(map_prep(hy_net), col = "dodgerblue2", add = TRUE, lwd = 0.5)
plot(map_prep(start), col = "magenta", add = TRUE, lwd = 4)
plot(map_prep(up), col = "darkblue", add = TRUE, lwd = 2)
plot(map_prep(down), col = "blue", add = TRUE, lwd = 2)
The four navigations above cover most common use cases when the nhdplus
attributes are available. The full nhdplus attribute suite is not always
available, though, and that is where navigate_network_dfs()
comes in.
Flownetwork-based navigation
navigate_network_dfs() performs up and
down navigation with only a network topology described as
id and toid. If upmain and
downmain attributes are also available, it performs main
path navigation as well.
The definitions of upmain and downmain in
the flow network context are worth a look:
hydroloom_name_definitions[names(hydroloom_name_definitions) == "upmain"]
#> upmain
#> "indicates that a given network element is the primary upstream connection at a confluence"
hydroloom_name_definitions[names(hydroloom_name_definitions) == "downmain"]
#> downmain
#> "indicates that a given network element is the primary downstream connection at a confluence"Building on the non-dendritic network example from
vignette("hydroloom"), the same five-edge network can carry
upmain and downmain attributes. The network
has one divergence and one confluence. Where id 1 appears
twice it has exactly one downmain == TRUE (the row
connecting to 4), and where toid 5 appears twice it has
exactly one upmain == TRUE (the row from 4). This is the
same divergence case study used in the non-dendritic
networks article, where it is shown in hy_node,
hy_topo, and hy_flownetwork form.
| id | toid | upmain | downmain |
|---|---|---|---|
| 1 | 2 | TRUE | FALSE |
| 1 | 4 | TRUE | TRUE |
| 2 | 3 | TRUE | TRUE |
| 3 | 5 | FALSE | TRUE |
| 4 | 5 | TRUE | TRUE |
| 5 | 0 | TRUE | TRUE |
hydroloom provides utilities to build this lightweight
flownetwork format from a geometric network via
make_attribute_topology(). upmain and
downmain attributes can be constructed using
add_divergence(), add_levelpaths(), and
to_flownetwork(). The sample data already carries
divergence and levelpath attributes, but
reconstructing them is shown below.
# select only id, name, feature_type.
# Note that the geometry is "sticky" and is included in base_net
base_net <- dplyr::select(hy_net, id, GNIS_NAME, feature_type)
# create a geometric network -- this includes divergences
base_net <- dplyr::left_join(make_attribute_topology(base_net, min_distance = 10),
base_net, by = "id") |>
sf::st_sf()
names(base_net)
#> [1] "id" "toid" "GNIS_NAME" "feature_type" "geom"
nrow(base_net)
#> [1] 832
# now switch from a flownetwork topology to a node topology.
base_net <- hydroloom::make_node_topology(base_net, add_div = TRUE, add = TRUE)
names(base_net)
#> [1] "id" "fromnode" "tonode" "GNIS_NAME" "feature_type"
#> [6] "geom"
nrow(base_net)
#> [1] 746
# divergence determination needs a dominant feature type input
unique(base_net$feature_type)
#> [1] "StreamRiver" "Connector" "ArtificialPath"
base_net <- add_divergence(base_net,
coastal_outlet_ids = outlet$id,
inland_outlet_ids = c(),
name_attr = "GNIS_NAME",
type_attr = "feature_type",
major_types = "StreamRiver")
names(base_net)
#> [1] "id" "fromnode" "tonode" "GNIS_NAME" "feature_type"
#> [6] "geom" "divergence"
nrow(base_net)
#> [1] 746
# now we can add a dendritic toid attribute because we have "divergence"
base_net <- add_toids(base_net, return_dendritic = TRUE)
# note that no rows were added -- these are only downmain!
nrow(base_net)
#> [1] 746
# now add a length attribute as the accumulated flowline length.
base_net$length_km <- as.numeric(st_length(base_net) / 1000)
base_net$weight <- accumulate_downstream(base_net, "length_km")
#> Dendritic routing will be applied. Diversions are assumed to have 0 flow fraction.
base_net <- add_levelpaths(base_net,
name_attribute = "GNIS_NAME",
weight_attribute = "weight")
names(base_net)
#> [1] "id" "toid" "levelpath_outlet_id"
#> [4] "topo_sort" "levelpath" "geom"
#> [7] "tonode" "GNIS_NAME" "feature_type"
#> [10] "divergence" "fromnode" "length_km"
#> [13] "weight"
# remove dendritic toid used above
base_net <- dplyr::select(base_net, -toid)
flow_net <- to_flownetwork(base_net)
nrow(flow_net)
#> [1] 832
names(flow_net)
#> [1] "id" "toid" "upmain" "downmain"The pipeline above transforms the data through several
hy subclasses. At each stage,
hy_capabilities() reports which hydroloom functions are
directly callable on the object’s current class and columns. Re-running
the pipeline with intermediate objects makes the progression
visible:
# 1. Raw load -- base hy with geometry only.
step1 <- hy(dplyr::select(hy_net, id, GNIS_NAME, feature_type))
class(step1)
#> [1] "hy" "sf" "tbl_df" "tbl" "data.frame"
hy_capabilities(step1)
#> add_toids make_node_topology
#> FALSE FALSE
#> to_flownetwork sort_network
#> FALSE FALSE
#> add_topo_sort add_levelpaths
#> FALSE FALSE
#> add_pathlength add_streamorder
#> FALSE FALSE
#> accumulate_downstream check_hy_graph
#> FALSE FALSE
#> navigate_hydro_network add_pfafstetter
#> FALSE FALSE
#> add_streamlevel add_divergence
#> FALSE FALSE
#> add_return_divergence subset_network
#> FALSE FALSE
#> navigate_network_dfs make_index_ids
#> FALSE FALSE
#> make_attribute_topology index_points_to_lines
#> TRUE TRUE
#> get_confluences add_hydro_location_distance
#> FALSE FALSE
#> index_hydro_location_distance get_subpath
#> FALSE FALSE
# 2. After make_attribute_topology + make_node_topology -- now hy_node.
step2 <- dplyr::left_join(
make_attribute_topology(step1, min_distance = 10),
step1, by = "id"
) |>
sf::st_sf() |>
make_node_topology(add_div = TRUE, add = TRUE)
class(step2)
#> [1] "hy_node" "hy" "sf" "data.frame"
hy_capabilities(step2)
#> add_toids make_node_topology
#> TRUE FALSE
#> to_flownetwork sort_network
#> FALSE FALSE
#> add_topo_sort add_levelpaths
#> FALSE FALSE
#> add_pathlength add_streamorder
#> FALSE FALSE
#> accumulate_downstream check_hy_graph
#> FALSE FALSE
#> navigate_hydro_network add_pfafstetter
#> FALSE FALSE
#> add_streamlevel add_divergence
#> FALSE TRUE
#> add_return_divergence subset_network
#> FALSE TRUE
#> navigate_network_dfs make_index_ids
#> FALSE FALSE
#> make_attribute_topology index_points_to_lines
#> TRUE TRUE
#> get_confluences add_hydro_location_distance
#> TRUE FALSE
#> index_hydro_location_distance get_subpath
#> FALSE FALSE
# 3. After add_divergence -- still hy_node, now with divergence so
# add_return_divergence becomes available.
step3 <- add_divergence(step2,
coastal_outlet_ids = outlet$id,
inland_outlet_ids = c(),
name_attr = "GNIS_NAME",
type_attr = "feature_type",
major_types = "StreamRiver")
class(step3)
#> [1] "hy_node" "sf" "hy" "data.frame"
hy_capabilities(step3)
#> add_toids make_node_topology
#> TRUE FALSE
#> to_flownetwork sort_network
#> FALSE FALSE
#> add_topo_sort add_levelpaths
#> FALSE FALSE
#> add_pathlength add_streamorder
#> FALSE FALSE
#> accumulate_downstream check_hy_graph
#> FALSE FALSE
#> navigate_hydro_network add_pfafstetter
#> FALSE FALSE
#> add_streamlevel add_divergence
#> FALSE TRUE
#> add_return_divergence subset_network
#> TRUE TRUE
#> navigate_network_dfs make_index_ids
#> FALSE FALSE
#> make_attribute_topology index_points_to_lines
#> TRUE TRUE
#> get_confluences add_hydro_location_distance
#> TRUE FALSE
#> index_hydro_location_distance get_subpath
#> FALSE FALSE
# 4. After add_toids(return_dendritic = TRUE) -- promotes to hy_topo,
# unlocking edge-list operations (sort_network, add_levelpaths,
# add_streamorder, accumulate_downstream, ...).
step4 <- add_toids(step3, return_dendritic = TRUE)
class(step4)
#> [1] "hy_topo" "hy" "sf" "data.frame"
hy_capabilities(step4)
#> add_toids make_node_topology
#> FALSE TRUE
#> to_flownetwork sort_network
#> FALSE TRUE
#> add_topo_sort add_levelpaths
#> TRUE TRUE
#> add_pathlength add_streamorder
#> TRUE TRUE
#> accumulate_downstream check_hy_graph
#> TRUE TRUE
#> navigate_hydro_network add_pfafstetter
#> TRUE FALSE
#> add_streamlevel add_divergence
#> FALSE FALSE
#> add_return_divergence subset_network
#> FALSE FALSE
#> navigate_network_dfs make_index_ids
#> TRUE TRUE
#> make_attribute_topology index_points_to_lines
#> TRUE TRUE
#> get_confluences add_hydro_location_distance
#> TRUE FALSE
#> index_hydro_location_distance get_subpath
#> FALSE FALSE
# 5. After add_levelpaths -- promotes to hy_leveled, unlocking
# add_pfafstetter, add_streamlevel, and to_flownetwork.
step4$length_km <- as.numeric(sf::st_length(step4) / 1000)
step4$weight <- accumulate_downstream(step4, "length_km")
#> Dendritic routing will be applied. Diversions are assumed to have 0 flow fraction.
step5 <- add_levelpaths(step4,
name_attribute = "GNIS_NAME",
weight_attribute = "weight")
class(step5)
#> [1] "hy_leveled" "hy_topo" "sf" "hy" "tbl_df"
#> [6] "tbl" "data.frame"
hy_capabilities(step5)
#> add_toids make_node_topology
#> FALSE TRUE
#> to_flownetwork sort_network
#> TRUE TRUE
#> add_topo_sort add_levelpaths
#> TRUE TRUE
#> add_pathlength add_streamorder
#> TRUE TRUE
#> accumulate_downstream check_hy_graph
#> TRUE TRUE
#> navigate_hydro_network add_pfafstetter
#> TRUE TRUE
#> add_streamlevel add_divergence
#> TRUE FALSE
#> add_return_divergence subset_network
#> FALSE FALSE
#> navigate_network_dfs make_index_ids
#> TRUE TRUE
#> make_attribute_topology index_points_to_lines
#> TRUE TRUE
#> get_confluences add_hydro_location_distance
#> TRUE FALSE
#> index_hydro_location_distance get_subpath
#> FALSE FALSE
# 6. After to_flownetwork -- becomes hy_flownetwork; navigate_network_dfs
# on upmain/downmain is now supported on this lightweight form.
step6 <- to_flownetwork(dplyr::select(step5, -toid))
class(step6)
#> [1] "hy_flownetwork" "tbl_df" "tbl" "data.frame"
hy_capabilities(step6)
#> add_toids make_node_topology
#> FALSE FALSE
#> to_flownetwork sort_network
#> FALSE FALSE
#> add_topo_sort add_levelpaths
#> FALSE FALSE
#> add_pathlength add_streamorder
#> FALSE FALSE
#> accumulate_downstream check_hy_graph
#> FALSE FALSE
#> navigate_hydro_network add_pfafstetter
#> FALSE FALSE
#> add_streamlevel add_divergence
#> FALSE FALSE
#> add_return_divergence subset_network
#> FALSE FALSE
#> navigate_network_dfs make_index_ids
#> TRUE TRUE
#> make_attribute_topology index_points_to_lines
#> FALSE FALSE
#> get_confluences add_hydro_location_distance
#> FALSE FALSE
#> index_hydro_location_distance get_subpath
#> FALSE FALSEEach transformation either changes the subclass or adds a column that
unlocks additional operations. The progression hy ->
hy_node -> hy_topo ->
hy_leveled -> hy_flownetwork is the
canonical path for working with non-dendritic NHDPlus-like data in
hydroloom.
The result is a flow network. The reconstruction wasn’t strictly
necessary — the demo NHDPlus data already carries every attribute needed
to build one — but it shows how the NHDPlus attributes map onto the
lighter flownetwork attributes. The hydroloom methods are nearly
identical to those of NHDPlus, with minor differences shown below:
nearly all upmain and downmain connections
agree, with a single junction differing.
The difference traces to how the divergence weight is computed.
hydroloom uses dendritic accumulation of flowline length (diversions get
0% of the upstream value) while NHDPlus uses unapportioned accumulation
(diversions get 100% of the upstream value). The resulting
upmain choice at one junction differs by a single
feature.
flow_net_nhdplus <- to_flownetwork(hy_net) |>
dplyr::arrange(id, toid)
flow_net_hydroloom <- to_flownetwork(base_net) |>
dplyr::arrange(id, toid)
different_downmain <- flow_net_nhdplus[flow_net_nhdplus$downmain != flow_net_hydroloom$downmain, ]
different_downmain
#> # hydroloom flow network (junction table): 0 connections, 0 diversions
#> # A tibble: 0 × 4
#> # ℹ 4 variables: id <int>, toid <dbl>, upmain <lgl>, downmain <lgl>
different_upmain <- flow_net_nhdplus[flow_net_nhdplus$upmain != flow_net_hydroloom$upmain, ]
different_upmain
#> # hydroloom flow network (junction table): 2 connections, 0 diversions
#> # A tibble: 2 × 4
#> id toid upmain downmain
#> <int> <dbl> <lgl> <lgl>
#> 1 8893470 8893552 TRUE TRUE
#> 2 8893472 8893552 FALSE TRUE
different_upmain <- hy_net[hy_net$id %in% c(different_upmain$id, different_upmain$toid), ]
par(mar = c(0, 0, 0, 0))
hydrogeofetch::plot_nhdplus(bbox = sf::st_bbox(different_upmain), plot_config = pc)
plot(map_prep(hy_net, 10), col = "dodgerblue2", add = TRUE, lwd = 0.5)
plot(map_prep(different_upmain, 10), col = "blue", add = TRUE, lwd = 2)
With a flownetwork in hand, the same navigations from earlier can be reproduced — this time using only the basic network, without any NHDPlus attributes.
# this is just the ids
path <- navigate_network_dfs(flow_net,
starts = outlet$id,
direction = "upmain")
# filter the source data to get the id's representation
path <- hy_net[hy_net$id %in% unlist(path), ]
# distance not yet supported
half_path <- navigate_network_dfs(flow_net,
starts = 8893396, # chosen from a map
direction = "downmain")
half_path <- hy_net[hy_net$id %in% unlist(half_path), ]
par(mar = c(0, 0, 0, 0))
hydrogeofetch::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
plot(map_prep(hy_net), col = "dodgerblue2", add = TRUE, lwd = 0.5)
plot(map_prep(half_path), col = "magenta", add = TRUE, lwd = 3)
plot(map_prep(path), col = "darkblue", add = TRUE, lwd = 2)
Now look at up and down navigation on the
flownetwork. The start point is the same feature picked from the map
above; in practice it would be a known location like a gage site.
# chosen from map
start <- hy_net[hy_net$id == 8893396, ]
up <- navigate_network_dfs(flow_net,
starts = start$id,
direction = "up")
up <- hy_net[hy_net$id %in% unlist(up), ]
down <- navigate_network_dfs(flow_net,
starts = start$id,
direction = "down")
down <- hy_net[hy_net$id %in% unlist(down), ]
par(mar = c(0, 0, 0, 0))
hydrogeofetch::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
plot(map_prep(hy_net), col = "dodgerblue2", add = TRUE, lwd = 0.5)
plot(map_prep(start), col = "magenta", add = TRUE, lwd = 4)
plot(map_prep(up), col = "darkblue", add = TRUE, lwd = 2)
plot(map_prep(down), col = "blue", add = TRUE, lwd = 2)