xgraph 3.0.0

//! [`GraphView`] adapter for the homogeneous [`Graph`].
//!
//! The adapter lives with the concrete type and depends on `core`, never the other way
//! round, so the abstraction stays free of any knowledge of slab storage.

use crate::core::io::dot::{DotAttributes, DotStyle};
use crate::core::observer::MutableGraph;
use crate::core::view::{EdgeId, Generations, GraphView, Link, NodeId};
use crate::graph::edge::Edge;
use crate::graph::graph::Graph;
use crate::graph::node::Node;
use std::fmt::Debug;
use std::hash::Hash;

/// Iterator over the node IDs of a [`Graph`].
///
/// Slab slots are addressed by position, so each is paired with its current generation to
/// form the identifier callers see.
pub struct GraphNodeIds<'a, W, N> {
    inner: slab::Iter<'a, Node<W, N>>,
    generations: &'a Generations,
}

impl<'a, W, N> Iterator for GraphNodeIds<'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 [`Graph`].
pub struct GraphLinks<'a, W> {
    inner: std::slice::Iter<'a, (NodeId, EdgeId, W)>,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        self.inner
            .next()
            .map(|&(target, edge, weight)| Link::new(target, edge, weight))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<W, N, E> GraphView for Graph<W, N, E>
where
    W: Copy + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Debug,
{
    type Weight = W;
    type NodeIds<'a>
        = GraphNodeIds<'a, W, N>
    where
        Self: 'a;
    type Links<'a>
        = GraphLinks<'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<'_> {
        GraphNodeIds {
            inner: self.nodes.iter(),
            generations: self.node_generations(),
        }
    }

    fn links(&self, node: NodeId) -> Self::Links<'_> {
        GraphLinks {
            inner: match self.node(node) {
                Some(node) => node.neighbors.iter(),
                // An unknown node has no links rather than being an error, which keeps the
                // trait total and lets algorithms decide for themselves whether a missing
                // node is worth reporting.
                None => [].iter(),
            },
        }
    }

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

/// Lets the homogeneous graph be wrapped in an [`Observed`](crate::core::Observed).
impl<W, N, E> MutableGraph for Graph<W, N, E>
where
    W: Copy + Default + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    type NodeData = N;
    type EdgeData = E;
    type EdgeWeight = W;
    type Error = crate::graph::graph::GraphError;

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

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

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

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

/// Labels nodes and edges with the data they carry.
///
/// Weights become edge labels, and node data its `Display` form, so the drawing shows what
/// the graph actually holds rather than bare identifiers.
impl<W, N, E> DotStyle for Graph<W, N, E>
where
    W: Copy + PartialEq + std::fmt::Display,
    N: Clone + Eq + Hash + Debug + std::fmt::Display,
    E: Clone + Debug + std::fmt::Display,
{
    fn node_attributes(&self, node: NodeId) -> DotAttributes {
        let mut attributes = match self.node(node) {
            Some(stored) => DotAttributes::new().label(stored.data.to_string()),
            None => DotAttributes::new().label(node.to_string()),
        };
        // Node attributes set on the graph are carried through, so anything Graphviz
        // understands — colour, shape — can be set on the graph and appear in the drawing.
        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 data = stored.data.to_string();
        let label = if data.is_empty() {
            stored.weight.to_string()
        } else {
            format!("{} ({})", data, stored.weight)
        };
        let mut attributes = DotAttributes::new().label(label);
        for (key, value) in &stored.attributes {
            attributes = attributes.set(key.clone(), value.clone());
        }
        attributes
    }
}

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

    #[test]
    fn test_view_reports_parallel_edges_separately() {
        let mut graph = Graph::<u32, &str, &str>::new(false);
        let a = graph.add_node("A");
        let b = graph.add_node("B");
        let rail = graph.add_edge(a, b, 1, "rail").unwrap();
        let road = graph.add_edge(a, b, 2, "road").unwrap();

        let edges: Vec<_> = graph.links(a).map(|link| link.edge).collect();
        assert_eq!(edges, vec![rail, road]);
        assert_eq!(graph.degree(a), 2);
        assert_eq!(graph.edge_count(), 2);
        assert_eq!(graph.edge_endpoints(rail), Some((a, b)));
    }

    #[test]
    fn test_view_skips_removed_node_ids() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let a = graph.add_node(1);
        let b = graph.add_node(2);
        let c = graph.add_node(3);
        graph.remove_node(b).unwrap();

        assert_eq!(graph.node_id_vec(), vec![a, c]);
        assert!(!graph.contains_node(b));
        assert_eq!(graph.links(b).count(), 0);
    }
}