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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
//! # Graaf
//!
//! Functions and types for working with graphs
//!
//! ## Examples
//!
//! ```
//! use {
//! graaf::{
//! algo::bfs::single_pair_shortest_path,
//! op::{
//! AddEdge,
//! Indegree,
//! },
//! },
//! std::collections::HashSet,
//! };
//!
//! let mut graph: [HashSet<usize>; 4] = [
//! HashSet::new(),
//! HashSet::new(),
//! HashSet::new(),
//! HashSet::new(),
//! ];
//!
//! // ╭───╮ ╭───╮
//! // │ 0 │ → │ 1 │
//! // ╰───╯ ╰───╯
//! // ↑ ↓
//! // ╭───╮ ╭───╮
//! // │ 3 │ │ 2 │
//! // ╰───╯ ╰───╯
//!
//! graph.add_edge(3, 0);
//! graph.add_edge(0, 1);
//! graph.add_edge(1, 2);
//!
//! assert_eq!(graph.indegree(0), 1);
//! assert_eq!(graph.indegree(1), 1);
//! assert_eq!(graph.indegree(2), 1);
//! assert_eq!(graph.indegree(3), 0);
//!
//! let path = single_pair_shortest_path(&graph, 3, 2);
//!
//! assert_eq!(path, Some(vec![3, 0, 1, 2]));
//! ```
// Clippy lint groups
#![deny(clippy::all, clippy::cargo, clippy::pedantic, clippy::nursery)]
// Clippy restriction lints
#![deny(
clippy::alloc_instead_of_core,
clippy::get_unwrap,
clippy::if_then_some_else_none,
clippy::impl_trait_in_params,
clippy::missing_assert_message,
clippy::multiple_inherent_impl,
clippy::panic_in_result_fn,
clippy::redundant_type_annotations,
clippy::rest_pat_in_fully_bound_structs,
clippy::self_named_module_files,
clippy::std_instead_of_alloc,
clippy::std_instead_of_core,
clippy::unnecessary_self_imports,
clippy::unneeded_field_pattern,
clippy::unseparated_literal_suffix,
clippy::unwrap_in_result
)]
// Rustc lint groups
#![deny(rust_2018_idioms)]
// Rustc lints
#![deny(
missing_copy_implementations,
missing_debug_implementations,
missing_docs,
trivial_casts,
trivial_numeric_casts,
unused_extern_crates,
unused_import_braces,
unused_results,
variant_size_differences
)]
// Rustdoc lints
#![deny(rustdoc::all)]
#![cfg_attr(feature = "adjacency_matrix", allow(incomplete_features))]
#![cfg_attr(feature = "adjacency_matrix", feature(generic_const_exprs))]
pub mod algo;
pub mod gen;
pub mod op;
pub mod prop;
pub mod repr;
#[cfg(test)]
mod tests {
#[test]
fn example() {
use {
crate::{
algo::bfs::single_pair_shortest_path,
op::{
AddEdge,
Indegree,
},
},
std::collections::HashSet,
};
let mut graph = [
HashSet::new(),
HashSet::new(),
HashSet::new(),
HashSet::new(),
];
// ╭───╮ ╭───╮
// │ 0 │ → │ 1 │
// ╰───╯ ╰───╯
// ↑ ↓
// ╭───╮ ╭───╮
// │ 3 │ │ 2 │
// ╰───╯ ╰───╯
graph.add_edge(3, 0);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
assert_eq!(graph.indegree(0), 1);
assert_eq!(graph.indegree(1), 1);
assert_eq!(graph.indegree(2), 1);
assert_eq!(graph.indegree(3), 0);
let path = single_pair_shortest_path(&graph, 3, 2);
assert_eq!(path, Some(vec![3, 0, 1, 2]));
}
}