oximedia_graph/
graph_merge.rs

1#![allow(dead_code)]
2//! Graph merging utilities for combining multiple filter graphs.
3//!
4//! This module supports merging two directed graphs into one, with
5//! configurable strategies for handling node ID conflicts, edge
6//! deduplication, and cross-graph linking.
7
8use std::collections::{HashMap, HashSet};
9
10/// A node identifier in a merge graph.
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
12pub struct MergeNodeId(
13    /// Inner identifier value.
14    pub usize,
15);
16
17impl std::fmt::Display for MergeNodeId {
18    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
19        write!(f, "MergeNode({})", self.0)
20    }
21}
22
23/// A labeled node in a merge graph.
24#[derive(Debug, Clone)]
25pub struct MergeNode {
26    /// Unique identifier.
27    pub id: MergeNodeId,
28    /// Human-readable label.
29    pub label: String,
30    /// Metadata key-value pairs.
31    pub metadata: HashMap<String, String>,
32}
33
34impl MergeNode {
35    /// Create a new merge node.
36    pub fn new(id: MergeNodeId, label: &str) -> Self {
37        Self {
38            id,
39            label: label.to_string(),
40            metadata: HashMap::new(),
41        }
42    }
43
44    /// Add a metadata entry.
45    pub fn with_metadata(mut self, key: &str, value: &str) -> Self {
46        self.metadata.insert(key.to_string(), value.to_string());
47        self
48    }
49}
50
51/// A directed edge in a merge graph.
52#[derive(Debug, Clone, PartialEq, Eq, Hash)]
53pub struct MergeEdge {
54    /// Source node.
55    pub from: MergeNodeId,
56    /// Destination node.
57    pub to: MergeNodeId,
58    /// Optional label for the edge.
59    pub label: Option<String>,
60    /// Weight of the edge (for priority resolution).
61    pub weight: u32,
62}
63
64impl MergeEdge {
65    /// Create a new merge edge.
66    pub fn new(from: MergeNodeId, to: MergeNodeId) -> Self {
67        Self {
68            from,
69            to,
70            label: None,
71            weight: 1,
72        }
73    }
74
75    /// Create a new merge edge with a label.
76    pub fn with_label(from: MergeNodeId, to: MergeNodeId, label: &str) -> Self {
77        Self {
78            from,
79            to,
80            label: Some(label.to_string()),
81            weight: 1,
82        }
83    }
84
85    /// Set the weight of the edge.
86    pub fn with_weight(mut self, weight: u32) -> Self {
87        self.weight = weight;
88        self
89    }
90}
91
92/// Strategy for resolving node ID conflicts during a merge.
93#[derive(Debug, Clone, Copy, PartialEq, Eq)]
94pub enum ConflictStrategy {
95    /// Keep nodes from the first graph, skip duplicates from the second.
96    KeepFirst,
97    /// Keep nodes from the second graph, overwriting the first.
98    KeepSecond,
99    /// Remap IDs of the second graph to avoid conflicts.
100    Remap,
101    /// Fail the merge if any conflict is detected.
102    Fail,
103}
104
105#[allow(clippy::derivable_impls)]
106impl Default for ConflictStrategy {
107    fn default() -> Self {
108        Self::Remap
109    }
110}
111
112/// Configuration for the merge operation.
113#[derive(Debug, Clone)]
114pub struct MergeConfig {
115    /// How to handle node ID conflicts.
116    pub conflict_strategy: ConflictStrategy,
117    /// Whether to deduplicate edges after merging.
118    pub deduplicate_edges: bool,
119    /// Optional cross-links to add between the two graphs.
120    pub cross_links: Vec<(MergeNodeId, MergeNodeId)>,
121}
122
123impl Default for MergeConfig {
124    fn default() -> Self {
125        Self {
126            conflict_strategy: ConflictStrategy::Remap,
127            deduplicate_edges: true,
128            cross_links: Vec::new(),
129        }
130    }
131}
132
133/// Error types for merge operations.
134#[derive(Debug, Clone, PartialEq, Eq)]
135pub enum MergeError {
136    /// Node ID conflict with Fail strategy.
137    Conflict(
138        /// The conflicting node ID.
139        MergeNodeId,
140    ),
141    /// A referenced node does not exist.
142    NodeNotFound(
143        /// The missing node.
144        MergeNodeId,
145    ),
146    /// Both graphs are empty.
147    EmptyGraphs,
148}
149
150impl std::fmt::Display for MergeError {
151    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
152        match self {
153            Self::Conflict(id) => write!(f, "Node conflict: {id}"),
154            Self::NodeNotFound(id) => write!(f, "Node not found: {id}"),
155            Self::EmptyGraphs => write!(f, "Both graphs are empty"),
156        }
157    }
158}
159
160/// A directed graph supporting merge operations.
161pub struct MergeGraph {
162    /// Nodes indexed by their ID.
163    nodes: HashMap<MergeNodeId, MergeNode>,
164    /// Directed edges.
165    edges: Vec<MergeEdge>,
166}
167
168impl MergeGraph {
169    /// Create a new empty merge graph.
170    pub fn new() -> Self {
171        Self {
172            nodes: HashMap::new(),
173            edges: Vec::new(),
174        }
175    }
176
177    /// Add a node to the graph.
178    pub fn add_node(&mut self, node: MergeNode) {
179        self.nodes.insert(node.id, node);
180    }
181
182    /// Add an edge to the graph.
183    pub fn add_edge(&mut self, edge: MergeEdge) {
184        self.edges.push(edge);
185    }
186
187    /// Return the number of nodes.
188    pub fn node_count(&self) -> usize {
189        self.nodes.len()
190    }
191
192    /// Return the number of edges.
193    pub fn edge_count(&self) -> usize {
194        self.edges.len()
195    }
196
197    /// Check if a node exists in the graph.
198    pub fn has_node(&self, id: MergeNodeId) -> bool {
199        self.nodes.contains_key(&id)
200    }
201
202    /// Get a reference to a node by ID.
203    pub fn get_node(&self, id: MergeNodeId) -> Option<&MergeNode> {
204        self.nodes.get(&id)
205    }
206
207    /// Return all node IDs, sorted.
208    pub fn node_ids(&self) -> Vec<MergeNodeId> {
209        let mut ids: Vec<MergeNodeId> = self.nodes.keys().copied().collect();
210        ids.sort();
211        ids
212    }
213
214    /// Return all edges.
215    pub fn edges(&self) -> &[MergeEdge] {
216        &self.edges
217    }
218
219    /// Return the next available ID (max + 1).
220    pub fn next_id(&self) -> MergeNodeId {
221        let max = self.nodes.keys().map(|k| k.0).max().unwrap_or(0);
222        MergeNodeId(max + 1)
223    }
224
225    /// Merge another graph into this one using the given configuration.
226    pub fn merge(
227        &mut self,
228        other: &MergeGraph,
229        config: &MergeConfig,
230    ) -> Result<MergeMapping, MergeError> {
231        let mut mapping = MergeMapping::new();
232
233        match config.conflict_strategy {
234            ConflictStrategy::Remap => {
235                let mut next_id = self.next_id().0;
236                for (&old_id, node) in &other.nodes {
237                    if self.nodes.contains_key(&old_id) {
238                        let new_id = MergeNodeId(next_id);
239                        next_id += 1;
240                        mapping.add(old_id, new_id);
241                        let mut new_node = node.clone();
242                        new_node.id = new_id;
243                        self.nodes.insert(new_id, new_node);
244                    } else {
245                        mapping.add(old_id, old_id);
246                        self.nodes.insert(old_id, node.clone());
247                    }
248                }
249            }
250            ConflictStrategy::KeepFirst => {
251                for (&old_id, node) in &other.nodes {
252                    self.nodes.entry(old_id).or_insert_with(|| node.clone());
253                    mapping.add(old_id, old_id);
254                }
255            }
256            ConflictStrategy::KeepSecond => {
257                for (&old_id, node) in &other.nodes {
258                    self.nodes.insert(old_id, node.clone());
259                    mapping.add(old_id, old_id);
260                }
261            }
262            ConflictStrategy::Fail => {
263                for &old_id in other.nodes.keys() {
264                    if self.nodes.contains_key(&old_id) {
265                        return Err(MergeError::Conflict(old_id));
266                    }
267                }
268                for (&old_id, node) in &other.nodes {
269                    self.nodes.insert(old_id, node.clone());
270                    mapping.add(old_id, old_id);
271                }
272            }
273        }
274
275        // Remap and add edges from the other graph
276        for edge in &other.edges {
277            let new_from = mapping.resolve(edge.from);
278            let new_to = mapping.resolve(edge.to);
279            let new_edge = MergeEdge {
280                from: new_from,
281                to: new_to,
282                label: edge.label.clone(),
283                weight: edge.weight,
284            };
285            self.edges.push(new_edge);
286        }
287
288        // Add cross-links
289        for &(from, to) in &config.cross_links {
290            self.edges.push(MergeEdge::new(from, to));
291        }
292
293        // Deduplicate edges if requested
294        if config.deduplicate_edges {
295            self.deduplicate_edges();
296        }
297
298        Ok(mapping)
299    }
300
301    /// Remove duplicate edges (same from/to pair).
302    fn deduplicate_edges(&mut self) {
303        let mut seen: HashSet<(MergeNodeId, MergeNodeId)> = HashSet::new();
304        self.edges.retain(|e| seen.insert((e.from, e.to)));
305    }
306
307    /// Return the set of edges as (from, to) pairs.
308    pub fn edge_pairs(&self) -> HashSet<(MergeNodeId, MergeNodeId)> {
309        self.edges.iter().map(|e| (e.from, e.to)).collect()
310    }
311
312    /// Return the adjacency list representation.
313    pub fn adjacency_list(&self) -> HashMap<MergeNodeId, Vec<MergeNodeId>> {
314        let mut adj: HashMap<MergeNodeId, Vec<MergeNodeId>> = HashMap::new();
315        for id in self.nodes.keys() {
316            adj.entry(*id).or_default();
317        }
318        for edge in &self.edges {
319            adj.entry(edge.from).or_default().push(edge.to);
320        }
321        for list in adj.values_mut() {
322            list.sort();
323        }
324        adj
325    }
326}
327
328impl Default for MergeGraph {
329    fn default() -> Self {
330        Self::new()
331    }
332}
333
334/// Tracks ID remapping from a merge operation.
335#[derive(Debug, Clone)]
336pub struct MergeMapping {
337    /// Map from old ID to new ID.
338    map: HashMap<MergeNodeId, MergeNodeId>,
339}
340
341impl MergeMapping {
342    /// Create a new empty mapping.
343    pub fn new() -> Self {
344        Self {
345            map: HashMap::new(),
346        }
347    }
348
349    /// Add a mapping entry.
350    pub fn add(&mut self, old_id: MergeNodeId, new_id: MergeNodeId) {
351        self.map.insert(old_id, new_id);
352    }
353
354    /// Resolve an old ID to its new ID. Returns the old ID if no mapping exists.
355    pub fn resolve(&self, old_id: MergeNodeId) -> MergeNodeId {
356        self.map.get(&old_id).copied().unwrap_or(old_id)
357    }
358
359    /// Return the number of remapped entries.
360    pub fn remap_count(&self) -> usize {
361        self.map.iter().filter(|(k, v)| k != v).count()
362    }
363
364    /// Check if any IDs were actually remapped.
365    pub fn has_remaps(&self) -> bool {
366        self.remap_count() > 0
367    }
368
369    /// Return all mappings.
370    pub fn mappings(&self) -> &HashMap<MergeNodeId, MergeNodeId> {
371        &self.map
372    }
373}
374
375impl Default for MergeMapping {
376    fn default() -> Self {
377        Self::new()
378    }
379}
380
381#[cfg(test)]
382mod tests {
383    use super::*;
384
385    fn mn(id: usize) -> MergeNodeId {
386        MergeNodeId(id)
387    }
388
389    fn make_node(id: usize, label: &str) -> MergeNode {
390        MergeNode::new(mn(id), label)
391    }
392
393    #[test]
394    fn test_empty_graph() {
395        let graph = MergeGraph::new();
396        assert_eq!(graph.node_count(), 0);
397        assert_eq!(graph.edge_count(), 0);
398    }
399
400    #[test]
401    fn test_add_node_and_edge() {
402        let mut graph = MergeGraph::new();
403        graph.add_node(make_node(0, "A"));
404        graph.add_node(make_node(1, "B"));
405        graph.add_edge(MergeEdge::new(mn(0), mn(1)));
406        assert_eq!(graph.node_count(), 2);
407        assert_eq!(graph.edge_count(), 1);
408    }
409
410    #[test]
411    fn test_merge_no_conflict() {
412        let mut g1 = MergeGraph::new();
413        g1.add_node(make_node(0, "A"));
414        g1.add_node(make_node(1, "B"));
415        g1.add_edge(MergeEdge::new(mn(0), mn(1)));
416
417        let mut g2 = MergeGraph::new();
418        g2.add_node(make_node(2, "C"));
419        g2.add_node(make_node(3, "D"));
420        g2.add_edge(MergeEdge::new(mn(2), mn(3)));
421
422        let config = MergeConfig::default();
423        let mapping = g1.merge(&g2, &config).expect("merge should succeed");
424        assert_eq!(g1.node_count(), 4);
425        assert_eq!(g1.edge_count(), 2);
426        assert!(!mapping.has_remaps());
427    }
428
429    #[test]
430    fn test_merge_with_remap() {
431        let mut g1 = MergeGraph::new();
432        g1.add_node(make_node(0, "A"));
433
434        let mut g2 = MergeGraph::new();
435        g2.add_node(make_node(0, "B")); // Conflict!
436
437        let config = MergeConfig {
438            conflict_strategy: ConflictStrategy::Remap,
439            ..Default::default()
440        };
441        let mapping = g1.merge(&g2, &config).expect("merge should succeed");
442        assert_eq!(g1.node_count(), 2);
443        assert!(mapping.has_remaps());
444    }
445
446    #[test]
447    fn test_merge_keep_first() {
448        let mut g1 = MergeGraph::new();
449        g1.add_node(make_node(0, "A"));
450
451        let mut g2 = MergeGraph::new();
452        g2.add_node(make_node(0, "B"));
453
454        let config = MergeConfig {
455            conflict_strategy: ConflictStrategy::KeepFirst,
456            ..Default::default()
457        };
458        g1.merge(&g2, &config).expect("merge should succeed");
459        assert_eq!(g1.node_count(), 1);
460        assert_eq!(
461            g1.get_node(mn(0)).expect("value should be valid").label,
462            "A"
463        );
464    }
465
466    #[test]
467    fn test_merge_keep_second() {
468        let mut g1 = MergeGraph::new();
469        g1.add_node(make_node(0, "A"));
470
471        let mut g2 = MergeGraph::new();
472        g2.add_node(make_node(0, "B"));
473
474        let config = MergeConfig {
475            conflict_strategy: ConflictStrategy::KeepSecond,
476            ..Default::default()
477        };
478        g1.merge(&g2, &config).expect("merge should succeed");
479        assert_eq!(g1.node_count(), 1);
480        assert_eq!(
481            g1.get_node(mn(0)).expect("value should be valid").label,
482            "B"
483        );
484    }
485
486    #[test]
487    fn test_merge_fail_on_conflict() {
488        let mut g1 = MergeGraph::new();
489        g1.add_node(make_node(0, "A"));
490
491        let mut g2 = MergeGraph::new();
492        g2.add_node(make_node(0, "B"));
493
494        let config = MergeConfig {
495            conflict_strategy: ConflictStrategy::Fail,
496            ..Default::default()
497        };
498        let result = g1.merge(&g2, &config);
499        assert!(matches!(result, Err(MergeError::Conflict(_))));
500    }
501
502    #[test]
503    fn test_merge_with_cross_links() {
504        let mut g1 = MergeGraph::new();
505        g1.add_node(make_node(0, "A"));
506
507        let mut g2 = MergeGraph::new();
508        g2.add_node(make_node(1, "B"));
509
510        let config = MergeConfig {
511            cross_links: vec![(mn(0), mn(1))],
512            ..Default::default()
513        };
514        g1.merge(&g2, &config).expect("merge should succeed");
515        assert_eq!(g1.edge_count(), 1);
516    }
517
518    #[test]
519    fn test_edge_deduplication() {
520        let mut graph = MergeGraph::new();
521        graph.add_node(make_node(0, "A"));
522        graph.add_node(make_node(1, "B"));
523        graph.add_edge(MergeEdge::new(mn(0), mn(1)));
524        graph.add_edge(MergeEdge::new(mn(0), mn(1)));
525        graph.deduplicate_edges();
526        assert_eq!(graph.edge_count(), 1);
527    }
528
529    #[test]
530    fn test_edge_pairs() {
531        let mut graph = MergeGraph::new();
532        graph.add_node(make_node(0, "A"));
533        graph.add_node(make_node(1, "B"));
534        graph.add_edge(MergeEdge::new(mn(0), mn(1)));
535        let pairs = graph.edge_pairs();
536        assert!(pairs.contains(&(mn(0), mn(1))));
537    }
538
539    #[test]
540    fn test_adjacency_list() {
541        let mut graph = MergeGraph::new();
542        graph.add_node(make_node(0, "A"));
543        graph.add_node(make_node(1, "B"));
544        graph.add_node(make_node(2, "C"));
545        graph.add_edge(MergeEdge::new(mn(0), mn(1)));
546        graph.add_edge(MergeEdge::new(mn(0), mn(2)));
547        let adj = graph.adjacency_list();
548        assert_eq!(adj[&mn(0)], vec![mn(1), mn(2)]);
549    }
550
551    #[test]
552    fn test_node_metadata() {
553        let node = make_node(0, "Test").with_metadata("type", "source");
554        assert_eq!(node.metadata.get("type"), Some(&"source".to_string()));
555    }
556
557    #[test]
558    fn test_edge_with_label() {
559        let edge = MergeEdge::with_label(mn(0), mn(1), "data_flow");
560        assert_eq!(edge.label, Some("data_flow".to_string()));
561    }
562
563    #[test]
564    fn test_edge_weight() {
565        let edge = MergeEdge::new(mn(0), mn(1)).with_weight(5);
566        assert_eq!(edge.weight, 5);
567    }
568
569    #[test]
570    fn test_merge_mapping_resolve() {
571        let mut mapping = MergeMapping::new();
572        mapping.add(mn(0), mn(10));
573        assert_eq!(mapping.resolve(mn(0)), mn(10));
574        assert_eq!(mapping.resolve(mn(5)), mn(5)); // unmapped
575    }
576
577    #[test]
578    fn test_merge_error_display() {
579        let err = MergeError::Conflict(mn(5));
580        assert!(format!("{err}").contains("5"));
581        let err2 = MergeError::EmptyGraphs;
582        assert_eq!(format!("{err2}"), "Both graphs are empty");
583    }
584
585    #[test]
586    fn test_next_id() {
587        let mut graph = MergeGraph::new();
588        graph.add_node(make_node(0, "A"));
589        graph.add_node(make_node(5, "B"));
590        assert_eq!(graph.next_id(), mn(6));
591    }
592
593    #[test]
594    fn test_has_node() {
595        let mut graph = MergeGraph::new();
596        graph.add_node(make_node(0, "A"));
597        assert!(graph.has_node(mn(0)));
598        assert!(!graph.has_node(mn(1)));
599    }
600}
oximedia_graph/graph_merge.rs

oximedia_graph/
graph_merge.rs
