Module paths 

Shortest paths, distances, eccentricity, efficiency, random walks and related path algorithms (igraph_paths.h).

Everything here is a method of Graph (or a free function when no graph is involved). Distances are returned as a Matrix (rows are sources, columns are targets, unreachable pairs hold f64::INFINITY), paths as Vec<VertexId> / Vec<EdgeId>, and multi-output functions return small named structs such as ShortestPaths or Diameter.

Edge weights are always passed as Option<&[f64]> indexed by edge id: None means an unweighted graph (every edge has length one). Most functions ignore edges with a positive infinite weight.

Example

use igraph::prelude::*;

// A weighted directed "diamond" with a shortcut: 0 → 1 → 3 and 0 → 2 → 3.
let g = Graph::from_edges(&[(0, 1), (1, 3), (0, 2), (2, 3), (0, 3)], 4, true).unwrap();
let w = [1.0, 1.0, 2.0, 2.0, 5.0];

// Unweighted: the direct edge wins.
assert_eq!(g.get_shortest_path(0, 3, None, NeighborMode::Out).unwrap().vertices, vec![0, 3]);
// Weighted: go through vertex 1 (length 2 instead of 5).
let p = g.get_shortest_path(0, 3, Some(&w), NeighborMode::Out).unwrap();
assert_eq!(p.vertices, vec![0, 1, 3]);
assert_eq!(p.edges, vec![0, 1]);

let d = g.distances(0, .., Some(&w), NeighborMode::Out).unwrap();
assert_eq!(d.row(0), vec![0.0, 1.0, 2.0, 2.0]);

// The three shortest routes from 0 to 3, by increasing length.
let k = g.get_k_shortest_paths(0, 3, 3, Some(&w), NeighborMode::Out).unwrap();
let routes: Vec<_> = k.into_iter().map(|p| p.vertices).collect();
assert_eq!(routes, vec![vec![0, 1, 3], vec![0, 2, 3], vec![0, 3]]);

// Directed diameter (the longest shortest path) of the unweighted graph.
assert_eq!(g.diameter().unwrap(), 1.0);

Provided functionality

Topic	Methods
Distance matrices	distances, distances_cutoff, distances_dijkstra, distances_dijkstra_cutoff, distances_bellman_ford, distances_johnson, distances_floyd_warshall
One shortest path per target	get_shortest_paths, get_shortest_paths_dijkstra, get_shortest_paths_bellman_ford
A single shortest path	get_shortest_path, get_shortest_path_dijkstra, get_shortest_path_bellman_ford, get_shortest_path_astar
All shortest paths	get_all_shortest_paths, get_all_shortest_paths_dijkstra
Other path enumerations	get_k_shortest_paths, get_all_simple_paths
Widest (bottleneck) paths	get_widest_paths, get_widest_path, widest_path_widths_dijkstra, widest_path_widths_floyd_warshall
Global path statistics	diameter, diameter_with_path, pseudo_diameter, radius, average_path_length, average_path_length_details, path_length_hist
Vertex path statistics	eccentricity, graph_center
Efficiency	global_efficiency, local_efficiency, average_local_efficiency
Miscellaneous	random_walk, spanner, voronoi, vertex_path_from_edge_path, expand_path_to_pairs

Global statistics on a classic network, built with Graph::famous from the constructors module:

use igraph::prelude::*;

let karate = Graph::famous("Zachary").unwrap();
assert_eq!(karate.diameter().unwrap(), 5.0);
assert_eq!(karate.radius(None, NeighborMode::All).unwrap(), 3.0);
let apl = karate.average_path_length(None, false, true).unwrap();
assert!((apl - 2.408199643).abs() < 1e-9);
// Histogram of the 561 vertex pairs by distance (the 78 edges first).
let h = karate.path_length_hist(false).unwrap();
assert_eq!(h.counts[0], 78.0);
assert_eq!(h.counts.iter().sum::<f64>(), 561.0);

See also

• centrality: distance based centralities such as closeness, harmonic_centrality and betweenness (which counts shortest paths).
• visitor: breadth-first and depth-first traversals (bfs, dfs), the building blocks of unweighted shortest paths.
• components: reachability questions (is_connected, reachability) and bounded-distance neighborhoods (neighborhood).
• structural: girth (the shortest cycle) and minimum_spanning_tree.
• cycles: closed walks and special walks such as find_cycle and eulerian_path (whose edge sequences vertex_path_from_edge_path converts to vertices).
• flow: maxflow, the “capacity” counterpart of the widest paths offered here.
• community: community_voronoi, a community detection method built on voronoi.

Structs

AllShortestPaths

All the shortest paths from one source, as returned by Graph::get_all_shortest_paths.

AveragePathLength

Average shortest path length and number of disconnected pairs, see Graph::average_path_length_details.

Diameter

The diameter of a graph together with one longest geodesic, see Graph::diameter_with_path.

GraphPath

A single path, described both by the vertices it visits and by the edges it traverses.

PathLengthHistogram

Histogram of shortest path lengths, see Graph::path_length_hist.

PseudoDiameter

A pseudo-diameter and its endpoints, see Graph::pseudo_diameter.

ShortestPaths

Single-source shortest (or widest) paths towards a set of targets, as returned by Graph::get_shortest_paths and friends.

SimplePathsOptions

Length limits for Graph::get_all_simple_paths.

VoronoiPartition

A Voronoi partitioning, see Graph::voronoi.

Enums

FloydWarshallAlgorithm

Variant of the Floyd–Warshall algorithm used by Graph::distances_floyd_warshall (igraph_floyd_warshall_algorithm_t).

Functions

expand_path_to_pairs

Turns a path given as a vertex sequence into the list of its consecutive vertex pairs, e.g. [a, b, c] into [(a, b), (b, c)].