mapgraph/

lib.rs

//! A powerful library for directed adjacency list graphs.
//!
//! Graph is a complex data structure where relations between nodes may often be cyclic which
//! doesn't go well with the Rust's type system. A typical approach to this is to refer to nodes and
//! edges in a graph using node and edge indices (sometimes called IDs or keys) which are **mapped**
//! to the actual nodes, edges and their weights instead of using references or pointers. Since
//! we're **mapping** indices anyway why not make the **maps** we use generic and allow custom
//! indices?
//!
//! `mapgraph` provides the generic [`Graph`] type that is based on two maps: one for nodes and
//! one for edges. By using the rich system of traits from the [`map`] submodule the [`Graph`] type
//! may borrow some capabilities of the maps it's based on. For example, using a [`HashMap`] as a
//! node map for a [`Graph`] makes it accept external indices for nodes, effectively making the
//! graph an index for its own nodes.
//!
//! # Library features and examples
//!
//! ## Internal node indices
//!
//! Let's imagine Alice and Bob are friends and often call each other. Sometimes they order pizza by
//! phone from a place where Luigi works, but they aren't friends with Luigi, so he never calls them
//! by himself.
//!
//! Here's one way to make a graph to represent their relations:
//!
//! ```
//! use mapgraph::aliases::SlotMapGraph;
//!
//! # fn main() -> Result<(), mapgraph::error::AddEdgeError> {
//! // we create a graph that uses SlotMaps for both nodes and edges
//! let mut graph = SlotMapGraph::<&'static str, ()>::default();
//!
//! // next we create a node for each person
//! let alice_index = graph.add_node("Alice");
//! let bob_index = graph.add_node("Bob");
//! let luigi_index = graph.add_node("Luigi");
//!
//! // let's ensure that the indices return us the right node weights
//! assert_eq!(graph.node_weight(alice_index).copied(), Some("Alice"));
//! assert_eq!(graph.node_weight(bob_index).copied(), Some("Bob"));
//! assert_eq!(graph.node_weight(luigi_index).copied(), Some("Luigi"));
//!
//! // finally let's connect them
//! graph.add_edge((), alice_index, bob_index)?;
//! graph.add_edge((), bob_index, alice_index)?;
//! graph.add_edge((), bob_index, luigi_index)?;
//! graph.add_edge((), alice_index, luigi_index)?;
//! # Ok(())
//! # }
//! ```
//!
//! Here [`SlotMapGraph`] is just an alias for [`Graph`] that uses [`SlotMap`]s for both nodes and
//! edges. We don't use edge weights, so we pass the unit type as the first parameter to
//! [`Graph::add_edge`].
//!
//! While this may not seem like much just yet, using [`SlotMap`]s gives [`Graph`] important
//! properties: removing nodes won't cause unrelated indices to be invalidated and key versioning
//! prevents older indices from pointing to newly added nodes that happen to be stored in place of
//! an older node.
//!
//! ## External node indices
//!
//! Now let's imagine we are telephone company employees who want to trace phone numbers to people
//! and their relations for data science purposes. The obvious way to do this would be to create a
//! separate index that maps phone numbers to graph indices, but that presents a challenge: the
//! index should be synchronised to the graph. Adding or removing nodes should update the index as
//! well as the graph itself. What if we used the phone numbers as node indices directly?
//!
//! Here's how we can do this:
//!
//! ```
//! use mapgraph::aliases::HashSlotMapGraph;
//!
//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
//! // we create a graph that uses a HashMap for nodes and a SlotMap for edges
//! let mut graph = HashSlotMapGraph::<&'static str, (), _>::default();
//!
//! // define some constants for simplicity
//! const ALICE_NUMBER: &'static str = "6661234";
//! const BOB_NUMBER: &'static str = "5553535";
//! const LUIGI_NUMBER: &'static str = "1001112";
//!
//! // next we create a node for each person
//! graph.try_add_node_at_index(ALICE_NUMBER, "Alice")?;
//! graph.try_add_node_at_index(BOB_NUMBER, "Bob")?;
//! graph.try_add_node_at_index(LUIGI_NUMBER, "Luigi")?;
//!
//! // let's ensure that the indices return us the right node weights
//! assert_eq!(graph.node_weight(ALICE_NUMBER).copied(), Some("Alice"));
//! assert_eq!(graph.node_weight(BOB_NUMBER).copied(), Some("Bob"));
//! assert_eq!(graph.node_weight(LUIGI_NUMBER).copied(), Some("Luigi"));
//!
//! // finally let's connect them
//! graph.add_edge((), ALICE_NUMBER, BOB_NUMBER)?;
//! graph.add_edge((), BOB_NUMBER, ALICE_NUMBER)?;
//! graph.add_edge((), BOB_NUMBER, LUIGI_NUMBER)?;
//! graph.add_edge((), ALICE_NUMBER, LUIGI_NUMBER)?;
//! # Ok(())
//! # }
//! ```
//!
//! We use a [`HashSlotMapGraph`] which is just an alias to a [`Graph`] like [`SlotMapGraph`] from
//! the previous example. The interface for adding nodes to a [`HashSlotMapGraph`] is, however,
//! different. The [`Graph::try_add_node_at_index`] method that accepts an external node index is
//! used rather than [`Graph::add_node`] which provides an index as its return value since
//! [`HashMap`] accepts keys provided externally unlike [`SlotMap`] which produces its keys
//! internally. The way your map treats indices is encoded by implementing either [`ExtKeyMap`] or
//! [`IntKeyMap`] trait. See documentation for the [`map`] module for more info on map traits and
//! the capabilities they expose.
//!
//! ## Ordered node indices
//!
//! For the last example let's pretend we also want to find people with particular area codes in
//! their phone numbers:
//!
//! ```
//! use mapgraph::aliases::BTreeSlotMapGraph;
//!
//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
//! // we create a graph that uses a BTreeMap for nodes and a SlotMap for edges
//! let mut graph = BTreeSlotMapGraph::<&'static str, (), _>::default();
//!
//! // define some constants for simplicity
//! const ALICE_NUMBER: &'static str = "6661234";
//! const BOB_NUMBER: &'static str = "5553535";
//! const LUIGI_NUMBER: &'static str = "1001112";
//!
//! // next we create a node for each person
//! graph.try_add_node_at_index(ALICE_NUMBER, "Alice")?;
//! graph.try_add_node_at_index(BOB_NUMBER, "Bob")?;
//! graph.try_add_node_at_index(LUIGI_NUMBER, "Luigi").unwrap();
//!
//! // we skip adding edges this time and just do a range query
//! let phones_and_names: Vec<_> = graph.nodes_range("5000000"..="7000000").collect();
//!
//! // check that the results match our expectations
//! assert_eq!(
//!     &phones_and_names,
//!     &[(BOB_NUMBER, &"Bob"), (ALICE_NUMBER, &"Alice")]
//! );
//! # Ok(())
//! # }
//! ```
//!
//! Here we use the capabilities of a [`BTreeMap`] that are lent to the graph using the
//! [`OrderedKeyMap`] trait.
//!
//! # More advanced features
//!
//! ## Frozen graphs
//!
//! This is a nice feature lent from the [`petgraph`] crate. [`FrozenGraph`] is a [`Graph`] with an
//! immutable structure. Having a mutable reference to a [`FrozenGraph`] means you can mutate
//! weights, but not add or remove nodes and edges. [`Graph`] and [`FrozenGraph`] can be freely
//! converted between each other, graph also implements [`Deref<Target=FrozenGraph>`]. See docs for
//! [`FrozenGraph`] for more info.
//!
//! ## Parallel iteration using [`rayon`]
//!
//! When the `rayon` crate feature is enabled, [`Graph`] exposes methods for parallel iteration of
//! nodes and edges in case the underlying maps expose this functionality through the [`ParIterMap`]
//! trait.
//!
//! ```
//! use mapgraph::aliases::HashSlotMapGraph;
//! use rayon::iter::ParallelIterator;
//!
//! let mut graph = HashSlotMapGraph::<i32, i32, &'static str>::default();
//!
//! // add nodes and edges...
//!
//! // add 1 to each node weight in parallel
//! graph
//!     .par_iter_node_weights_mut()
//!     .for_each(|(_, weight)| *weight += 1);
//! ```
//!
//! In case you need to mutably iterate nodes and edges in parallel or to walk over edges while
//! doing parallel iteration on nodes (or vice versa), a mutable reference to a [`Graph`] may be
//! split into a reference to [`Nodes`] and a reference to [`Edges`]:
//!
//! ```
//! use mapgraph::{aliases::HashSlotMapGraph, graph::iter::EdgesWalker};
//! use rayon::iter::ParallelIterator;
//!
//! let mut graph = HashSlotMapGraph::<i32, i32, &'static str>::default();
//!
//! // add nodes and edges...
//!
//! // split a reference to a graph
//! let (nodes, edges) = graph.as_nodes_mut_and_edges();
//!
//! nodes.par_iter_mut().for_each(|(_, node)| {
//!     // let's sum all the weight of outgoing edges of that node
//!     let mut outputs_walker = node.walk_outputs();
//!     let mut sum = 0;
//!     while let Some((_ei, edge)) = outputs_walker.walk_edges_next(edges) {
//!         sum += *edge.weight();
//!     }
//!
//!     // add that sum to the node's weight
//!     *node.weight_mut() += sum;
//! });
//! ```
//!
//! # Crate features
//!
//! * `std` - enables support for the [`HashMap`] type, provides implementations of
//!   [`std::error::Error`] on error types, enables the `std` feature on the [`slotmap`] crate if the
//!   `slotmap` feature is enabled. Requires the `alloc` feature.
//! * `alloc` - enables support for the [`alloc`] crate, in particular [`BTreeMap`] and [`BTreeSet`]
//!   types.
//! * `slotmap` - enables integration with the [`slotmap`] crate.
//! * `indexmap` - enables integration with the [`indexmap`] crate.
//! * `algorithms` - enables the [`algo`] module which provides various algorithms to be run on
//!   graphs.
//! * `serde` - enables serialization/deserialization using [`serde`]. Disabled by default.
//! * `rayon` - enables parallel iteration support using [`rayon`]. Disabled by default.
//!
//! [`petgraph`]: https://github.com/petgraph/petgraph
//! [`HashMap`]: std::collections::HashMap
//! [`BTreeMap`]: alloc::collections::BTreeMap
//! [`BTreeSet`]: alloc::collections::BTreeSet
//! [`SlotMap`]: slotmap::SlotMap
//! [`IndexMap`]: indexmap::IndexMap
//! [`SlotMapGraph`]: aliases::SlotMapGraph
//! [`HashSlotMapGraph`]: aliases::HashSlotMapGraph
//! [`Deref<Target=FrozenGraph>`]: std::ops::Deref
//! [`Nodes`]: graph::Nodes
//! [`Edges`]: graph::Edges

#![no_std]
#![cfg_attr(docsrs, feature(doc_auto_cfg))]
#![deny(missing_docs)]
#![deny(missing_debug_implementations)]
#![deny(rust_2018_idioms)]
#![deny(unreachable_pub)]
#![deny(unsafe_code)]
#![deny(clippy::unwrap_used)]
#![deny(clippy::iter_without_into_iter)]
#![warn(clippy::missing_errors_doc)]
#![warn(clippy::missing_panics_doc)]

#[cfg(feature = "alloc")]
extern crate alloc;
#[cfg(feature = "std")]
extern crate std;

#[cfg(feature = "algorithms")]
pub mod algo;
#[cfg(any(feature = "alloc", feature = "slotmap"))]
pub mod aliases;
pub mod error;
pub mod graph;
pub mod map;
mod util;

pub use graph::{FrozenGraph, Graph};
#[cfg(feature = "rayon")]
pub use map::ParIterMap;
pub use map::{ExtKeyMap, IntKeyMap, KeySet, Map, MapWithCapacity, OrderedKeyMap};