In dSHARP-CMU/pathfinder: Topology Navigation And Manipulation Functions

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)

library(pathfinder)

Starting with an igraph object, specify edge bundles that must be traversed by using a list of edge indices:

# A small subset of road data from Pittsburgh
pgh_graph

pgh_distances

# Edges belonging to Pittsburgh bridges
pgh_bundles

greedy_search() will traverse the graph by walking a path from the starting vertex to the nearest edge bundle, crossing that bundle, then finding the next closest bundle, until all bundles have been crossed at least once. By setting cheat = TRUE you can allow bundles to be crossed more than once if there is no other option to do so.

penalized_run <- greedy_search(pgh_graph, 
                               edge_bundles = pgh_bundles, 
                               distances = pgh_distances)

render_pathway_plot <- function(graph, bundles, distances, pathway) {
  plot_graph <- decorate_graph(graph, bundles, distances)

  # In this case we're looking at 
  plot_layout <- cbind(
    V(plot_graph)$lon,
    V(plot_graph)$lat
  )

  pathway_augmented <- augment_edges(pathway)

  plot(plot_graph, 
       layout = plot_layout,
       vertex.size = 0.1, 
       vertex.label = NA, 
       edge.label = NA, 
       curved = FALSE, 
       edge.arrow.mode = 0,
       edge.color = c(path = "blue", bundled = "red", none = "gray80")[pathway_augmented$edge_type],
       edge.width = c(path = 2, bundled = 3, none = 0.2)[pathway_augmented$edge_type])
}

render_pathway_plot(pgh_graph, pgh_bundles, pgh_distances, penalized_run)

By setting cheat = FALSE you will prohibit re-crossing, however this may result in uninishable paths.

strict_run <- greedy_search(pgh_graph, 
                              edge_bundles = pgh_bundles, 
                              distances = pgh_distances, 
                              cheat = FALSE)

render_pathway_plot(pgh_graph, pgh_bundles, pgh_distances, strict_run)

Tidying methods are also available to get summary statistics on resulting pathways at different levels of resolution:

One line per pathway: