const_graphs/
lib.rs

1//! Blazingly-fast compile-time no-std graph crate.
2//! ```
3//! use const_graphs::Graph;
4//!
5//! fn bfs<const SIZE: usize>(
6//!   graph: &Graph<SIZE>,
7//!   start: usize,
8//!   end: usize,
9//! ) -> Option<Vec<usize>> {
10//!   let mut queue = std::collections::VecDeque::new();
11//!
12//!   let mut distance = [usize::MAX; SIZE];
13//!   let mut predecessor = [usize::MAX; SIZE];
14//!
15//!   distance[start] = 0;
16//!
17//!   queue.push_back(start);
18//!
19//!   while let Some(current) = queue.pop_front() {
20//!     for (neighbor, &has_edge) in graph
21//!                                      .get_edges(current)
22//!                                      .iter()
23//!                                      .enumerate() {
24//!       if has_edge && distance[neighbor] == usize::MAX {
25//!         distance[neighbor] = distance[current] + 1;
26//!         predecessor[neighbor] = current;
27//!         queue.push_back(neighbor);
28//!
29//!         if neighbor == end {
30//!           let mut path = vec![end];
31//!           let mut current = end;
32//!           while predecessor[current] != usize::MAX {
33//!             current = predecessor[current];
34//!             path.push(current);
35//!           }
36//!
37//!           path.reverse();
38//!
39//!           return Some(path);
40//!         }
41//!       }
42//!     }
43//!   }
44//!   
45//!   return None;
46//! }
47//!
48//! use const_graphs::WeightedGraph;
49//!
50//! fn bfs_weighted<const SIZE: usize>(
51//!   graph: &WeightedGraph<SIZE>,
52//!   start: usize,
53//!   end: usize,
54//! ) -> Option<Vec<usize>> {
55//!   let mut queue = std::collections::VecDeque::new();
56//!
57//!   let mut distance = [usize::MAX; SIZE];
58//!   let mut predecessor = [usize::MAX; SIZE];
59//!
60//!   distance[start] = 0;
61//!
62//!   queue.push_back(start);
63//!
64//!   while let Some(current) = queue.pop_front() {
65//!     for (neighbor, &edge) in graph
66//!                                      .get_edges(current)
67//!                                      .iter()
68//!                                      .enumerate() {
69//!       if edge.is_some() &&
70//!          distance[neighbor] == usize::MAX {
71//!         distance[neighbor] = distance[current] + 1;
72//!         predecessor[neighbor] = current;
73//!         queue.push_back(neighbor);
74//!
75//!         if neighbor == end {
76//!           let mut path = vec![end];
77//!           let mut current = end;
78//!           while predecessor[current] != usize::MAX {
79//!             current = predecessor[current];
80//!             path.push(current);
81//!           }
82//!
83//!           path.reverse();
84//!
85//!           return Some(path);
86//!         }
87//!       }
88//!     }
89//!   }
90//!
91//!   return None;
92//! }
93//! ```
94
95#![no_std]
96#![feature(const_mut_refs)]
97#![feature(const_fn_floating_point_arithmetic)]
98#![deny(missing_docs)]
99#![deny(rustdoc::broken_intra_doc_links)]
100#![deny(rustdoc::missing_crate_level_docs)]
101#![deny(rustdoc::invalid_codeblock_attributes)]
102#![deny(rustdoc::invalid_html_tags)]
103#![deny(rustdoc::invalid_rust_codeblocks)]
104#![deny(rustdoc::bare_urls)]
105
106mod graph;
107mod weighted_graph;
108
109pub use self::graph::Graph;
110pub use self::weighted_graph::WeightedGraph;
const_graphs/lib.rs

const_graphs/
lib.rs
