Network Navigation

dblodgett@usgs.gov

Network Navigation

One of the most common operations with hydrologic and hydrographic networks is referred to as “navigation”. To “navigate” the network is the action of traversing network connections according to a set of rules. There four primary types of network navigation, two in the upstream direction and two in the downstream direction and only along a main path or including branches. In hydroloom, these navigation types are referred to as upmain, downmain, up and down. Additional rules, such as a desired maximum distance, can be applied to any of the four types.

Hydroloom has two functions that support network navigation.

  1. navigate_network_dfs(), requires the “flownetwork” representation of a hydrologic network (see to_flownetwork()) and returns ids encountered along the requested navigation as a list of contiguous paths.
  2. navigate_hydro_network() currently (5/2024) requires the nhdplus representation of a hydrologic network (see vignette("advanced_network")) and returns ids encountered along the requested navigation as a single vector.

While similar, the two functions use completely different implementations. navigate_network_dfs() uses a graph-theoretic “depth first search” with upmain and downmain attributes for all flownetwork connections. navigate_hydro_network() relies on topo_sort, levelpath, and other nhdplus attributes to support network navigation.

For the rest of this vignette, we will use the new_hope sample dataset included with hydroloom. A map some basic summary information about the data are shown just 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"         "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) # sleaner 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
nhdplusTools::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
#> Zoom set to: 11

plot(map_prep(hy_net), col = "blue", add = TRUE)

NHDPlus-based network navigation.

The nhdplus data model has network attributes, like levelpath that provide a shortcut to “main” navigations. A path of flowlines that flow from a most upstream headwater to the outlet of a given levelpath in the network have the same levelpath id. Additionally, every feature has a up_levelpath and dn_levelpath indicating the levelpath of the flowline upstream and downstream along the “main” path respectively. These attributes, combined with relatively simple table operations, enable navigation up and down stream along the network. While levelpath attributes are the key to the algorithm, topo_sort, dn_toposort, dn_mino_hydro, length_km, and pathlength_km are also used to accomplish aspects of the algorithm implemented innavigate_hydro_network().

When working with data that uses the nhdplus data model, navigate_hydro_network() works with no pre-processing. Below, all network navigation modes are demonstrated using the sample data as is from 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))
nhdplusTools::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
#> Zoom set to: 11

# 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)

We can reproduce the path extracted above with a network navigation, which is a more natural approach for most applications. Below, we see how to use navigate_hydro_network from a starting location and use the distance parameter to limit how far we will navigate 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))
nhdplusTools::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
#> Zoom set to: 11
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 we can look at the more complete up and down navigation. Sometimes these are called “upstream with tributaries” and “downstream with diversions” or “UT” and “DD”. For demonstration sake, we will start at the top of the half path found above. More typically, this would be starting from a known location, such as where a gage site is located.


start <- half_path[half_path$topo_sort == max(half_path$topo_sort), ]

up <- navigate_hydro_network(hy_net, 
                             start = start$id, 
                             mode = "UT")
up <- hy_net[hy_net$id %in% up, ]

down <- navigate_hydro_network(hy_net,
                               start = start$id,
                               mode = "DD")
down <- hy_net[hy_net$id %in% down, ]

par(mar = c(0, 0, 0, 0))
nhdplusTools::plot_nhdplus(bbox = sf::st_bbox(hy_net), plot_config = pc)
#> Zoom set to: 11
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)