fuchsia / third_party / github.com / petgraph / petgraph / refs/heads/upstream/next / . / crates / core / src / storage / sequential.rs

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<Id> { | |

/// 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<usize>; | |

/// 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<Id>; | |

} | |

pub trait SequentialGraphStorage { | |

type EdgeIdBijection<'graph>: GraphIdBijection<EdgeId> | |

where | |

Self: 'graph; | |

type NodeIdBijection<'graph>: GraphIdBijection<NodeId> | |

where | |

Self: 'graph; | |

fn node_id_bijection(&self) -> Self::NodeIdBijection<'_>; | |

fn edge_id_bijection(&self) -> Self::EdgeIdBijection<'_>; | |

} |