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.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)
vcount(g
distances
every vertex must be included here at most once. (This
is not required for shortest_paths
.out
then the shortest paths from the vertex, if in
then to
it will be considered. INULL
and the graph has a weight
edge attribute, then the
attribute is used. If this is NA
then no weights are used (even if
the graph has a weight
i
in the tree is the
vertex from which vertex i
was reached. The predecessor of the start
vertex (in the from
argumei
in the tree is the edge via
which vertex i
was reached. The start vertex and vertices that were
not reached during the search will hdistances
a numeric matrix with length(to)
columns and length(v)
rows. The shortest path length from a vertex to
itself is always zero. For unreachable vertices Inf
is included.For shortest_paths
a named list with four entries is returned:
length(to)
; list
element i
contains the vertex ids on the path from vertex from
to vertex to[i]
(or the other way for directed graphs depending on
the mode
argument). The vector also contains from
and i
as the first and last elements. If from
is the same as i
then
it is only included once. If there is no path between two vertices then a
numeric vector of length zero is returned as the list element. If this
output is not requested in the output
argument, then it will be
NULL
.vpath
, but the
vectors of the list contain the edge ids along the shortest paths, instead
of the vertex ids. This entry is set to NULL
if it is not requested
in the output
argument.to
argument, or NULL
if it
was not requested.NULL
, if it was not requested.all_shortest_paths
a list is returned, each list element
contains a shortest path from from
to a vertex in to
. The
shortest paths to the same vertex are collected into consecutive elements of
the list.For mean_distance
a single number is returned.
distance_table
returns a named list with two entries: res
is
a numeric vector, the histogram of distances, unconnected
is a
numeric scalar, the number of pairs for which the first vertex is not
reachable from the second. The sum of the two entries is always $n(n-1)$
for directed graphs and $n(n-1)/2$ for undirected graphs.
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 argorithm
argument and
the weight
edge attribute of the graph. The implemented algorithms
are breadth-first search (unweighted
dijkstra
bellman-ford
"johnson"
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
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.
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")
Run the code above in your browser using DataLab