1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//! Street-network graph algorithms for OpenStreetMap-style networks.
//!
//! `osmnxr-core` is the compute core of the R package
//! [osmnxr](https://strategicprojects.github.io/osmnxr/) (OSMnx for R). It
//! holds the graph math and nothing else: no I/O, no geometry types, no
//! coordinate reference systems. A caller hands it edge lists of 0-based node
//! indices with weights, and gets back node paths, edge indices, distances
//! and scores. The crate has no dependencies.
//!
//! # Modules
//!
//! - [`graph`]: a compressed-sparse-row (CSR) directed graph built from
//! parallel `from`/`to`/`weight` vectors.
//! - [`routing`]: Dijkstra, shortest paths that report the edges traversed
//! (parallel edges included), Yen's k shortest paths, distance matrices, a
//! travelling-salesman heuristic, the Pareto front of bicriteria paths
//! (Martins' label-setting, exact constrained shortest paths) and the LARAC
//! Lagrangian relaxation for large graphs.
//! - [`centrality`]: betweenness (Brandes) and closeness.
//! - [`metrics`]: basic network statistics, compass bearings and the
//! orientation entropy of a street grid.
//! - [`simplify`]: topology simplification (chains of degree-2 nodes between
//! endpoints) and connected components.
//! - [`spatial`]: grid-indexed snapping of points to the nearest polyline.
//!
//! # Conventions
//!
//! Nodes are `0 .. n_nodes`; edges are directed, so a two-way street is two
//! edges. Weights must be nonnegative and finite. Functions that return edges
//! give indices into the caller's input order, so attributes and geometry can
//! be recovered exactly. Unreachable targets are `f64::INFINITY` distances,
//! empty paths or `None`, never a made-up value.
//!
//! # Example
//!
//! ```
//! use osmnxr_core::graph::Graph;
//! use osmnxr_core::routing::{dijkstra, shortest_path_route};
//!
//! // a square 0 -> 1 -> 2 -> 3 -> 0 with a diagonal 0 -> 2
//! let from = [0, 1, 2, 3, 0];
//! let to = [1, 2, 3, 0, 2];
//! let weight = [1.0, 1.0, 1.0, 1.0, 1.5];
//! let g = Graph::from_edges(&from, &to, &weight, 4);
//!
//! let dist = dijkstra(&g, 0);
//! assert_eq!(dist, vec![0.0, 1.0, 1.5, 2.5]);
//!
//! let (path, _slots, cost) = shortest_path_route(&g, 0, 3).unwrap();
//! assert_eq!(path, vec![0, 2, 3]);
//! assert_eq!(cost, 2.5);
//! ```
pub use Graph;