Paths and traversal
Graphs.jl provides several traversal and shortest-path algorithms, along with various utility functions. Where appropriate, edge distances may be passed in as a matrix of real number values.
Edge distances for most traversals may be passed in as a sparse or dense matrix of values, indexed by
[src,dst] vertices. That is,
distmx[2,4] = 2.5 assigns the distance
2.5 to the (directed) edge connecting vertex 2 and vertex 4. Note that for undirected graphs
distmx[4,2] also has to be set.
Default edge distances may be passed in via the
Any graph traversal will traverse an edge only if it is present in the graph. When a distance matrix is given:
- distance values for undefined edges will be ignored;
- any unassigned values (in sparse distance matrices) for edges that are present in the graph will be assumed to take the default value of 1.0;
- any zero values (in sparse/dense distance matrices) for edges that are present in the graph will instead have an implicit edge cost of 1.0.
Graph traversal refers to a process that traverses vertices of a graph following certain order (starting from user-input sources). This package implements three traversal schemes:
The package also includes uniform random walks and self avoiding walks with the following functions:
The following properties always hold for shortest path algorithms implemented here:
- The distance from a vertex to itself is always
- The distance between two vertices with no connecting edge is always
yen_k_shortest_paths functions return path states (subtypes of
Graphs.AbstractPathState) that contain various information about the graph learned during traversal.
The corresponding state types (with the exception of
YenState) have the following common fields:
state.distsholds a vector with the distances computed, indexed by source vertex.
state.parentsholds a vector of parents of each vertex on the shortest paths (the parent of a source vertex is always
In addition, with the appropriate optional arguments,
dijkstra_shortest_paths will return information on all possible shortest paths available from the source.