xgraph 3.0.0

//! The abstraction every algorithm in this library is written against.

/// Identifier of a node within one graph.
///
/// Carries a generation alongside the storage index. Node slots are reused after a
/// removal, so an index on its own is ambiguous: an ID held across a `remove_node` would
/// silently start referring to whatever node took the slot. The generation is bumped on
/// every removal, so a stale ID fails to resolve instead.
///
/// The type is distinct from [`EdgeId`], which is what stops one being passed where the
/// other is expected — a mistake that had gone unnoticed in this crate's own graph
/// conversion code.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct NodeId {
    // Ordered index-first, so sorting node IDs orders them by storage position.
    index: u32,
    generation: u32,
}

impl NodeId {
    /// Builds an ID for a specific slot and generation.
    ///
    /// Callers outside a graph implementation normally receive IDs rather than build them.
    pub const fn new(index: u32, generation: u32) -> Self {
        Self { index, generation }
    }

    /// Builds an ID for a slot that has never been reused.
    ///
    /// Useful when addressing a freshly built graph — one loaded from a file, say — by
    /// position. An ID built this way will not resolve against a slot that has since been
    /// removed and refilled, which is the point.
    pub const fn from_index(index: usize) -> Self {
        Self::new(index as u32, 0)
    }

    /// The storage slot this ID refers to.
    pub const fn index(self) -> usize {
        self.index as usize
    }

    /// How many times this slot had been reused when the ID was issued.
    pub const fn generation(self) -> u32 {
        self.generation
    }
}

impl std::fmt::Debug for NodeId {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        // Generation 0 is the common case and adding it would only clutter test output.
        if self.generation == 0 {
            write!(f, "n{}", self.index)
        } else {
            write!(f, "n{}v{}", self.index, self.generation)
        }
    }
}

impl std::fmt::Display for NodeId {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.index)
    }
}

/// Identifier of a single edge within one graph.
///
/// Node pairs do not identify edges: both graph types admit parallel edges, and telling
/// them apart is what makes bridge detection, cycle detection and per-edge attributes
/// correct on a multigraph. Like [`NodeId`], it carries a generation so that an ID held
/// across a removal fails to resolve rather than addressing a different edge.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct EdgeId {
    index: u32,
    generation: u32,
}

impl EdgeId {
    /// Builds an ID for a specific slot and generation.
    pub const fn new(index: u32, generation: u32) -> Self {
        Self { index, generation }
    }

    /// Builds an ID for a slot that has never been reused.
    pub const fn from_index(index: usize) -> Self {
        Self::new(index as u32, 0)
    }

    /// The storage slot this ID refers to.
    pub const fn index(self) -> usize {
        self.index as usize
    }

    /// How many times this slot had been reused when the ID was issued.
    pub const fn generation(self) -> u32 {
        self.generation
    }
}

impl std::fmt::Debug for EdgeId {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.generation == 0 {
            write!(f, "e{}", self.index)
        } else {
            write!(f, "e{}v{}", self.index, self.generation)
        }
    }
}

impl std::fmt::Display for EdgeId {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.index)
    }
}

/// Tracks how many times each storage slot has been reused.
///
/// A graph keeps one of these per store and consults it on every lookup, which is what
/// turns a stale identifier from a silent mis-read into a `None`.
#[derive(Debug, Clone, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Generations {
    counts: Vec<u32>,
}

impl Generations {
    /// Creates an empty tracker.
    pub fn new() -> Self {
        Self::default()
    }

    /// Records that `index` has just been filled, and reports its current generation.
    pub fn issue(&mut self, index: usize) -> u32 {
        if index >= self.counts.len() {
            self.counts.resize(index + 1, 0);
        }
        self.counts[index]
    }

    /// Records that `index` has been vacated, so identifiers naming it stop resolving.
    pub fn retire(&mut self, index: usize) {
        if let Some(count) = self.counts.get_mut(index) {
            *count = count.wrapping_add(1);
        }
    }

    /// Whether an identifier still names the occupant of its slot.
    pub fn is_current(&self, index: usize, generation: u32) -> bool {
        self.counts.get(index) == Some(&generation)
    }

    /// The current generation of a slot.
    pub fn generation(&self, index: usize) -> u32 {
        self.counts.get(index).copied().unwrap_or(0)
    }
}

/// One traversable connection leading out of a node.
///
/// Named `Link` rather than `Arc` so that it never has to be disambiguated from
/// [`std::sync::Arc`] at a use site.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Link<W> {
    /// The node on the far end of the connection.
    pub target: NodeId,
    /// The edge this connection traverses.
    pub edge: EdgeId,
    /// The weight of that edge.
    pub weight: W,
}

impl<W> Link<W> {
    /// Creates a link to `target` across `edge`, carrying `weight`.
    pub fn new(target: NodeId, edge: EdgeId, weight: W) -> Self {
        Self {
            target,
            edge,
            weight,
        }
    }
}

/// A read-only view of a graph's structure.
///
/// This is the query half of the command/query split: it exposes everything an algorithm
/// needs to traverse a graph and nothing that could mutate it, so `&impl GraphView` is a
/// compiler-checked promise that an algorithm leaves the graph alone.
///
/// Implementations are cheap to compose. [`EdgeFiltered`](crate::core::EdgeFiltered) and
/// [`NodeFiltered`](crate::core::NodeFiltered) wrap any view in another view, which is how
/// "run this algorithm over only these edges" is expressed without duplicating the
/// algorithm.
///
/// # Examples
/// ```rust
/// # #[cfg(feature = "graph")] {
/// use xgraph::core::GraphView;
/// use xgraph::graph::Graph;
///
/// let mut graph = Graph::<u32, &str, &str>::new(false);
/// let a = graph.add_node("A");
/// let b = graph.add_node("B");
/// graph.add_edge(a, b, 3, "rail").unwrap();
///
/// assert_eq!(graph.node_count(), 2);
/// assert_eq!(graph.links(a).next().unwrap().target, b);
/// # }
/// ```
pub trait GraphView {
    /// The type edge weights are expressed in.
    type Weight: Copy;

    /// The iterator [`node_ids`](GraphView::node_ids) returns.
    type NodeIds<'a>: Iterator<Item = NodeId>
    where
        Self: 'a;

    /// The iterator [`links`](GraphView::links) returns.
    type Links<'a>: Iterator<Item = Link<Self::Weight>>
    where
        Self: 'a;

    /// Whether edges are one-way.
    fn is_directed(&self) -> bool;

    /// The number of nodes in the graph.
    fn node_count(&self) -> usize;

    /// The number of edges in the graph, counting parallel edges separately.
    fn edge_count(&self) -> usize;

    /// Whether a node with this ID exists.
    fn contains_node(&self, node: NodeId) -> bool;

    /// Every node ID in the graph, in ascending order.
    ///
    /// IDs are not necessarily contiguous: removing a node leaves a gap until the slot is
    /// reused, so algorithms must iterate this rather than a `0..node_count()` range.
    fn node_ids(&self) -> Self::NodeIds<'_>;

    /// Every connection leading out of `node`, one per incident edge.
    ///
    /// A node connected to a neighbour by three parallel edges yields three links. For a
    /// node that does not exist the iterator is empty.
    fn links(&self, node: NodeId) -> Self::Links<'_>;

    /// The endpoints of an edge, as stored.
    ///
    /// For an undirected graph the pair is normalized and carries no direction.
    fn edge_endpoints(&self, edge: EdgeId) -> Option<(NodeId, NodeId)>;

    /// Collects the node IDs into a vector.
    ///
    /// Useful when a traversal needs to mutate nothing but must outlive the borrow that
    /// [`node_ids`](GraphView::node_ids) holds.
    fn node_id_vec(&self) -> Vec<NodeId> {
        self.node_ids().collect()
    }

    /// The number of edges incident to a node, counting parallel edges separately.
    ///
    /// Returns 0 for a node that does not exist.
    fn degree(&self, node: NodeId) -> usize {
        self.links(node).count()
    }
}

impl<G: GraphView + ?Sized> GraphView for &G {
    type Weight = G::Weight;
    type NodeIds<'a>
        = G::NodeIds<'a>
    where
        Self: 'a;
    type Links<'a>
        = G::Links<'a>
    where
        Self: 'a;

    fn is_directed(&self) -> bool {
        (**self).is_directed()
    }
    fn node_count(&self) -> usize {
        (**self).node_count()
    }
    fn edge_count(&self) -> usize {
        (**self).edge_count()
    }
    fn contains_node(&self, node: NodeId) -> bool {
        (**self).contains_node(node)
    }
    fn node_ids(&self) -> Self::NodeIds<'_> {
        (**self).node_ids()
    }
    fn links(&self, node: NodeId) -> Self::Links<'_> {
        (**self).links(node)
    }
    fn edge_endpoints(&self, edge: EdgeId) -> Option<(NodeId, NodeId)> {
        (**self).edge_endpoints(edge)
    }
}