god_gragh/graph/
traits.rs

1//! 图核心 trait 定义
2//!
3//! 定义图操作的基本接口，支持泛型实现
4
5use crate::edge::{EdgeIndex, EdgeRef};
6use crate::node::{NodeIndex, NodeRef};
7use crate::errors::{GraphError, GraphResult};
8
9/// 图基础 trait
10///
11/// 定义所有图类型必须实现的基本操作
12pub trait GraphBase {
13    /// 节点数据类型
14    type NodeData;
15    /// 边数据类型
16    type EdgeData;
17
18    /// 获取节点数量
19    fn node_count(&self) -> usize;
20
21    /// 获取边数量
22    fn edge_count(&self) -> usize;
23
24    /// 检查是否为空图
25    fn is_empty(&self) -> bool {
26        self.node_count() == 0
27    }
28
29    /// 检查是否包含节点
30    fn contains_node(&self, index: NodeIndex) -> bool;
31
32    /// 检查是否包含边
33    fn contains_edge(&self, index: EdgeIndex) -> bool;
34}
35
36/// 图查询 trait
37///
38/// 定义图的只读查询操作
39pub trait GraphQuery: GraphBase {
40    /// 获取节点引用
41    fn get_node(&self, index: NodeIndex) -> GraphResult<&Self::NodeData>;
42
43    /// 获取边引用
44    fn get_edge(&self, index: EdgeIndex) -> GraphResult<&Self::EdgeData>;
45
46    /// 获取边的端点
47    fn edge_endpoints(&self, index: EdgeIndex) -> GraphResult<(NodeIndex, NodeIndex)>;
48
49    /// 获取节点的出边邻居迭代器
50    fn neighbors(&self, node: NodeIndex) -> impl Iterator<Item = NodeIndex>;
51
52    /// 获取节点的关联边迭代器
53    fn incident_edges(&self, node: NodeIndex) -> impl Iterator<Item = EdgeIndex>;
54
55    /// 检查是否存在从 from 到 to 的边
56    fn has_edge(&self, from: NodeIndex, to: NodeIndex) -> bool;
57
58    /// 获取节点的出度
59    fn out_degree(&self, node: NodeIndex) -> GraphResult<usize>;
60
61    /// 获取节点的入度（有向图）
62    fn in_degree(&self, node: NodeIndex) -> GraphResult<usize> {
63        self.out_degree(node)
64    }
65
66    /// 获取节点的总度数
67    fn degree(&self, node: NodeIndex) -> GraphResult<usize> {
68        self.out_degree(node)
69    }
70
71    /// 获取所有节点迭代器
72    fn nodes(&self) -> impl Iterator<Item = NodeRef<'_, Self::NodeData>>;
73
74    /// 获取所有边迭代器
75    fn edges(&self) -> impl Iterator<Item = EdgeRef<'_, Self::EdgeData>>;
76}
77
78/// 图可变操作 trait
79///
80/// 定义图的可变操作
81pub trait GraphOps: GraphBase {
82    /// 添加节点
83    fn add_node(&mut self, data: Self::NodeData) -> GraphResult<NodeIndex>;
84
85    /// 删除节点，返回节点数据
86    fn remove_node(&mut self, index: NodeIndex) -> GraphResult<Self::NodeData>;
87
88    /// 添加边
89    fn add_edge(
90        &mut self,
91        from: NodeIndex,
92        to: NodeIndex,
93        data: Self::EdgeData,
94    ) -> GraphResult<EdgeIndex>;
95
96    /// 删除边，返回边数据
97    fn remove_edge(&mut self, index: EdgeIndex) -> GraphResult<Self::EdgeData>;
98
99    /// 更新节点数据，返回旧数据
100    fn update_node(
101        &mut self,
102        index: NodeIndex,
103        data: Self::NodeData,
104    ) -> GraphResult<Self::NodeData>;
105
106    /// 更新边数据，返回旧数据
107    fn update_edge(
108        &mut self,
109        index: EdgeIndex,
110        data: Self::EdgeData,
111    ) -> GraphResult<Self::EdgeData>;
112
113    /// 清空图
114    fn clear(&mut self);
115
116    /// 预分配容量
117    fn reserve(&mut self, additional_nodes: usize, additional_edges: usize);
118}
119
120/// 边方向
121#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
122pub enum Direction {
123    /// 出边方向
124    Outgoing,
125    /// 入边方向
126    Incoming,
127}
128
129impl Direction {
130    /// 获取相反方向
131    #[inline]
132    pub fn opposite(self) -> Self {
133        match self {
134            Direction::Outgoing => Direction::Incoming,
135            Direction::Incoming => Direction::Outgoing,
136        }
137    }
138
139    /// 检查是否为出边方向
140    #[inline]
141    pub fn is_outgoing(self) -> bool {
142        matches!(self, Direction::Outgoing)
143    }
144
145    /// 检查是否为入边方向
146    #[inline]
147    pub fn is_incoming(self) -> bool {
148        matches!(self, Direction::Incoming)
149    }
150}
151
152/// 索引验证辅助函数
153///
154/// 验证 NodeIndex 的 generation 是否匹配
155#[inline]
156pub fn validate_node_index(provided: NodeIndex, current_generation: u32) -> GraphResult<()> {
157    if provided.generation() == current_generation {
158        Ok(())
159    } else {
160        Err(GraphError::NodeDeleted {
161            index: provided.index(),
162            provided: provided.generation(),
163            current: current_generation,
164        })
165    }
166}
167
168/// 索引验证辅助函数
169///
170/// 验证 EdgeIndex 的 generation 是否匹配
171#[inline]
172pub fn validate_edge_index(provided: EdgeIndex, current_generation: u32) -> GraphResult<()> {
173    if provided.generation() == current_generation {
174        Ok(())
175    } else {
176        Err(GraphError::EdgeDeleted {
177            index: provided.index(),
178            provided: provided.generation(),
179            current: current_generation,
180        })
181    }
182}
183
184#[cfg(test)]
185mod tests {
186    use super::*;
187
188    #[test]
189    fn test_direction() {
190        assert_eq!(Direction::Outgoing.opposite(), Direction::Incoming);
191        assert_eq!(Direction::Incoming.opposite(), Direction::Outgoing);
192        assert!(Direction::Outgoing.is_outgoing());
193        assert!(Direction::Incoming.is_incoming());
194    }
195}
god_gragh/graph/traits.rs

god_gragh/graph/
traits.rs
