sz_orm_graph/
subgraph.rs

1//! 子图匹配与图同构（Subgraph Matching）
2//!
3//! 提供子图查找、图同构检测等功能。
4
5use std::collections::{HashMap, HashSet};
6
7use crate::algorithm::{DirectedGraph, NodeId};
8
9/// 子图匹配器
10pub struct SubgraphMatcher;
11
12impl SubgraphMatcher {
13    /// 查找模式图在目标图中的所有匹配
14    ///
15    /// 返回每个匹配的节点映射（模式节点 -> 目标节点）。
16    /// 使用简单的回溯算法，适用于小规模模式图。
17    pub fn find_matches(
18        pattern: &DirectedGraph,
19        target: &DirectedGraph,
20    ) -> Vec<HashMap<NodeId, NodeId>> {
21        let pattern_nodes: Vec<NodeId> = pattern.nodes().collect();
22        if pattern_nodes.is_empty() {
23            return Vec::new();
24        }
25        let target_nodes: Vec<NodeId> = target.nodes().collect();
26        let mut results = Vec::new();
27        let mut mapping = HashMap::new();
28        let mut used = HashSet::new();
29        Self::match_recursive(
30            pattern,
31            target,
32            &pattern_nodes,
33            &target_nodes,
34            0,
35            &mut mapping,
36            &mut used,
37            &mut results,
38        );
39        results
40    }
41
42    #[allow(clippy::too_many_arguments)]
43    fn match_recursive(
44        pattern: &DirectedGraph,
45        target: &DirectedGraph,
46        pattern_nodes: &[NodeId],
47        target_nodes: &[NodeId],
48        idx: usize,
49        mapping: &mut HashMap<NodeId, NodeId>,
50        used: &mut HashSet<NodeId>,
51        results: &mut Vec<HashMap<NodeId, NodeId>>,
52    ) {
53        if idx == pattern_nodes.len() {
54            results.push(mapping.clone());
55            return;
56        }
57        let pattern_node = pattern_nodes[idx];
58        for &target_node in target_nodes {
59            if used.contains(&target_node) {
60                continue;
61            }
62            if !Self::is_consistent(pattern, target, pattern_node, target_node, mapping) {
63                continue;
64            }
65            mapping.insert(pattern_node, target_node);
66            used.insert(target_node);
67            Self::match_recursive(
68                pattern,
69                target,
70                pattern_nodes,
71                target_nodes,
72                idx + 1,
73                mapping,
74                used,
75                results,
76            );
77            mapping.remove(&pattern_node);
78            used.remove(&target_node);
79        }
80    }
81
82    fn is_consistent(
83        pattern: &DirectedGraph,
84        target: &DirectedGraph,
85        pattern_node: NodeId,
86        target_node: NodeId,
87        mapping: &HashMap<NodeId, NodeId>,
88    ) -> bool {
89        if let Some(p_neighbors) = pattern.neighbors(pattern_node) {
90            for &(p_neighbor, _) in p_neighbors {
91                if let Some(&t_neighbor) = mapping.get(&p_neighbor) {
92                    if !target.has_edge(target_node, t_neighbor) {
93                        return false;
94                    }
95                }
96            }
97        }
98        for (&mapped_p, &mapped_t) in mapping.iter() {
99            if let Some(p_neighbors) = pattern.neighbors(mapped_p) {
100                for &(p_neighbor, _) in p_neighbors {
101                    if p_neighbor == pattern_node && !target.has_edge(mapped_t, target_node) {
102                        return false;
103                    }
104                }
105            }
106        }
107        true
108    }
109
110    /// 检查模式图是否是目标图的子图
111    pub fn is_subgraph(pattern: &DirectedGraph, target: &DirectedGraph) -> bool {
112        !Self::find_matches(pattern, target).is_empty()
113    }
114
115    /// 统计模式图在目标图中的匹配数
116    pub fn count_matches(pattern: &DirectedGraph, target: &DirectedGraph) -> usize {
117        Self::find_matches(pattern, target).len()
118    }
119}
120
121/// 图同构检测器
122pub struct IsomorphismChecker;
123
124impl IsomorphismChecker {
125    /// 检查两个图是否同构
126    ///
127    /// 两个图同构当且仅当存在节点的一一映射，保持边关系。
128    pub fn is_isomorphic(g1: &DirectedGraph, g2: &DirectedGraph) -> bool {
129        if g1.node_count() != g2.node_count() {
130            return false;
131        }
132        if g1.edge_count() != g2.edge_count() {
133            return false;
134        }
135        if g1.node_count() == 0 {
136            return true;
137        }
138        let g1_invariants = Self::compute_invariants(g1);
139        let g2_invariants = Self::compute_invariants(g2);
140        if g1_invariants != g2_invariants {
141            return false;
142        }
143        !SubgraphMatcher::find_matches(g1, g2).is_empty()
144    }
145
146    /// 计算图的不变量（用于快速排除非同构图）
147    fn compute_invariants(graph: &DirectedGraph) -> Vec<usize> {
148        let mut degree_sequence: Vec<usize> = graph
149            .nodes()
150            .map(|n| graph.in_degree(n) * 1000 + graph.out_degree(n))
151            .collect();
152        degree_sequence.sort_unstable();
153        degree_sequence
154    }
155}
156
157/// 公共子图查找器
158pub struct CommonSubgraphFinder;
159
160impl CommonSubgraphFinder {
161    /// 查找两个图的最大公共子图（节点数最大）
162    ///
163    /// 使用简单的贪心算法，不保证最优解。
164    pub fn largest_common_subgraph(g1: &DirectedGraph, g2: &DirectedGraph) -> DirectedGraph {
165        let g1_nodes: Vec<NodeId> = g1.nodes().collect();
166        let g2_nodes: Vec<NodeId> = g2.nodes().collect();
167        let mut best_mapping: HashMap<NodeId, NodeId> = HashMap::new();
168        for &n1 in &g1_nodes {
169            for &n2 in &g2_nodes {
170                if g1.in_degree(n1) + g1.out_degree(n1) == g2.in_degree(n2) + g2.out_degree(n2)
171                    && !best_mapping.contains_key(&n1)
172                    && !best_mapping.values().any(|&v| v == n2)
173                {
174                    best_mapping.insert(n1, n2);
175                }
176            }
177        }
178        let mut result = DirectedGraph::new();
179        for (&n1, &_n2) in &best_mapping {
180            result.add_node(n1);
181            if let Some(neighbors) = g1.neighbors(n1) {
182                for &(neighbor, weight) in neighbors {
183                    if let Some(&mapped) = best_mapping.get(&neighbor) {
184                        result.add_edge(n1, neighbor, weight);
185                        let _ = mapped;
186                    }
187                }
188            }
189        }
190        result
191    }
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197
198    #[test]
199    fn test_subgraph_match_simple() {
200        let mut target = DirectedGraph::new();
201        target.add_edge_unweighted(1, 2);
202        target.add_edge_unweighted(2, 3);
203        let mut pattern = DirectedGraph::new();
204        pattern.add_edge_unweighted(10, 20);
205        assert!(SubgraphMatcher::is_subgraph(&pattern, &target));
206    }
207
208    #[test]
209    fn test_subgraph_match_no_match() {
210        let mut target = DirectedGraph::new();
211        target.add_edge_unweighted(1, 2);
212        let mut pattern = DirectedGraph::new();
213        pattern.add_edge_unweighted(10, 20);
214        pattern.add_edge_unweighted(20, 30);
215        assert!(!SubgraphMatcher::is_subgraph(&pattern, &target));
216    }
217
218    #[test]
219    fn test_subgraph_count_matches() {
220        let mut target = DirectedGraph::new();
221        target.add_edge_unweighted(1, 2);
222        target.add_edge_unweighted(3, 4);
223        let mut pattern = DirectedGraph::new();
224        pattern.add_edge_unweighted(10, 20);
225        let count = SubgraphMatcher::count_matches(&pattern, &target);
226        assert!(count >= 2);
227    }
228
229    #[test]
230    fn test_subgraph_match_self() {
231        let mut g = DirectedGraph::new();
232        g.add_edge_unweighted(1, 2);
233        g.add_edge_unweighted(2, 3);
234        assert!(SubgraphMatcher::is_subgraph(&g, &g));
235    }
236
237    #[test]
238    fn test_subgraph_match_empty_pattern() {
239        let target = DirectedGraph::new();
240        let pattern = DirectedGraph::new();
241        assert!(!SubgraphMatcher::is_subgraph(&pattern, &target));
242    }
243
244    #[test]
245    fn test_subgraph_match_single_node() {
246        let mut target = DirectedGraph::new();
247        target.add_node(1);
248        let mut pattern = DirectedGraph::new();
249        pattern.add_node(10);
250        assert!(SubgraphMatcher::is_subgraph(&pattern, &target));
251    }
252
253    #[test]
254    fn test_isomorphism_same_graph() {
255        let mut g = DirectedGraph::new();
256        g.add_edge_unweighted(1, 2);
257        g.add_edge_unweighted(2, 3);
258        assert!(IsomorphismChecker::is_isomorphic(&g, &g));
259    }
260
261    #[test]
262    fn test_isomorphism_different_node_count() {
263        let mut g1 = DirectedGraph::new();
264        g1.add_edge_unweighted(1, 2);
265        let mut g2 = DirectedGraph::new();
266        g2.add_edge_unweighted(1, 2);
267        g2.add_node(3);
268        assert!(!IsomorphismChecker::is_isomorphic(&g1, &g2));
269    }
270
271    #[test]
272    fn test_isomorphism_different_edge_count() {
273        let mut g1 = DirectedGraph::new();
274        g1.add_edge_unweighted(1, 2);
275        let mut g2 = DirectedGraph::new();
276        g2.add_edge_unweighted(1, 2);
277        g2.add_edge_unweighted(2, 1);
278        assert!(!IsomorphismChecker::is_isomorphic(&g1, &g2));
279    }
280
281    #[test]
282    fn test_isomorphism_renamed_nodes() {
283        let mut g1 = DirectedGraph::new();
284        g1.add_edge_unweighted(1, 2);
285        let mut g2 = DirectedGraph::new();
286        g2.add_edge_unweighted(10, 20);
287        assert!(IsomorphismChecker::is_isomorphic(&g1, &g2));
288    }
289
290    #[test]
291    fn test_common_subgraph_empty() {
292        let g1 = DirectedGraph::new();
293        let g2 = DirectedGraph::new();
294        let common = CommonSubgraphFinder::largest_common_subgraph(&g1, &g2);
295        assert_eq!(common.node_count(), 0);
296    }
297
298    #[test]
299    fn test_common_subgraph_simple() {
300        let mut g1 = DirectedGraph::new();
301        g1.add_edge_unweighted(1, 2);
302        let mut g2 = DirectedGraph::new();
303        g2.add_edge_unweighted(10, 20);
304        let common = CommonSubgraphFinder::largest_common_subgraph(&g1, &g2);
305        assert!(common.node_count() > 0 || common.node_count() == 0);
306    }
307
308    #[test]
309    fn test_common_subgraph_same_graph() {
310        let mut g1 = DirectedGraph::new();
311        g1.add_edge_unweighted(1, 2);
312        g1.add_edge_unweighted(2, 3);
313        let common = CommonSubgraphFinder::largest_common_subgraph(&g1, &g1);
314        assert!(common.node_count() > 0);
315    }
316
317    #[test]
318    fn test_find_matches_returns_mapping() {
319        let mut target = DirectedGraph::new();
320        target.add_edge_unweighted(1, 2);
321        let mut pattern = DirectedGraph::new();
322        pattern.add_edge_unweighted(10, 20);
323        let matches = SubgraphMatcher::find_matches(&pattern, &target);
324        assert!(!matches.is_empty());
325        for mapping in &matches {
326            assert_eq!(mapping.len(), 2);
327        }
328    }
329
330    #[test]
331    fn test_isomorphism_empty_graphs() {
332        let g1 = DirectedGraph::new();
333        let g2 = DirectedGraph::new();
334        assert!(IsomorphismChecker::is_isomorphic(&g1, &g2));
335    }
336
337    #[test]
338    fn test_isomorphism_single_node() {
339        let mut g1 = DirectedGraph::new();
340        g1.add_node(1);
341        let mut g2 = DirectedGraph::new();
342        g2.add_node(10);
343        assert!(IsomorphismChecker::is_isomorphic(&g1, &g2));
344    }
345}
sz_orm_graph/subgraph.rs

sz_orm_graph/
subgraph.rs
