Shortest (directed or undirected) paths between vertices
shortest.paths calculates the length of all the
shortest paths from or to the vertices in the
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), mode = "all") get.shortest.paths(graph, from, to=V(graph), mode = "all") get.all.shortest.paths(graph, from, to = V(graph), mode = "all") average.path.length(graph, directed=TRUE, unconnected=TRUE)
- The graph to work on.
- Numeric vector, the vertices from or to which the shortest paths will be calculated.
- Character constant, gives whether the shortest paths to or
from the given vertices should be calculated for directed graphs. If
outthen the shortest paths from the vertex, if
inthen to it will be c
- Numeric constant, the vertex from or to the shortest paths will be calculated. Note that right now this is not a vector of vertex ids, but only a single vertex.
- Numeric vector, only the shortest paths to these vertices will be calculated. Defaults to all vertices.
- Whether to consider directed paths in directed graphs, this argument is ignored for undirected graphs.
- What to do if the graph is unconnected (not strongly connected if directed paths are considered). If TRUE only the lengths of the existing paths are considered and averaged; if FALSE the length of the missing paths are counted having length
The shortest paths (also called geodesics) are calculated by using breath-first search in the graph. Right now edge weights are not used, ie. every edge weight is one.
shortest.paths is able to calculate the path length
from or to many vertices at the same time, but
get.shortest.paths works from one source only. This might
change in the future.
Also note that
get.shortest.paths gives only one shortest path,
however more than one might exists between two vertices.
get.all.shortest.paths calculates all shortest paths from a
vertex to other vertices given in the
shortest.pathsa numeric matrix with
length(v)rows. The shortest path length from a vertex to itself is always zero.
get.shortest.pathsa list of length
vcount(graph). List element
icontains the vertex ids on the path from vertex
i(or the other way for directed graphs depending on the
modeargument). The vector also contains
ias the first and last elements. If
fromis the same as
ithen 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.
get.all.shortest.pathsa list is returned, each list element contains a shortest path from
fromto a vertex in
to. The shortest paths to the same vertex are collected into consecutive elements of the list. For
average.path.lengtha single number is returned.
West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.
g <- graph.ring(10) shortest.paths(g) get.shortest.paths(g, 5) get.all.shortest.paths(g, 0, 5:7) average.path.length(g)