rustworkx_core/graph_ext/
contraction.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13//! This module defines graph traits for node contraction.
14
15use crate::dictmap::{DictMap, InitWithHasher};
16use crate::err::{ContractError, ContractSimpleError};
17use crate::graph_ext::NodeRemovable;
18use indexmap::map::Entry;
19use indexmap::IndexSet;
20use petgraph::data::Build;
21use petgraph::graphmap;
22use petgraph::stable_graph;
23use petgraph::visit::{Data, Dfs, EdgeRef, GraphBase, GraphProp, IntoEdgesDirected, Visitable};
24use petgraph::{Directed, Direction, Undirected};
25use std::convert::Infallible;
26use std::error::Error;
27use std::hash::Hash;
28use std::ops::Deref;
29
30pub trait ContractNodesDirected: Data {
31    /// The error type returned by contraction.
32    type Error: Error;
33
34    /// Substitute a set of nodes with a single new node.
35    ///
36    /// The specified `nodes` are removed and replaced with a new node
37    /// with the given `weight`. Any nodes not in the graph are ignored.
38    /// It is valid for `nodes` to be empty, in which case the new node
39    /// is added to the graph without edges.
40    ///
41    /// The contraction may result in multiple edges between nodes if
42    /// the underlying graph is a multi-graph. If this is not desired,
43    /// use [ContractNodesSimpleDirected::contract_nodes_simple].
44    ///
45    /// If `check_cycle` is enabled and the contraction would introduce
46    /// a cycle, an error is returned and the graph is not modified.
47    ///
48    /// The `NodeId` of the newly created node is returned.
49    ///
50    /// # Example
51    /// ```
52    /// use std::convert::Infallible;
53    /// use petgraph::prelude::*;
54    /// use rustworkx_core::graph_ext::*;
55    ///
56    /// // Performs the following transformation:
57    /// //      ┌─┐
58    /// //      │a│
59    /// //      └┬┘              ┌─┐
60    /// //       0               │a│
61    /// //      ┌▼┐              └┬┘
62    /// //      │b│               0
63    /// //      └┬┘              ┌▼┐
64    /// //       1      ───►     │m│
65    /// //      ┌▼┐              └┬┘
66    /// //      │c│               2
67    /// //      └┬┘              ┌▼┐
68    /// //       2               │d│
69    /// //      ┌▼┐              └─┘
70    /// //      │d│
71    /// //      └─┘
72    /// let mut dag: StableDiGraph<char, usize> = StableDiGraph::default();
73    /// let a = dag.add_node('a');
74    /// let b = dag.add_node('b');
75    /// let c = dag.add_node('c');
76    /// let d = dag.add_node('d');
77    /// dag.add_edge(a.clone(), b.clone(), 0);
78    /// dag.add_edge(b.clone(), c.clone(), 1);
79    /// dag.add_edge(c.clone(), d.clone(), 2);
80    ///
81    /// let m = dag.contract_nodes([b, c], 'm', true).unwrap();
82    /// assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &0);
83    /// assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &2);
84    /// ```
85    fn contract_nodes<I>(
86        &mut self,
87        nodes: I,
88        weight: Self::NodeWeight,
89        check_cycle: bool,
90    ) -> Result<Self::NodeId, Self::Error>
91    where
92        I: IntoIterator<Item = Self::NodeId>;
93}
94
95impl<N, E, Ix> ContractNodesDirected for stable_graph::StableGraph<N, E, Directed, Ix>
96where
97    Ix: stable_graph::IndexType,
98    E: Clone,
99{
100    type Error = ContractError;
101
102    fn contract_nodes<I>(
103        &mut self,
104        nodes: I,
105        obj: Self::NodeWeight,
106        check_cycle: bool,
107    ) -> Result<Self::NodeId, Self::Error>
108    where
109        I: IntoIterator<Item = Self::NodeId>,
110    {
111        let nodes = IndexSet::from_iter(nodes);
112        if check_cycle && !can_contract(self.deref(), &nodes) {
113            return Err(ContractError::DAGWouldCycle);
114        }
115        Ok(contract_stable(self, nodes, obj, NoCallback::None).unwrap())
116    }
117}
118
119impl<N, E> ContractNodesDirected for graphmap::GraphMap<N, E, Directed>
120where
121    for<'a> N: graphmap::NodeTrait + 'a,
122    for<'a> E: Clone + 'a,
123{
124    type Error = ContractError;
125
126    fn contract_nodes<I>(
127        &mut self,
128        nodes: I,
129        obj: Self::NodeWeight,
130        check_cycle: bool,
131    ) -> Result<Self::NodeId, Self::Error>
132    where
133        I: IntoIterator<Item = Self::NodeId>,
134    {
135        let nodes = IndexSet::from_iter(nodes);
136        if check_cycle && !can_contract(self.deref(), &nodes) {
137            return Err(ContractError::DAGWouldCycle);
138        }
139        Ok(contract_stable(self, nodes, obj, NoCallback::None).unwrap())
140    }
141}
142
143pub trait ContractNodesSimpleDirected: Data {
144    /// The error type returned by contraction.
145    type Error<Ex: Error>: Error;
146
147    /// Substitute a set of nodes with a single new node.
148    ///
149    /// The specified `nodes` are removed and replaced with a new node
150    /// with the given `weight`. Any nodes not in the graph are ignored.
151    /// It is valid for `nodes` to be empty, in which case the new node
152    /// is added to the graph without edges.
153    ///
154    /// The specified function `weight_combo_fn` is used to merge
155    /// would-be parallel edges during contraction; this function
156    /// preserves simple graphs.
157    ///
158    /// If `check_cycle` is enabled and the contraction would introduce
159    /// a cycle, an error is returned and the graph is not modified.
160    ///
161    /// The `NodeId` of the newly created node is returned.
162    ///
163    /// # Example
164    /// ```
165    /// use std::convert::Infallible;
166    /// use petgraph::prelude::*;
167    /// use rustworkx_core::graph_ext::*;
168    ///
169    /// // Performs the following transformation:
170    /// //                          ┌─┐
171    /// //     ┌─┐                  │a│
172    /// //  ┌0─┤a├─1┐               └┬┘
173    /// //  │  └─┘  │                1
174    /// // ┌▼┐     ┌▼┐              ┌▼┐
175    /// // │b│     │c│     ───►     │m│
176    /// // └┬┘     └┬┘              └┬┘
177    /// //  │  ┌─┐  │                3
178    /// //  └2►│d│◄3┘               ┌▼┐
179    /// //     └─┘                  │d│
180    /// //                          └─┘
181    /// let mut dag: StableDiGraph<char, usize> = StableDiGraph::default();
182    /// let a = dag.add_node('a');
183    /// let b = dag.add_node('b');
184    /// let c = dag.add_node('c');
185    /// let d = dag.add_node('d');
186    /// dag.add_edge(a.clone(), b.clone(), 0);
187    /// dag.add_edge(a.clone(), c.clone(), 1);
188    /// dag.add_edge(b.clone(), d.clone(), 2);
189    /// dag.add_edge(c.clone(), d.clone(), 3);
190    ///
191    /// let m = dag.contract_nodes_simple([b, c], 'm', true, |&e1, &e2| Ok::<_, Infallible>(if e1 > e2 { e1 } else { e2 } )).unwrap();
192    /// assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &1);
193    /// assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &3);
194    /// ```
195    fn contract_nodes_simple<I, F, C: Error>(
196        &mut self,
197        nodes: I,
198        weight: Self::NodeWeight,
199        check_cycle: bool,
200        weight_combo_fn: F,
201    ) -> Result<Self::NodeId, Self::Error<C>>
202    where
203        I: IntoIterator<Item = Self::NodeId>,
204        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>;
205}
206
207impl<N, E, Ix> ContractNodesSimpleDirected for stable_graph::StableGraph<N, E, Directed, Ix>
208where
209    Ix: stable_graph::IndexType,
210    E: Clone,
211{
212    type Error<Err: Error> = ContractSimpleError<Err>;
213
214    fn contract_nodes_simple<I, F, C: Error>(
215        &mut self,
216        nodes: I,
217        weight: Self::NodeWeight,
218        check_cycle: bool,
219        weight_combo_fn: F,
220    ) -> Result<Self::NodeId, Self::Error<C>>
221    where
222        I: IntoIterator<Item = Self::NodeId>,
223        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,
224    {
225        let nodes = IndexSet::from_iter(nodes);
226        if check_cycle && !can_contract(self.deref(), &nodes) {
227            return Err(ContractSimpleError::DAGWouldCycle);
228        }
229        contract_stable(self, nodes, weight, Some(weight_combo_fn))
230            .map_err(ContractSimpleError::MergeError)
231    }
232}
233
234impl<N, E> ContractNodesSimpleDirected for graphmap::GraphMap<N, E, Directed>
235where
236    for<'a> N: graphmap::NodeTrait + 'a,
237    for<'a> E: Clone + 'a,
238{
239    type Error<Err: Error> = ContractSimpleError<Err>;
240
241    fn contract_nodes_simple<I, F, C: Error>(
242        &mut self,
243        nodes: I,
244        weight: Self::NodeWeight,
245        check_cycle: bool,
246        weight_combo_fn: F,
247    ) -> Result<Self::NodeId, Self::Error<C>>
248    where
249        I: IntoIterator<Item = Self::NodeId>,
250        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,
251    {
252        let nodes = IndexSet::from_iter(nodes);
253        if check_cycle && !can_contract(self.deref(), &nodes) {
254            return Err(ContractSimpleError::DAGWouldCycle);
255        }
256        contract_stable(self, nodes, weight, Some(weight_combo_fn))
257            .map_err(ContractSimpleError::MergeError)
258    }
259}
260
261pub trait ContractNodesUndirected: Data {
262    /// Substitute a set of nodes with a single new node.
263    ///
264    /// The specified `nodes` are removed and replaced with a new node
265    /// with the given `weight`. Any nodes not in the graph are ignored.
266    /// It is valid for `nodes` to be empty, in which case the new node
267    /// is added to the graph without edges.
268    ///
269    /// The contraction may result in multiple edges between nodes if
270    /// the underlying graph is a multi-graph. If this is not desired,
271    /// use [ContractNodesSimpleUndirected::contract_nodes_simple].
272    ///
273    /// The `NodeId` of the newly created node is returned.
274    ///
275    /// # Example
276    /// ```
277    /// use petgraph::prelude::*;
278    /// use rustworkx_core::graph_ext::*;
279    ///
280    /// // Performs the following transformation:
281    /// //      ┌─┐
282    /// //      │a│
283    /// //      └┬┘              ┌─┐
284    /// //       0               │a│
285    /// //      ┌┴┐              └┬┘
286    /// //      │b│               0
287    /// //      └┬┘              ┌┴┐
288    /// //       1      ───►     │m│
289    /// //      ┌┴┐              └┬┘
290    /// //      │c│               2
291    /// //      └┬┘              ┌┴┐
292    /// //       2               │d│
293    /// //      ┌┴┐              └─┘
294    /// //      │d│
295    /// //      └─┘
296    /// let mut dag: StableUnGraph<char, usize> = StableUnGraph::default();
297    /// let a = dag.add_node('a');
298    /// let b = dag.add_node('b');
299    /// let c = dag.add_node('c');
300    /// let d = dag.add_node('d');
301    /// dag.add_edge(a.clone(), b.clone(), 0);
302    /// dag.add_edge(b.clone(), c.clone(), 1);
303    /// dag.add_edge(c.clone(), d.clone(), 2);
304    ///
305    /// let m = dag.contract_nodes([b, c], 'm');
306    /// assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &0);
307    /// assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &2);
308    /// ```
309    fn contract_nodes<I>(&mut self, nodes: I, weight: Self::NodeWeight) -> Self::NodeId
310    where
311        I: IntoIterator<Item = Self::NodeId>;
312}
313
314impl<N, E, Ix> ContractNodesUndirected for stable_graph::StableGraph<N, E, Undirected, Ix>
315where
316    Ix: stable_graph::IndexType,
317    E: Clone,
318{
319    fn contract_nodes<I>(&mut self, nodes: I, obj: Self::NodeWeight) -> Self::NodeId
320    where
321        I: IntoIterator<Item = Self::NodeId>,
322    {
323        contract_stable(self, IndexSet::from_iter(nodes), obj, NoCallback::None).unwrap()
324    }
325}
326
327impl<N, E> ContractNodesUndirected for graphmap::GraphMap<N, E, Undirected>
328where
329    for<'a> N: graphmap::NodeTrait + 'a,
330    for<'a> E: Clone + 'a,
331{
332    fn contract_nodes<I>(&mut self, nodes: I, obj: Self::NodeWeight) -> Self::NodeId
333    where
334        I: IntoIterator<Item = Self::NodeId>,
335    {
336        contract_stable(self, IndexSet::from_iter(nodes), obj, NoCallback::None).unwrap()
337    }
338}
339
340pub trait ContractNodesSimpleUndirected: Data {
341    type Error<Ex: Error>: Error;
342
343    /// Substitute a set of nodes with a single new node.
344    ///
345    /// The specified `nodes` are removed and replaced with a new node
346    /// with the given `weight`. Any nodes not in the graph are ignored.
347    /// It is valid for `nodes` to be empty, in which case the new node
348    /// is added to the graph without edges.
349    ///
350    /// The specified function `weight_combo_fn` is used to merge
351    /// would-be parallel edges during contraction; this function
352    /// preserves simple graphs.
353    ///
354    /// The `NodeId` of the newly created node is returned.
355    ///
356    /// # Example
357    /// ```
358    /// use std::convert::Infallible;
359    /// use petgraph::prelude::*;
360    /// use rustworkx_core::graph_ext::*;
361    ///
362    /// // Performs the following transformation:
363    /// //                          ┌─┐
364    /// //     ┌─┐                  │a│
365    /// //  ┌0─┤a├─1┐               └┬┘
366    /// //  │  └─┘  │                1
367    /// // ┌┴┐     ┌┴┐              ┌┴┐
368    /// // │b│     │c│     ───►     │m│
369    /// // └┬┘     └┬┘              └┬┘
370    /// //  │  ┌─┐  │                3
371    /// //  └2─│d├─3┘               ┌┴┐
372    /// //     └─┘                  │d│
373    /// //                          └─┘
374    /// let mut dag: StableUnGraph<char, usize> = StableUnGraph::default();
375    /// let a = dag.add_node('a');
376    /// let b = dag.add_node('b');
377    /// let c = dag.add_node('c');
378    /// let d = dag.add_node('d');
379    /// dag.add_edge(a.clone(), b.clone(), 0);
380    /// dag.add_edge(a.clone(), c.clone(), 1);
381    /// dag.add_edge(b.clone(), d.clone(), 2);
382    /// dag.add_edge(c.clone(), d.clone(), 3);
383    ///
384    /// let m = dag.contract_nodes_simple([b, c], 'm', |&e1, &e2| Ok::<_, Infallible>(if e1 > e2 { e1 } else { e2 } )).unwrap();
385    /// assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &1);
386    /// assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &3);
387    /// ```
388    fn contract_nodes_simple<I, F, C: Error>(
389        &mut self,
390        nodes: I,
391        weight: Self::NodeWeight,
392        weight_combo_fn: F,
393    ) -> Result<Self::NodeId, Self::Error<C>>
394    where
395        I: IntoIterator<Item = Self::NodeId>,
396        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>;
397}
398
399impl<N, E, Ix> ContractNodesSimpleUndirected for stable_graph::StableGraph<N, E, Undirected, Ix>
400where
401    Ix: stable_graph::IndexType,
402    E: Clone,
403{
404    type Error<Err: Error> = ContractSimpleError<Err>;
405
406    fn contract_nodes_simple<I, F, C: Error>(
407        &mut self,
408        nodes: I,
409        weight: Self::NodeWeight,
410        weight_combo_fn: F,
411    ) -> Result<Self::NodeId, Self::Error<C>>
412    where
413        I: IntoIterator<Item = Self::NodeId>,
414        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,
415    {
416        contract_stable(
417            self,
418            IndexSet::from_iter(nodes),
419            weight,
420            Some(weight_combo_fn),
421        )
422        .map_err(ContractSimpleError::MergeError)
423    }
424}
425
426impl<N, E> ContractNodesSimpleUndirected for graphmap::GraphMap<N, E, Undirected>
427where
428    for<'a> N: graphmap::NodeTrait + 'a,
429    for<'a> E: Clone + 'a,
430{
431    type Error<Err: Error> = ContractSimpleError<Err>;
432
433    fn contract_nodes_simple<I, F, C: Error>(
434        &mut self,
435        nodes: I,
436        weight: Self::NodeWeight,
437        weight_combo_fn: F,
438    ) -> Result<Self::NodeId, Self::Error<C>>
439    where
440        I: IntoIterator<Item = Self::NodeId>,
441        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,
442    {
443        contract_stable(
444            self,
445            IndexSet::from_iter(nodes),
446            weight,
447            Some(weight_combo_fn),
448        )
449        .map_err(ContractSimpleError::MergeError)
450    }
451}
452
453fn merge_duplicates<K, V, F, E>(xs: Vec<(K, V)>, mut merge_fn: F) -> Result<Vec<(K, V)>, E>
454where
455    K: Hash + Eq,
456    F: FnMut(&V, &V) -> Result<V, E>,
457{
458    let mut kvs = DictMap::with_capacity(xs.len());
459    for (k, v) in xs {
460        match kvs.entry(k) {
461            Entry::Occupied(entry) => {
462                *entry.into_mut() = merge_fn(&v, entry.get())?;
463            }
464            Entry::Vacant(entry) => {
465                entry.insert(v);
466            }
467        }
468    }
469    Ok(kvs.into_iter().collect::<Vec<_>>())
470}
471
472fn contract_stable<G, F, E: Error>(
473    graph: &mut G,
474    mut nodes: IndexSet<G::NodeId, foldhash::fast::RandomState>,
475    weight: G::NodeWeight,
476    weight_combo_fn: Option<F>,
477) -> Result<G::NodeId, E>
478where
479    G: GraphProp + NodeRemovable + Build + Visitable,
480    for<'b> &'b G:
481        GraphBase<NodeId = G::NodeId> + Data<EdgeWeight = G::EdgeWeight> + IntoEdgesDirected,
482    G::NodeId: Ord + Hash,
483    G::EdgeWeight: Clone,
484    F: FnMut(&G::EdgeWeight, &G::EdgeWeight) -> Result<G::EdgeWeight, E>,
485{
486    let node_index = graph.add_node(weight);
487
488    // Sanitize new node index from user input.
489    nodes.swap_remove(&node_index);
490
491    // Connect old node edges to the replacement.
492    add_edges(graph, node_index, &nodes, weight_combo_fn).unwrap();
493
494    // Remove nodes that have been replaced.
495    for index in nodes {
496        graph.remove_node(index);
497    }
498
499    Ok(node_index)
500}
501/// Check if a set of nodes in a directed graph can be contracted without introducing a cycle.
502///
503/// This function determines whether contracting the given set of nodes into a single node
504/// would introduce a cycle in the graph. It is typically used to check the feasibility of the contraction before performing
505/// the actual operation.
506///
507/// # Arguments
508///
509/// * `graph` - The graph to check.
510/// * `nodes` - A set of node indices to be contracted.
511///
512/// A bool whether the graph can be contracted based on the given nodes is returned.
513///
514/// # Example
515///
516/// ```rust
517/// use petgraph::stable_graph::StableDiGraph;
518/// use indexmap::IndexSet;
519/// use foldhash::fast::RandomState;
520/// use rustworkx_core::graph_ext::contraction::can_contract;
521///
522/// // Create a simple DAG: a -> b -> c
523/// let mut graph = StableDiGraph::<&str, ()>::default();
524/// let a = graph.add_node("a");
525/// let b = graph.add_node("b");
526/// let c = graph.add_node("c");
527/// graph.add_edge(a, b, ());
528/// graph.add_edge(b, c, ());
529///
530/// // Try to contract nodes b and c
531/// let mut nodes = IndexSet::with_hasher(RandomState::default());
532/// nodes.insert(b);
533/// nodes.insert(c);
534///
535/// let can_contract = can_contract(&graph, &nodes);
536/// assert!(can_contract); // true: contracting b and c does not introduce a cycle
537/// ```
538pub fn can_contract<G>(graph: G, nodes: &IndexSet<G::NodeId, foldhash::fast::RandomState>) -> bool
539where
540    G: Data + Visitable + IntoEdgesDirected,
541    G::NodeId: Eq + Hash,
542{
543    // Start with successors of `nodes` that aren't in `nodes` itself.
544    let visit_next: Vec<G::NodeId> = nodes
545        .iter()
546        .flat_map(|n| graph.edges(*n))
547        .filter_map(|edge| {
548            let target_node = edge.target();
549            if !nodes.contains(&target_node) {
550                Some(target_node)
551            } else {
552                None
553            }
554        })
555        .collect();
556
557    // Now, if we can reach any of `nodes`, there exists a path from `nodes`
558    // back to `nodes` of length > 1, meaning contraction is disallowed.
559    let mut dfs = Dfs::from_parts(visit_next, graph.visit_map());
560    while let Some(node) = dfs.next(graph) {
561        if nodes.contains(&node) {
562            // we found a path back to `nodes`
563            return false;
564        }
565    }
566    true
567}
568
569// Helper type for specifying `NoCallback::None` at callsites of `contract`.
570type NoCallback<E> = Option<fn(&E, &E) -> Result<E, Infallible>>;
571
572fn add_edges<G, F, E>(
573    graph: &mut G,
574    new_node: G::NodeId,
575    nodes: &IndexSet<G::NodeId, foldhash::fast::RandomState>,
576    mut weight_combo_fn: Option<F>,
577) -> Result<(), E>
578where
579    G: GraphProp + Build + Visitable,
580    for<'b> &'b G:
581        GraphBase<NodeId = G::NodeId> + Data<EdgeWeight = G::EdgeWeight> + IntoEdgesDirected,
582    G::NodeId: Ord + Hash,
583    G::EdgeWeight: Clone,
584    F: FnMut(&G::EdgeWeight, &G::EdgeWeight) -> Result<G::EdgeWeight, E>,
585{
586    // Determine and add edges for new node.
587    {
588        // Note: even when the graph is undirected, we used edges_directed because
589        // it gives us a consistent endpoint order.
590        let mut incoming_edges: Vec<(G::NodeId, G::EdgeWeight)> = nodes
591            .iter()
592            .flat_map(|i| graph.edges_directed(*i, Direction::Incoming))
593            .filter_map(|edge| {
594                let pred = edge.source();
595                (!nodes.contains(&pred)).then_some((pred, edge.weight().clone()))
596            })
597            .collect();
598
599        if let Some(merge_fn) = &mut weight_combo_fn {
600            incoming_edges = merge_duplicates(incoming_edges, merge_fn)?;
601        }
602
603        for (source, weight) in incoming_edges.into_iter() {
604            graph.add_edge(source, new_node, weight);
605        }
606    }
607
608    if graph.is_directed() {
609        let mut outgoing_edges: Vec<(G::NodeId, G::EdgeWeight)> = nodes
610            .iter()
611            .flat_map(|&i| graph.edges_directed(i, Direction::Outgoing))
612            .filter_map(|edge| {
613                let succ = edge.target();
614                (!nodes.contains(&succ)).then_some((succ, edge.weight().clone()))
615            })
616            .collect();
617
618        if let Some(merge_fn) = &mut weight_combo_fn {
619            outgoing_edges = merge_duplicates(outgoing_edges, merge_fn)?;
620        }
621
622        for (target, weight) in outgoing_edges.into_iter() {
623            graph.add_edge(new_node, target, weight);
624        }
625    }
626
627    Ok(())
628}
rustworkx_core/graph_ext/contraction.rs

rustworkx_core/graph_ext/
contraction.rs
