In huoston/shortestpath: Shortest Path Algorithm Visualization

library(shortestpath)
library(knitr)
opts_chunk$set(dev = "svg")

set.seed(22)

The shortestpath package uses igraph's graph objects to represent graphs. However, additional attributes are added to the igraph graph in order to show the steps of finding a shortest path by the corresponding algorithm. The resulting object is called spgraph. In other words, spgraph is a subclass of igraph with required additional attributes.

spgraph

The spgraph is an igraph graph with the following additional attributes:

library(igraph)
graph <- make_graph("House") %>%
    as.spgraph()

print(graph)

spresults

Each algorithm (in this case dijkstra) returns an spresults object. An spresults object is a list of spgraphs, with each graph depicting a single iteration of the algorithm.

results <- dijkstra(graph, "A", "D")
print(results)
str(results, list.len=2)
head(lapply(results, function(step) step$min_dists), 3)

As a convenience, you can access graph attributes of the last iteration using spresults$attr:

# These are equivalent:
results[[length(results)]]$min_dists == results$min_dists

Probably the most interesting attributes are min_dists and shortest_path_predecessors:

results$min_dists
results$shortest_path_predecessors

The shortest path predecessors matrix consists of igraph.vs lists, which allows to reconstruct the actual shortest path. Each algorithm is able to indentfy all shortest paths: In the example above, there are two shortest paths from A to D.

To access individual elements of a matrix of lists in R, you have to use double brackets:

results$shortest_path_predecessors[["A","D"]]

Getting all shortest paths

You can use shortestpath's getShortestPaths() method to get a list of all shortest paths:

getShortestPaths(results)

Graph Modification

The shortestpath package provides many graph modification functions for spgraphs and igraphs that are used internally. Further details can be found in the R documentation: ?graphModification

par(mar = c(0,0,0,0))
g <- random.graph.game(10, 0.5) %>%
  setAlphabeticalVertexNames %>%
  setRandomEdgeWeights()

plot(g)
E(g)$weight

huoston/shortestpath documentation built on May 25, 2019, 8:18 a.m.