blob: e64dd042822cc03822e0bac09c419ade87923a1a [file] [log] [blame]
 use crate::{edge::EdgeId, node::NodeId}; /// Index mapper for a graph. /// /// The index mapper is a type, that maps a specific value (`From`), typically a [`LinearGraphId`], /// into a different value ([`usize`]). /// /// Mapping is bijective, meaning that `From -> usize` and `usize -> From` are both possible, and /// that every `From` value has a unique `usize` value in the range specified by `0..Self::MAX`. /// Meaning it is not possible to have a mapping of e.g. three nodes, like: `A`, `B`, `C` to `1`, /// `3`, `5` with `MAX = 5`, because `2` and `4` are not mapped to anything. /// /// How this conversion is done is up to the implementation, but should be consistent, i.e. the same /// input value should always map to the same output value. /// Index lookup should also be (if possible) `O(1)` for `Id -> usize`, but not necessarily for /// `usize -> Id`. pub trait GraphIdBijection { /// The maximum value that can be mapped to. /// /// This **must** be equal to the number of nodes in the graph. /// /// # Example /// /// ``` /// use petgraph_core::id::{IndexMapper, LinearGraphId}; /// use petgraph_dino::{DiDinoGraph, NodeId}; /// /// let mut graph = DiDinoGraph::new(); /// /// let a = *graph.insert_node("A").id(); /// let b = *graph.insert_node("B").id(); /// # let ab = graph.insert_edge("A → B", &a, &b); /// /// let mapper = NodeId::index_mapper(graph.storage()); /// /// assert_eq!(mapper.max(), 2); /// ``` fn max(&self) -> usize; /// Map a value from `From` to [`usize`]. /// /// This **must** be pure and **must** return a valid value for any `Id` value in the graph it /// is bound to. /// /// # Example /// /// ``` /// use petgraph_core::id::{IndexMapper, LinearGraphId}; /// use petgraph_dino::{DiDinoGraph, NodeId}; /// /// let mut graph = DiDinoGraph::new(); /// /// let a = *graph.insert_node("A").id(); /// let b = *graph.insert_node("B").id(); /// # let ab = graph.insert_edge("A → B", &a, &b); /// /// let mut mapper = NodeId::index_mapper(graph.storage()); /// /// // The mapping is highly dependent on the implementation, but should be consistent. /// // The order for which node maps to which value is not guaranteed. /// assert_ne!(mapper.get(&a), mapper.get(&b)); /// ``` fn get(&self, from: Id) -> Option; /// Lookup a value from `To` to [`usize`]. /// /// This **must** be pure and **must** return a valid value for any `Id` value in the graph /// it is bound to. /// /// # Example /// /// ``` /// use petgraph_core::id::{IndexMapper, LinearGraphId}; /// use petgraph_dino::{DiDinoGraph, NodeId}; /// /// let mut graph = DiDinoGraph::new(); /// /// let a = *graph.insert_node("A").id(); /// let b = *graph.insert_node("B").id(); /// # let ab = graph.insert_edge("A → B", &a, &b); /// /// let mut mapper = NodeId::index_mapper(graph.storage()); /// /// // The mapping is highly dependent on the implementation, but should be consistent. /// // The order for which node maps to which value is not guaranteed. /// assert_ne!(mapper.index(&a), mapper.index(&b)); /// ``` /// /// # Panics /// /// Panics if the provided id is not valid, meaning it is not part of the graph (e.g. id from /// another instance) fn index(&self, from: Id) -> usize { self.get(from).expect("invalid id provided") } /// Reverse lookup a value from `To` to `From`. /// /// This **must** be pure, but **may** return `None` if a reverse mapping does not exist (for /// example `usize` is too large and therefore does not exist). /// /// # Example /// /// ``` /// use numi::borrow::Moo; /// use petgraph_dino::{DiDinoGraph, NodeId}; /// /// let mut graph = DiDinoGraph::new(); /// /// let a = *graph.insert_node("A").id(); /// let b = *graph.insert_node("B").id(); /// # let ab = graph.insert_edge("A → B", a, b); /// /// let mut mapper = NodeId::index_mapper(graph.storage()); /// /// let mapped = mapper.index(&a); /// assert_eq!(mapper.reverse(mapped), Some(Moo::Borrowed(&a))); /// ``` fn reverse(&self, to: usize) -> Option; } pub trait SequentialGraphStorage { type EdgeIdBijection<'graph>: GraphIdBijection where Self: 'graph; type NodeIdBijection<'graph>: GraphIdBijection where Self: 'graph; fn node_id_bijection(&self) -> Self::NodeIdBijection<'_>; fn edge_id_bijection(&self) -> Self::EdgeIdBijection<'_>; }