graph_core/
graph.rs

1use crate::{Edge, NodeId};
2
3/// The central graph abstraction that every algorithm in graph-rs operates on.
4///
5/// `N` is the node-data type and `W` is the edge-weight type.
6///
7/// Implementors provide two associated iterator types — `NodeIter<'a>` and
8/// `NeighborIter<'a>` — that borrow from `&self`. These are **Generic
9/// Associated Types** (GATs, stable since Rust 1.65): associated types that
10/// are themselves generic over a lifetime, enabling zero-allocation iterators
11/// that reference graph internals directly.
12///
13/// # Implementing `Graph`
14///
15/// ```ignore
16/// use graph_core::{Graph, NodeId, Edge};
17///
18/// struct MyGraph { /* ... */ }
19///
20/// impl Graph for MyGraph {
21///     type NodeData = String;
22///     type Weight   = f64;
23///     // ... (see AdjacencyList for a complete example)
24/// }
25/// ```
26pub trait Graph {
27    /// Data stored at each node (e.g. `String`, `()`, coordinates).
28    type NodeData;
29
30    /// Edge-weight type (e.g. `f64`, `u32`, `()`).
31    type Weight;
32
33    /// Iterator over all [`NodeId`]s in the graph.
34    type NodeIter<'a>: Iterator<Item = NodeId>
35    where
36        Self: 'a;
37
38    /// Iterator over `(neighbour_id, &weight)` pairs for one node.
39    type NeighborIter<'a>: Iterator<Item = (NodeId, &'a Self::Weight)>
40    where
41        Self: 'a;
42
43    // ── Mutation ──────────────────────────────────────────────────────────────
44
45    /// Adds a node with the given data and returns its [`NodeId`].
46    fn add_node(&mut self, data: Self::NodeData) -> NodeId;
47
48    /// Adds a directed edge from `from` to `to` with `weight`.
49    ///
50    /// # Errors
51    ///
52    /// Returns [`GraphError`](crate::GraphError) if either node does not exist.
53    fn add_edge(
54        &mut self,
55        from: NodeId,
56        to: NodeId,
57        weight: Self::Weight,
58    ) -> Result<(), crate::GraphError>;
59
60    /// Removes the node at `id` and all edges incident to it.
61    ///
62    /// Returns the node data if found, or `None` if the node did not exist.
63    fn remove_node(&mut self, id: NodeId) -> Option<Self::NodeData>;
64
65    // ── Query ─────────────────────────────────────────────────────────────────
66
67    /// Returns the number of nodes.
68    fn node_count(&self) -> usize;
69
70    /// Returns the number of directed edges.
71    fn edge_count(&self) -> usize;
72
73    /// Returns `true` if the graph contains a node with this id.
74    fn contains_node(&self, id: NodeId) -> bool;
75
76    /// Returns `true` if there is a directed edge from `from` to `to`.
77    fn contains_edge(&self, from: NodeId, to: NodeId) -> bool;
78
79    /// Returns the out-degree of node `id` (number of outgoing edges).
80    ///
81    /// # Panics
82    ///
83    /// Panics if `id` does not exist in the graph.
84    fn degree(&self, id: NodeId) -> usize;
85
86    // ── Iteration ─────────────────────────────────────────────────────────────
87
88    /// Returns an iterator over all [`NodeId`]s in the graph.
89    fn nodes(&self) -> Self::NodeIter<'_>;
90
91    /// Returns an iterator over `(neighbour_id, &weight)` for all outgoing
92    /// edges of `id`.
93    ///
94    /// # Panics
95    ///
96    /// Panics if `id` does not exist in the graph.
97    fn neighbors(&self, id: NodeId) -> Self::NeighborIter<'_>;
98
99    // ── Provided helpers ──────────────────────────────────────────────────────
100
101    /// Returns all edges in the graph as [`Edge<W>`] values.
102    ///
103    /// Default implementation iterates over all nodes and their neighbours.
104    /// Implementations may override this for efficiency.
105    fn all_edges(&self) -> Vec<Edge<Self::Weight>>
106    where
107        Self::Weight: Clone,
108    {
109        let mut edges = Vec::new();
110        for u in self.nodes() {
111            for (v, w) in self.neighbors(u) {
112                edges.push(Edge::new(u, v, w.clone()));
113            }
114        }
115        edges
116    }
117
118    /// Returns `true` if the graph has no nodes.
119    ///
120    /// # Examples
121    ///
122    /// ```
123    /// use graph_core::{AdjacencyList, Graph};
124    ///
125    /// let g: AdjacencyList<()> = AdjacencyList::directed();
126    /// assert!(g.is_empty());
127    /// ```
128    #[inline]
129    fn is_empty(&self) -> bool {
130        self.node_count() == 0
131    }
132}
graph_core/graph.rs

graph_core/
graph.rs
