xgraph 3.0.0

//! [`GraphView`] adapter for the [`HeterogeneousGraph`].
//!
//! The heterogeneous graph groups its adjacency by neighbour — `(NodeId, Vec<(EdgeId, W)>)`
//! — while the view is a flat sequence of links, so the iterator below walks both levels.

use crate::core::filter::EdgeFiltered;
use crate::core::io::dot::{DotAttributes, DotStyle};
use crate::core::observer::MutableGraph;
use crate::core::view::{EdgeId, Generations, GraphView, Link, NodeId};
use crate::hgraph::h_edge::EdgeType;
use crate::hgraph::h_graph::HeterogeneousGraph;
use crate::hgraph::h_node::{HNode, NodeType};
use std::fmt::Debug;

/// Iterator over the node IDs of a [`HeterogeneousGraph`].
pub struct HGraphNodeIds<'a, W, N: NodeType> {
    inner: slab::Iter<'a, HNode<W, N>>,
    generations: &'a Generations,
}

impl<'a, W, N: NodeType> Iterator for HGraphNodeIds<'a, W, N> {
    type Item = NodeId;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner
            .next()
            .map(|(index, _)| NodeId::new(index as u32, self.generations.generation(index)))
    }
}

/// Iterator over the links leading out of one node of a [`HeterogeneousGraph`].
///
/// Flattens the graph's two-level adjacency into one link per incident edge.
pub struct HGraphLinks<'a, W> {
    neighbors: std::slice::Iter<'a, (NodeId, Vec<(EdgeId, W)>)>,
    current: Option<(NodeId, std::slice::Iter<'a, (EdgeId, W)>)>,
}

impl<'a, W: Copy> Iterator for HGraphLinks<'a, W> {
    type Item = Link<W>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some((target, edges)) = self.current.as_mut() {
                if let Some(&(edge, weight)) = edges.next() {
                    return Some(Link::new(*target, edge, weight));
                }
            }
            let (target, edges) = self.neighbors.next()?;
            self.current = Some((*target, edges.iter()));
        }
    }
}

impl<W, N, E> GraphView for HeterogeneousGraph<W, N, E>
where
    W: Copy + PartialEq + Debug,
    N: NodeType,
    E: EdgeType,
{
    type Weight = W;
    type NodeIds<'a>
        = HGraphNodeIds<'a, W, N>
    where
        Self: 'a;
    type Links<'a>
        = HGraphLinks<'a, W>
    where
        Self: 'a;

    fn is_directed(&self) -> bool {
        self.directed
    }

    fn node_count(&self) -> usize {
        self.nodes.len()
    }

    fn edge_count(&self) -> usize {
        self.edges.len()
    }

    fn contains_node(&self, node: NodeId) -> bool {
        self.node(node).is_some()
    }

    fn node_ids(&self) -> Self::NodeIds<'_> {
        HGraphNodeIds {
            inner: self.nodes.iter(),
            generations: self.node_generations(),
        }
    }

    fn links(&self, node: NodeId) -> Self::Links<'_> {
        HGraphLinks {
            neighbors: match self.node(node) {
                Some(node) => node.neighbors.iter(),
                None => [].iter(),
            },
            current: None,
        }
    }

    fn edge_endpoints(&self, edge: EdgeId) -> Option<(NodeId, NodeId)> {
        self.edge(edge).map(|e| (e.from, e.to))
    }
}

/// Lets the heterogeneous graph be wrapped in an [`Observed`](crate::core::Observed).
impl<W, N, E> MutableGraph for HeterogeneousGraph<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: NodeType,
    E: EdgeType + Default,
{
    type NodeData = N;
    type EdgeData = E;
    type EdgeWeight = W;
    type Error = crate::hgraph::h_graph::HGraphError;

    fn add_node(&mut self, data: N) -> NodeId {
        HeterogeneousGraph::add_node(self, data)
    }

    fn add_edge(
        &mut self,
        from: NodeId,
        to: NodeId,
        weight: W,
        data: E,
    ) -> Result<EdgeId, Self::Error> {
        HeterogeneousGraph::add_edge(self, from, to, weight, data)
    }

    fn remove_node(&mut self, node: NodeId) -> Result<bool, Self::Error> {
        HeterogeneousGraph::remove_node(self, node)
    }

    fn remove_edge_by_id(&mut self, edge: EdgeId) -> Result<(), Self::Error> {
        HeterogeneousGraph::remove_edge(self, edge)
    }
}

/// Labels nodes and edges with the strings their types render to.
impl<W, N, E> DotStyle for HeterogeneousGraph<W, N, E>
where
    W: Copy + PartialEq + Debug + std::fmt::Display,
    N: NodeType,
    E: EdgeType,
{
    fn node_attributes(&self, node: NodeId) -> DotAttributes {
        let mut attributes = match self.node(node) {
            Some(stored) => DotAttributes::new().label(stored.data.as_string()),
            None => DotAttributes::new().label(node.to_string()),
        };
        if let Some(stored) = self.node(node) {
            for (key, value) in &stored.attributes {
                attributes = attributes.set(key.clone(), value.clone());
            }
        }
        attributes
    }

    fn edge_attributes(&self, edge: EdgeId) -> DotAttributes {
        let Some(stored) = self.edge(edge) else {
            return DotAttributes::new();
        };
        let mut attributes =
            DotAttributes::new().label(format!("{} ({})", stored.data.as_string(), stored.weight));
        for (key, value) in &stored.attributes {
            attributes = attributes.set(key.clone(), value.clone());
        }
        attributes
    }
}

/// Convenience constructors for restricted views of a heterogeneous graph.
impl<W, N, E> HeterogeneousGraph<W, N, E>
where
    W: Copy + PartialEq + Debug,
    N: NodeType,
    E: EdgeType,
{
    /// The kind of an edge, as reported by its data's [`EdgeType::as_string`].
    pub fn edge_kind(&self, edge: EdgeId) -> Option<String> {
        self.edges.get(edge.index()).map(|e| e.data.as_string())
    }

    /// A view restricted to edges whose kind appears in `kinds`.
    ///
    /// Every algorithm in [`core`](crate::core) applies to the result unchanged, which is
    /// what removes the need for a `*_by_types` twin of each method.
    ///
    /// # Examples
    /// ```rust
    /// use xgraph::core::Traversal;
    /// use xgraph::hgraph::h_edge::EdgeType;
    /// use xgraph::hgraph::h_node::NodeType;
    /// use xgraph::hgraph::HeterogeneousGraph;
    ///
    /// #[derive(Clone, Eq, PartialEq, Hash, Debug)]
    /// struct City(String);
    /// impl NodeType for City {
    ///     fn as_string(&self) -> String { self.0.clone() }
    /// }
    /// #[derive(Clone, Debug, Default)]
    /// struct Route(String);
    /// impl EdgeType for Route {
    ///     fn as_string(&self) -> String { self.0.clone() }
    /// }
    ///
    /// let mut graph = HeterogeneousGraph::<f64, City, Route>::new(false);
    /// let a = graph.add_node(City("A".into()));
    /// let b = graph.add_node(City("B".into()));
    /// let c = graph.add_node(City("C".into()));
    /// graph.add_edge(a, b, 1.0, Route("rail".into())).unwrap();
    /// graph.add_edge(b, c, 1.0, Route("road".into())).unwrap();
    ///
    /// assert!(graph.has_path(a, c).unwrap());
    /// assert!(!graph.of_edge_kinds(&["rail"]).has_path(a, c).unwrap());
    /// ```
    pub fn of_edge_kinds<'a>(
        &'a self,
        kinds: &'a [&'a str],
    ) -> EdgeFiltered<&'a Self, impl Fn(EdgeId) -> bool + 'a> {
        EdgeFiltered::new(self, move |edge| {
            self.edge_kind(edge)
                .is_some_and(|kind| kinds.contains(&kind.as_str()))
        })
    }

    /// A view restricted to edges whose data equals one of `allowed`.
    ///
    /// An empty `allowed` slice admits every edge, matching how the `*_by_types` methods
    /// this replaces treated an empty filter.
    pub fn of_edge_data<'a>(
        &'a self,
        allowed: &'a [E],
    ) -> EdgeFiltered<&'a Self, impl Fn(EdgeId) -> bool + 'a>
    where
        E: PartialEq,
    {
        EdgeFiltered::new(self, move |edge| {
            self.edge(edge)
                .is_some_and(|e| allowed.is_empty() || allowed.contains(&e.data))
        })
    }

    /// A view restricted to the edges `predicate` accepts.
    ///
    /// The predicate sees the whole edge, so it can filter on weight, data or attributes,
    /// not only on the edge's kind.
    pub fn filter_edges<'a, F>(
        &'a self,
        predicate: F,
    ) -> EdgeFiltered<&'a Self, impl Fn(EdgeId) -> bool + 'a>
    where
        F: Fn(&crate::hgraph::h_edge::HEdge<W, E>) -> bool + 'a,
    {
        EdgeFiltered::new(self, move |edge| self.edge(edge).is_some_and(&predicate))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Clone, Eq, PartialEq, Hash, Debug)]
    struct City(String);
    impl NodeType for City {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[derive(Clone, Debug, Default)]
    struct Route(String);
    impl EdgeType for Route {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[test]
    fn test_links_flatten_the_two_level_adjacency() {
        let mut graph = HeterogeneousGraph::<f64, City, Route>::new(false);
        let a = graph.add_node(City("A".into()));
        let b = graph.add_node(City("B".into()));
        let c = graph.add_node(City("C".into()));

        let rail = graph.add_edge(a, b, 1.0, Route("rail".into())).unwrap();
        let road = graph.add_edge(a, b, 2.0, Route("road".into())).unwrap();
        let ferry = graph.add_edge(a, c, 3.0, Route("ferry".into())).unwrap();

        // Two parallel edges to `b` plus one to `c`, as three separate links.
        let mut seen: Vec<_> = graph
            .links(a)
            .map(|link| (link.target, link.edge))
            .collect();
        seen.sort_unstable();
        assert_eq!(seen, vec![(b, rail), (b, road), (c, ferry)]);
        assert_eq!(graph.degree(a), 3);
        assert_eq!(graph.node_id_vec(), vec![a, b, c]);
    }
}