distance_table

Shortest (directed or undirected) paths between vertices

distances calculates the length of all the shortest paths from or to the vertices in the network. shortest_paths calculates one shortest path (the path itself, and not just its length) from or to the given vertex.

Usage

distance_table(graph, directed = TRUE)
mean_distance(graph, directed = TRUE, unconnected = TRUE)
distances(
  graph,
  v = V(graph),
  to = V(graph),
  mode = c("all", "out", "in"),
  weights = NULL,
  algorithm = c("automatic", "unweighted", "dijkstra", "bellman-ford", "johnson")
)
shortest_paths(
  graph,
  from,
  to = V(graph),
  mode = c("out", "all", "in"),
  weights = NULL,
  output = c("vpath", "epath", "both"),
  predecessors = FALSE,
  inbound.edges = FALSE
)
all_shortest_paths(
  graph,
  from,
  to = V(graph),
  mode = c("out", "all", "in"),
  weights = NULL
)

Details

The shortest path, or geodesic between two pair of vertices is a path with the minimal number of vertices. The functions documented in this manual page all calculate shortest paths between vertex pairs.

distances calculates the lengths of pairwise shortest paths from a set of vertices (from) to another set of vertices (to). It uses different algorithms, depending on the algorithm argument and the weight edge attribute of the graph. The implemented algorithms are breadth-first search (‘unweighted’), this only works for unweighted graphs; the Dijkstra algorithm (‘dijkstra’), this works for graphs with non-negative edge weights; the Bellman-Ford algorithm (‘bellman-ford’), and Johnson's algorithm (‘"johnson"’). The latter two algorithms work with arbitrary edge weights, but (naturally) only for graphs that don't have a negative cycle.

igraph can choose automatically between algorithms, and chooses the most efficient one that is appropriate for the supplied weights (if any). For automatic algorithm selection, supply ‘automatic’ as the algorithm argument. (This is also the default.)

shortest_paths calculates a single shortest path (i.e. the path itself, not just its length) between the source vertex given in from, to the target vertices given in to. shortest_paths uses breadth-first search for unweighted graphs and Dijkstra's algorithm for weighted graphs. The latter only works if the edge weights are non-negative.

all_shortest_paths calculates all shortest paths between pairs of vertices. More precisely, between the from vertex to the vertices given in to. It uses a breadth-first search for unweighted graphs and Dijkstra's algorithm for weighted ones. The latter only supports non-negative edge weights.

mean_distance calculates the average path length in a graph, by calculating the shortest paths between all pairs of vertices (both ways for directed graphs). This function does not consider edge weights currently and uses a breadth-first search.

distance_table calculates a histogram, by calculating the shortest path length between each pair of vertices. For directed graphs both directions are considered, so every pair of vertices appears twice in the histogram.

References

West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.

Aliases

• distance_table
• mean_distance
• distances
• shortest.paths
• get.shortest.paths
• get.all.shortest.paths
• average.path.length
• path.length.hist
• all_shortest_paths
• shortest_paths

Examples

# NOT RUN {
g <- make_ring(10)
distances(g)
shortest_paths(g, 5)
all_shortest_paths(g, 1, 6:8)
mean_distance(g)
## Weighted shortest paths
el <- matrix(nc=3, byrow=TRUE,
             c(1,2,0, 1,3,2, 1,4,1, 2,3,0, 2,5,5, 2,6,2, 3,2,1, 3,4,1,
               3,7,1, 4,3,0, 4,7,2, 5,6,2, 5,8,8, 6,3,2, 6,7,1, 6,9,1,
               6,10,3, 8,6,1, 8,9,1, 9,10,4) )
g2 <- add_edges(make_empty_graph(10), t(el[,1:2]), weight=el[,3])
distances(g2, mode="out")

# }