shortest.paths
calculates the length of all the
shortest paths from or to the vertices in the
network. get.shortest.paths
calculates one shortest path (the
path itself, and not just its length) from or to the given vertex.shortest.paths(graph, v=V(graph), to=V(graph),
mode = c("all", "out", "in"),
weights = NULL, algorithm = c("automatic", "unweighted",
"dijkstra", "bellman-ford",
"johnson"))
get.shortest.paths(graph, from, to=V(graph), mode = c("out", "all",
"in"), weights = NULL, output=c("vpath", "epath", "both"))
get.all.shortest.paths(graph, from, to = V(graph), mode = c("out",
"all", "in"), weights=NULL)
average.path.length(graph, directed=TRUE, unconnected=TRUE)
path.length.hist (graph, directed = TRUE)
shortest.paths
every vertex must be included here at most
once. (This is not required for get.sh
out
then the shortest paths from the vertex, if
in
then to it will be cNULL
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
shortest.paths
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 get.shortest.paths
the return value depends on the
output
parameter. If this is vcount(graph)
is returned.
List element i
contains the vertex ids on
the path from vertex from
to vertex 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 output
is
If output
is get.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 average.path.length
a single number is returned.
path.length.hist
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.
shortest.paths
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.)
get.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
. get.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.
get.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.
average.path.length
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.
path.length.hist
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 <- graph.ring(10)
shortest.paths(g)
get.shortest.paths(g, 5)
get.all.shortest.paths(g, 1, 6:8)
average.path.length(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(graph.empty(10), t(el[,1:2]), weight=el[,3])
shortest.paths(g2, mode="out")
Run the code above in your browser using DataLab