14562829866

Committed 20 Apr 2025 07:57PM UTC coverage: 95.372%. Remained the same

Build # 14562829866

Build Type

Pull #1433

github

Committed by

web-flow

Commit Message

Merge e300ab93f into 487c1f618

Pull Request Pull Request #1433: Update cibuildwheel to 2.23.2 in order to unblock i686 builds

Run Details

18651 of 19556 relevant lines covered (95.37%)

1089010.65 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

74.89

/rustworkx-core/src/graph_ext/contraction.rs

// Licensed under the Apache License, Version 2.0 (the "License"); you may
// not use this file except in compliance with the License. You may obtain
// a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations
// under the License.

//! This module defines graph traits for node contraction.

use crate::dictmap::{DictMap, InitWithHasher};
use crate::err::{ContractError, ContractSimpleError};
use crate::graph_ext::NodeRemovable;
use indexmap::map::Entry;
use indexmap::IndexSet;
use petgraph::data::Build;
use petgraph::graphmap;
use petgraph::stable_graph;
use petgraph::visit::{Data, Dfs, EdgeRef, GraphBase, GraphProp, IntoEdgesDirected, Visitable};
use petgraph::{Directed, Direction, Undirected};
use std::convert::Infallible;
use std::error::Error;
use std::hash::Hash;
use std::ops::Deref;

pub trait ContractNodesDirected: Data {
    /// The error type returned by contraction.
    type Error: Error;

    /// Substitute a set of nodes with a single new node.
    ///
    /// The specified `nodes` are removed and replaced with a new node
    /// with the given `weight`. Any nodes not in the graph are ignored.
    /// It is valid for `nodes` to be empty, in which case the new node
    /// is added to the graph without edges.
    ///
    /// The contraction may result in multiple edges between nodes if
    /// the underlying graph is a multi-graph. If this is not desired,
    /// use [ContractNodesSimpleDirected::contract_nodes_simple].
    ///
    /// If `check_cycle` is enabled and the contraction would introduce
    /// a cycle, an error is returned and the graph is not modified.
    ///
    /// The `NodeId` of the newly created node is returned.
    ///
    /// # Example
    /// ```
    /// use std::convert::Infallible;
    /// use petgraph::prelude::*;
    /// use rustworkx_core::graph_ext::*;
    ///
    /// // Performs the following transformation:
    /// //      ┌─┐
    /// //      │a│
    /// //      └┬┘              ┌─┐
    /// //       0               │a│
    /// //      ┌▼┐              └┬┘
    /// //      │b│               0
    /// //      └┬┘              ┌▼┐
    /// //       1      ───►     │m│
    /// //      ┌▼┐              └┬┘
    /// //      │c│               2
    /// //      └┬┘              ┌▼┐
    /// //       2               │d│
    /// //      ┌▼┐              └─┘
    /// //      │d│
    /// //      └─┘
    /// let mut dag: StableDiGraph<char, usize> = StableDiGraph::default();
    /// let a = dag.add_node('a');
    /// let b = dag.add_node('b');
    /// let c = dag.add_node('c');
    /// let d = dag.add_node('d');
    /// dag.add_edge(a.clone(), b.clone(), 0);
    /// dag.add_edge(b.clone(), c.clone(), 1);
    /// dag.add_edge(c.clone(), d.clone(), 2);
    ///
    /// let m = dag.contract_nodes([b, c], 'm', true).unwrap();
    /// assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &0);
    /// assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &2);
    /// ```
    fn contract_nodes<I>(
        &mut self,
        nodes: I,
        weight: Self::NodeWeight,
        check_cycle: bool,
    ) -> Result<Self::NodeId, Self::Error>
    where
        I: IntoIterator<Item = Self::NodeId>;
}

impl<N, E, Ix> ContractNodesDirected for stable_graph::StableGraph<N, E, Directed, Ix>
where
    Ix: stable_graph::IndexType,
    E: Clone,
{
    type Error = ContractError;

    fn contract_nodes<I>(
        &mut self,
        nodes: I,
        obj: Self::NodeWeight,
        check_cycle: bool,
    ) -> Result<Self::NodeId, Self::Error>
    where
        I: IntoIterator<Item = Self::NodeId>,
    {
        let nodes = IndexSet::from_iter(nodes);
        if check_cycle && !can_contract(self.deref(), &nodes) {
            return Err(ContractError::DAGWouldCycle);
        }
        Ok(contract_stable(self, nodes, obj, NoCallback::None).unwrap())
    }
}

impl<N, E> ContractNodesDirected for graphmap::GraphMap<N, E, Directed>
where
    for<'a> N: graphmap::NodeTrait + 'a,
    for<'a> E: Clone + 'a,
{
    type Error = ContractError;

    fn contract_nodes<I>(
        &mut self,
        nodes: I,
        obj: Self::NodeWeight,
        check_cycle: bool,
    ) -> Result<Self::NodeId, Self::Error>
    where
        I: IntoIterator<Item = Self::NodeId>,
    {
        let nodes = IndexSet::from_iter(nodes);
        if check_cycle && !can_contract(self.deref(), &nodes) {
            return Err(ContractError::DAGWouldCycle);
        }
        Ok(contract_stable(self, nodes, obj, NoCallback::None).unwrap())
    }
}

pub trait ContractNodesSimpleDirected: Data {
    /// The error type returned by contraction.
    type Error<Ex: Error>: Error;

    /// Substitute a set of nodes with a single new node.
    ///
    /// The specified `nodes` are removed and replaced with a new node
    /// with the given `weight`. Any nodes not in the graph are ignored.
    /// It is valid for `nodes` to be empty, in which case the new node
    /// is added to the graph without edges.
    ///
    /// The specified function `weight_combo_fn` is used to merge
    /// would-be parallel edges during contraction; this function
    /// preserves simple graphs.
    ///
    /// If `check_cycle` is enabled and the contraction would introduce
    /// a cycle, an error is returned and the graph is not modified.
    ///
    /// The `NodeId` of the newly created node is returned.
    ///
    /// # Example
    /// ```
    /// use std::convert::Infallible;
    /// use petgraph::prelude::*;
    /// use rustworkx_core::graph_ext::*;
    ///
    /// // Performs the following transformation:
    /// //                          ┌─┐
    /// //     ┌─┐                  │a│
    /// //  ┌0─┤a├─1┐               └┬┘
    /// //  │  └─┘  │                1
    /// // ┌▼┐     ┌▼┐              ┌▼┐
    /// // │b│     │c│     ───►     │m│
    /// // └┬┘     └┬┘              └┬┘
    /// //  │  ┌─┐  │                3
    /// //  └2►│d│◄3┘               ┌▼┐
    /// //     └─┘                  │d│
    /// //                          └─┘
    /// let mut dag: StableDiGraph<char, usize> = StableDiGraph::default();
    /// let a = dag.add_node('a');
    /// let b = dag.add_node('b');
    /// let c = dag.add_node('c');
    /// let d = dag.add_node('d');
    /// dag.add_edge(a.clone(), b.clone(), 0);
    /// dag.add_edge(a.clone(), c.clone(), 1);
    /// dag.add_edge(b.clone(), d.clone(), 2);
    /// dag.add_edge(c.clone(), d.clone(), 3);
    ///
    /// let m = dag.contract_nodes_simple([b, c], 'm', true, |&e1, &e2| Ok::<_, Infallible>(if e1 > e2 { e1 } else { e2 } )).unwrap();
    /// assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &1);
    /// assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &3);
    /// ```
    fn contract_nodes_simple<I, F, C: Error>(
        &mut self,
        nodes: I,
        weight: Self::NodeWeight,
        check_cycle: bool,
        weight_combo_fn: F,
    ) -> Result<Self::NodeId, Self::Error<C>>
    where
        I: IntoIterator<Item = Self::NodeId>,
        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>;
}

impl<N, E, Ix> ContractNodesSimpleDirected for stable_graph::StableGraph<N, E, Directed, Ix>
where
    Ix: stable_graph::IndexType,
    E: Clone,
{
    type Error<Err: Error> = ContractSimpleError<Err>;

    fn contract_nodes_simple<I, F, C: Error>(
        &mut self,
        nodes: I,
        weight: Self::NodeWeight,
        check_cycle: bool,
        weight_combo_fn: F,
    ) -> Result<Self::NodeId, Self::Error<C>>
    where
        I: IntoIterator<Item = Self::NodeId>,
        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,
    {
        let nodes = IndexSet::from_iter(nodes);
        if check_cycle && !can_contract(self.deref(), &nodes) {
            return Err(ContractSimpleError::DAGWouldCycle);
        }
        contract_stable(self, nodes, weight, Some(weight_combo_fn))
            .map_err(ContractSimpleError::MergeError)
    }
}

impl<N, E> ContractNodesSimpleDirected for graphmap::GraphMap<N, E, Directed>
where
    for<'a> N: graphmap::NodeTrait + 'a,
    for<'a> E: Clone + 'a,
{
    type Error<Err: Error> = ContractSimpleError<Err>;

    fn contract_nodes_simple<I, F, C: Error>(
        &mut self,
        nodes: I,
        weight: Self::NodeWeight,
        check_cycle: bool,
        weight_combo_fn: F,
    ) -> Result<Self::NodeId, Self::Error<C>>
    where
        I: IntoIterator<Item = Self::NodeId>,
        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,
    {
        let nodes = IndexSet::from_iter(nodes);
        if check_cycle && !can_contract(self.deref(), &nodes) {
            return Err(ContractSimpleError::DAGWouldCycle);
        }
        contract_stable(self, nodes, weight, Some(weight_combo_fn))
            .map_err(ContractSimpleError::MergeError)
    }
}

pub trait ContractNodesUndirected: Data {
    /// Substitute a set of nodes with a single new node.
    ///
    /// The specified `nodes` are removed and replaced with a new node
    /// with the given `weight`. Any nodes not in the graph are ignored.
    /// It is valid for `nodes` to be empty, in which case the new node
    /// is added to the graph without edges.
    ///
    /// The contraction may result in multiple edges between nodes if
    /// the underlying graph is a multi-graph. If this is not desired,
    /// use [ContractNodesSimpleUndirected::contract_nodes_simple].
    ///
    /// The `NodeId` of the newly created node is returned.
    ///
    /// # Example
    /// ```
    /// use petgraph::prelude::*;
    /// use rustworkx_core::graph_ext::*;
    ///
    /// // Performs the following transformation:
    /// //      ┌─┐
    /// //      │a│
    /// //      └┬┘              ┌─┐
    /// //       0               │a│
    /// //      ┌┴┐              └┬┘
    /// //      │b│               0
    /// //      └┬┘              ┌┴┐
    /// //       1      ───►     │m│
    /// //      ┌┴┐              └┬┘
    /// //      │c│               2
    /// //      └┬┘              ┌┴┐
    /// //       2               │d│
    /// //      ┌┴┐              └─┘
    /// //      │d│
    /// //      └─┘
    /// let mut dag: StableUnGraph<char, usize> = StableUnGraph::default();
    /// let a = dag.add_node('a');
    /// let b = dag.add_node('b');
    /// let c = dag.add_node('c');
    /// let d = dag.add_node('d');
    /// dag.add_edge(a.clone(), b.clone(), 0);
    /// dag.add_edge(b.clone(), c.clone(), 1);
    /// dag.add_edge(c.clone(), d.clone(), 2);
    ///
    /// let m = dag.contract_nodes([b, c], 'm');
    /// assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &0);
    /// assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &2);
    /// ```
    fn contract_nodes<I>(&mut self, nodes: I, weight: Self::NodeWeight) -> Self::NodeId
    where
        I: IntoIterator<Item = Self::NodeId>;
}

impl<N, E, Ix> ContractNodesUndirected for stable_graph::StableGraph<N, E, Undirected, Ix>
where
    Ix: stable_graph::IndexType,
    E: Clone,
{
    fn contract_nodes<I>(&mut self, nodes: I, obj: Self::NodeWeight) -> Self::NodeId
    where
        I: IntoIterator<Item = Self::NodeId>,
    {
        contract_stable(self, IndexSet::from_iter(nodes), obj, NoCallback::None).unwrap()
    }
}

impl<N, E> ContractNodesUndirected for graphmap::GraphMap<N, E, Undirected>
where
    for<'a> N: graphmap::NodeTrait + 'a,
    for<'a> E: Clone + 'a,
{
    fn contract_nodes<I>(&mut self, nodes: I, obj: Self::NodeWeight) -> Self::NodeId
    where
        I: IntoIterator<Item = Self::NodeId>,
    {
        contract_stable(self, IndexSet::from_iter(nodes), obj, NoCallback::None).unwrap()
    }
}

pub trait ContractNodesSimpleUndirected: Data {
    type Error<Ex: Error>: Error;

    /// Substitute a set of nodes with a single new node.
    ///
    /// The specified `nodes` are removed and replaced with a new node
    /// with the given `weight`. Any nodes not in the graph are ignored.
    /// It is valid for `nodes` to be empty, in which case the new node
    /// is added to the graph without edges.
    ///
    /// The specified function `weight_combo_fn` is used to merge
    /// would-be parallel edges during contraction; this function
    /// preserves simple graphs.
    ///
    /// The `NodeId` of the newly created node is returned.
    ///
    /// # Example
    /// ```
    /// use std::convert::Infallible;
    /// use petgraph::prelude::*;
    /// use rustworkx_core::graph_ext::*;
    ///
    /// // Performs the following transformation:
    /// //                          ┌─┐
    /// //     ┌─┐                  │a│
    /// //  ┌0─┤a├─1┐               └┬┘
    /// //  │  └─┘  │                1
    /// // ┌┴┐     ┌┴┐              ┌┴┐
    /// // │b│     │c│     ───►     │m│
    /// // └┬┘     └┬┘              └┬┘
    /// //  │  ┌─┐  │                3
    /// //  └2─│d├─3┘               ┌┴┐
    /// //     └─┘                  │d│
    /// //                          └─┘
    /// let mut dag: StableUnGraph<char, usize> = StableUnGraph::default();
    /// let a = dag.add_node('a');
    /// let b = dag.add_node('b');
    /// let c = dag.add_node('c');
    /// let d = dag.add_node('d');
    /// dag.add_edge(a.clone(), b.clone(), 0);
    /// dag.add_edge(a.clone(), c.clone(), 1);
    /// dag.add_edge(b.clone(), d.clone(), 2);
    /// dag.add_edge(c.clone(), d.clone(), 3);
    ///
    /// let m = dag.contract_nodes_simple([b, c], 'm', |&e1, &e2| Ok::<_, Infallible>(if e1 > e2 { e1 } else { e2 } )).unwrap();
    /// assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &1);
    /// assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &3);
    /// ```
    fn contract_nodes_simple<I, F, C: Error>(
        &mut self,
        nodes: I,
        weight: Self::NodeWeight,
        weight_combo_fn: F,
    ) -> Result<Self::NodeId, Self::Error<C>>
    where
        I: IntoIterator<Item = Self::NodeId>,
        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>;
}

impl<N, E, Ix> ContractNodesSimpleUndirected for stable_graph::StableGraph<N, E, Undirected, Ix>
where
    Ix: stable_graph::IndexType,
    E: Clone,
{
    type Error<Err: Error> = ContractSimpleError<Err>;

    fn contract_nodes_simple<I, F, C: Error>(
        &mut self,
        nodes: I,
        weight: Self::NodeWeight,
        weight_combo_fn: F,
    ) -> Result<Self::NodeId, Self::Error<C>>
    where
        I: IntoIterator<Item = Self::NodeId>,
        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,
    {
        contract_stable(
            self,
            IndexSet::from_iter(nodes),
            weight,
            Some(weight_combo_fn),
        )
        .map_err(ContractSimpleError::MergeError)
    }
}

impl<N, E> ContractNodesSimpleUndirected for graphmap::GraphMap<N, E, Undirected>
where
    for<'a> N: graphmap::NodeTrait + 'a,
    for<'a> E: Clone + 'a,
{
    type Error<Err: Error> = ContractSimpleError<Err>;

    fn contract_nodes_simple<I, F, C: Error>(
        &mut self,
        nodes: I,
        weight: Self::NodeWeight,
        weight_combo_fn: F,
    ) -> Result<Self::NodeId, Self::Error<C>>
    where
        I: IntoIterator<Item = Self::NodeId>,
        F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,
    {
        contract_stable(
            self,
            IndexSet::from_iter(nodes),
            weight,
            Some(weight_combo_fn),
        )
        .map_err(ContractSimpleError::MergeError)
    }
}

fn merge_duplicates<K, V, F, E>(xs: Vec<(K, V)>, mut merge_fn: F) -> Result<Vec<(K, V)>, E>
where
    K: Hash + Eq,
    F: FnMut(&V, &V) -> Result<V, E>,
{
    let mut kvs = DictMap::with_capacity(xs.len());
    for (k, v) in xs {
        match kvs.entry(k) {
            Entry::Occupied(entry) => {
                *entry.into_mut() = merge_fn(&v, entry.get())?;
            }
            Entry::Vacant(entry) => {
                entry.insert(v);
            }
        }
    }
    Ok(kvs.into_iter().collect::<Vec<_>>())
}

fn contract_stable<G, F, E: Error>(
    graph: &mut G,
    mut nodes: IndexSet<G::NodeId, ahash::RandomState>,
    weight: G::NodeWeight,
    weight_combo_fn: Option<F>,
) -> Result<G::NodeId, E>
where
    G: GraphProp + NodeRemovable + Build + Visitable,
    for<'b> &'b G:
        GraphBase<NodeId = G::NodeId> + Data<EdgeWeight = G::EdgeWeight> + IntoEdgesDirected,
    G::NodeId: Ord + Hash,
    G::EdgeWeight: Clone,
    F: FnMut(&G::EdgeWeight, &G::EdgeWeight) -> Result<G::EdgeWeight, E>,
{
    let node_index = graph.add_node(weight);

    // Sanitize new node index from user input.
    nodes.swap_remove(&node_index);

    // Connect old node edges to the replacement.
    add_edges(graph, node_index, &nodes, weight_combo_fn).unwrap();

    // Remove nodes that have been replaced.
    for index in nodes {
        graph.remove_node(index);
    }

    Ok(node_index)
}

fn can_contract<G>(graph: G, nodes: &IndexSet<G::NodeId, ahash::RandomState>) -> bool
where
    G: Data + Visitable + IntoEdgesDirected,
    G::NodeId: Eq + Hash,
{
    // Start with successors of `nodes` that aren't in `nodes` itself.
    let visit_next: Vec<G::NodeId> = nodes
        .iter()
        .flat_map(|n| graph.edges(*n))
        .filter_map(|edge| {
            let target_node = edge.target();
            if !nodes.contains(&target_node) {
                Some(target_node)
            } else {
                None
            }
        })
        .collect();

    // Now, if we can reach any of `nodes`, there exists a path from `nodes`
    // back to `nodes` of length > 1, meaning contraction is disallowed.
    let mut dfs = Dfs::from_parts(visit_next, graph.visit_map());
    while let Some(node) = dfs.next(graph) {
        if nodes.contains(&node) {
            // we found a path back to `nodes`
            return false;
        }
    }
    true
}

// Helper type for specifying `NoCallback::None` at callsites of `contract`.
type NoCallback<E> = Option<fn(&E, &E) -> Result<E, Infallible>>;

fn add_edges<G, F, E>(
    graph: &mut G,
    new_node: G::NodeId,
    nodes: &IndexSet<G::NodeId, ahash::RandomState>,
    mut weight_combo_fn: Option<F>,
) -> Result<(), E>
where
    G: GraphProp + Build + Visitable,
    for<'b> &'b G:
        GraphBase<NodeId = G::NodeId> + Data<EdgeWeight = G::EdgeWeight> + IntoEdgesDirected,
    G::NodeId: Ord + Hash,
    G::EdgeWeight: Clone,
    F: FnMut(&G::EdgeWeight, &G::EdgeWeight) -> Result<G::EdgeWeight, E>,
{
    // Determine and add edges for new node.
    {
        // Note: even when the graph is undirected, we used edges_directed because
        // it gives us a consistent endpoint order.
        let mut incoming_edges: Vec<(G::NodeId, G::EdgeWeight)> = nodes
            .iter()
            .flat_map(|i| graph.edges_directed(*i, Direction::Incoming))
            .filter_map(|edge| {
                let pred = edge.source();
                (!nodes.contains(&pred)).then_some((pred, edge.weight().clone()))
            })
            .collect();

        if let Some(merge_fn) = &mut weight_combo_fn {
            incoming_edges = merge_duplicates(incoming_edges, merge_fn)?;
        }

        for (source, weight) in incoming_edges.into_iter() {
            graph.add_edge(source, new_node, weight);
        }
    }

    if graph.is_directed() {
        let mut outgoing_edges: Vec<(G::NodeId, G::EdgeWeight)> = nodes
            .iter()
            .flat_map(|&i| graph.edges_directed(i, Direction::Outgoing))
            .filter_map(|edge| {
                let succ = edge.target();
                (!nodes.contains(&succ)).then_some((succ, edge.weight().clone()))
            })
            .collect();

        if let Some(merge_fn) = &mut weight_combo_fn {
            outgoing_edges = merge_duplicates(outgoing_edges, merge_fn)?;
        }

        for (target, weight) in outgoing_edges.into_iter() {
            graph.add_edge(new_node, target, weight);
        }
    }

    Ok(())
}

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
15	use crate::dictmap::{DictMap, InitWithHasher};
16	use crate::err::{ContractError, ContractSimpleError};
17	use crate::graph_ext::NodeRemovable;
18	use indexmap::map::Entry;
19	use indexmap::IndexSet;
20	use petgraph::data::Build;
21	use petgraph::graphmap;
22	use petgraph::stable_graph;
23	use petgraph::visit::{Data, Dfs, EdgeRef, GraphBase, GraphProp, IntoEdgesDirected, Visitable};
24	use petgraph::{Directed, Direction, Undirected};
25	use std::convert::Infallible;
26	use std::error::Error;
27	use std::hash::Hash;
28	use std::ops::Deref;
29
30	pub 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
95	impl<N, E, Ix> ContractNodesDirected for stable_graph::StableGraph<N, E, Directed, Ix>
96	where
97	Ix: stable_graph::IndexType,
98	E: Clone,
99	{
100	type Error = ContractError;
101
102	fn contract_nodes<I>(	26✔
103	&mut self,	26✔
104	nodes: I,	26✔
105	obj: Self::NodeWeight,	26✔
106	check_cycle: bool,	26✔
107	) -> Result<Self::NodeId, Self::Error>	26✔
108	where	26✔
109	I: IntoIterator<Item = Self::NodeId>,	26✔
110	{	26✔
111	let nodes = IndexSet::from_iter(nodes);	26✔
112	if check_cycle && !can_contract(self.deref(), &nodes) {	26✔
113	return Err(ContractError::DAGWouldCycle);	10✔
114	}	16✔
115	Ok(contract_stable(self, nodes, obj, NoCallback::None).unwrap())	16✔
116	}	26✔
117	}
118
119	impl<N, E> ContractNodesDirected for graphmap::GraphMap<N, E, Directed>
120	where
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
143	pub 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
207	impl<N, E, Ix> ContractNodesSimpleDirected for stable_graph::StableGraph<N, E, Directed, Ix>
208	where
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>(	6✔
215	&mut self,	6✔
216	nodes: I,	6✔
217	weight: Self::NodeWeight,	6✔
218	check_cycle: bool,	6✔
219	weight_combo_fn: F,	6✔
220	) -> Result<Self::NodeId, Self::Error<C>>	6✔
221	where	6✔
222	I: IntoIterator<Item = Self::NodeId>,	6✔
223	F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,	6✔
224	{	6✔
225	let nodes = IndexSet::from_iter(nodes);	6✔
226	if check_cycle && !can_contract(self.deref(), &nodes) {	6✔
227	return Err(ContractSimpleError::DAGWouldCycle);	×
228	}	6✔
229	contract_stable(self, nodes, weight, Some(weight_combo_fn))	6✔
230	.map_err(ContractSimpleError::MergeError)	6✔
231	}	6✔
232	}
233
234	impl<N, E> ContractNodesSimpleDirected for graphmap::GraphMap<N, E, Directed>
235	where
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
261	pub 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
314	impl<N, E, Ix> ContractNodesUndirected for stable_graph::StableGraph<N, E, Undirected, Ix>
315	where
316	Ix: stable_graph::IndexType,
317	E: Clone,
318	{
319	fn contract_nodes<I>(&mut self, nodes: I, obj: Self::NodeWeight) -> Self::NodeId	12✔
320	where	12✔
321	I: IntoIterator<Item = Self::NodeId>,	12✔
322	{	12✔
323	contract_stable(self, IndexSet::from_iter(nodes), obj, NoCallback::None).unwrap()	12✔
324	}	12✔
325	}
326
327	impl<N, E> ContractNodesUndirected for graphmap::GraphMap<N, E, Undirected>
328	where
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
340	pub 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
399	impl<N, E, Ix> ContractNodesSimpleUndirected for stable_graph::StableGraph<N, E, Undirected, Ix>
400	where
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>(	6✔
407	&mut self,	6✔
408	nodes: I,	6✔
409	weight: Self::NodeWeight,	6✔
410	weight_combo_fn: F,	6✔
411	) -> Result<Self::NodeId, Self::Error<C>>	6✔
412	where	6✔
413	I: IntoIterator<Item = Self::NodeId>,	6✔
414	F: FnMut(&Self::EdgeWeight, &Self::EdgeWeight) -> Result<Self::EdgeWeight, C>,	6✔
415	{	6✔
416	contract_stable(	6✔
417	self,	6✔
418	IndexSet::from_iter(nodes),	6✔
419	weight,	6✔
420	Some(weight_combo_fn),	6✔
421	)	6✔
422	.map_err(ContractSimpleError::MergeError)	6✔
423	}	6✔
424	}
425
426	impl<N, E> ContractNodesSimpleUndirected for graphmap::GraphMap<N, E, Undirected>
427	where
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
453	fn merge_duplicates<K, V, F, E>(xs: Vec<(K, V)>, mut merge_fn: F) -> Result<Vec<(K, V)>, E>	18✔
454	where	18✔
455	K: Hash + Eq,	18✔
456	F: FnMut(&V, &V) -> Result<V, E>,	18✔
457	{	18✔
458	let mut kvs = DictMap::with_capacity(xs.len());	18✔
459	for (k, v) in xs {	66✔
460	match kvs.entry(k) {	48✔
461	Entry::Occupied(entry) => {	32✔
462	*entry.into_mut() = merge_fn(&v, entry.get())?;	32✔
463	}
464	Entry::Vacant(entry) => {	16✔
465	entry.insert(v);	16✔
466	}	16✔
467	}
468	}
469	Ok(kvs.into_iter().collect::<Vec<_>>())	18✔
470	}	18✔
471
472	fn contract_stable<G, F, E: Error>(	40✔
473	graph: &mut G,	40✔
474	mut nodes: IndexSet<G::NodeId, ahash::RandomState>,	40✔
475	weight: G::NodeWeight,	40✔
476	weight_combo_fn: Option<F>,	40✔
477	) -> Result<G::NodeId, E>	40✔
478	where	40✔
479	G: GraphProp + NodeRemovable + Build + Visitable,	40✔
480	for<'b> &'b G:	40✔
481	GraphBase<NodeId = G::NodeId> + Data<EdgeWeight = G::EdgeWeight> + IntoEdgesDirected,	40✔
482	G::NodeId: Ord + Hash,	40✔
483	G::EdgeWeight: Clone,	40✔
484	F: FnMut(&G::EdgeWeight, &G::EdgeWeight) -> Result<G::EdgeWeight, E>,	40✔
485	{	40✔
486	let node_index = graph.add_node(weight);	40✔
487		40✔
488	// Sanitize new node index from user input.	40✔
489	nodes.swap_remove(&node_index);	40✔
490		40✔
491	// Connect old node edges to the replacement.	40✔
492	add_edges(graph, node_index, &nodes, weight_combo_fn).unwrap();	40✔
493
494	// Remove nodes that have been replaced.
495	for index in nodes {	132✔
496	graph.remove_node(index);	92✔
497	}	92✔
498
499	Ok(node_index)	40✔
500	}	40✔
501
502	fn can_contract<G>(graph: G, nodes: &IndexSet<G::NodeId, ahash::RandomState>) -> bool	12✔
503	where	12✔
504	G: Data + Visitable + IntoEdgesDirected,	12✔
505	G::NodeId: Eq + Hash,	12✔
506	{	12✔
507	// Start with successors of `nodes` that aren't in `nodes` itself.	12✔
508	let visit_next: Vec<G::NodeId> = nodes	12✔
509	.iter()	12✔
510	.flat_map(\|n\| graph.edges(*n))	24✔
511	.filter_map(\|edge\| {	12✔
512	let target_node = edge.target();	12✔
513	if !nodes.contains(&target_node) {	12✔
514	Some(target_node)	10✔
515	} else {
516	None	2✔
517	}
518	})	12✔
519	.collect();	12✔
520		12✔
521	// Now, if we can reach any of `nodes`, there exists a path from `nodes`	12✔
522	// back to `nodes` of length > 1, meaning contraction is disallowed.	12✔
523	let mut dfs = Dfs::from_parts(visit_next, graph.visit_map());	12✔
524	while let Some(node) = dfs.next(graph) {	26✔
525	if nodes.contains(&node) {	24✔
526	// we found a path back to `nodes`
527	return false;	10✔
528	}	14✔
529	}
530	true	2✔
531	}	12✔
532
533	// Helper type for specifying `NoCallback::None` at callsites of `contract`.
534	type NoCallback<E> = Option<fn(&E, &E) -> Result<E, Infallible>>;
535
536	fn add_edges<G, F, E>(	40✔
537	graph: &mut G,	40✔
538	new_node: G::NodeId,	40✔
539	nodes: &IndexSet<G::NodeId, ahash::RandomState>,	40✔
540	mut weight_combo_fn: Option<F>,	40✔
541	) -> Result<(), E>	40✔
542	where	40✔
543	G: GraphProp + Build + Visitable,	40✔
544	for<'b> &'b G:	40✔
545	GraphBase<NodeId = G::NodeId> + Data<EdgeWeight = G::EdgeWeight> + IntoEdgesDirected,	40✔
546	G::NodeId: Ord + Hash,	40✔
547	G::EdgeWeight: Clone,	40✔
548	F: FnMut(&G::EdgeWeight, &G::EdgeWeight) -> Result<G::EdgeWeight, E>,	40✔
549	{	40✔
550	// Determine and add edges for new node.	40✔
551	{	40✔
552	// Note: even when the graph is undirected, we used edges_directed because	40✔
553	// it gives us a consistent endpoint order.	40✔
554	let mut incoming_edges: Vec<(G::NodeId, G::EdgeWeight)> = nodes	40✔
555	.iter()	40✔
556	.flat_map(\|i\| graph.edges_directed(*i, Direction::Incoming))	92✔
557	.filter_map(\|edge\| {	104✔
558	let pred = edge.source();	104✔
559	(!nodes.contains(&pred)).then_some((pred, edge.weight().clone()))	104✔
560	})	104✔
561	.collect();	40✔
562
563	if let Some(merge_fn) = &mut weight_combo_fn {	40✔
564	incoming_edges = merge_duplicates(incoming_edges, merge_fn)?;	12✔
565	}	28✔
566
567	for (source, weight) in incoming_edges.into_iter() {	40✔
568	graph.add_edge(source, new_node, weight);	38✔
569	}	38✔
570	}
571
572	if graph.is_directed() {	40✔
573	let mut outgoing_edges: Vec<(G::NodeId, G::EdgeWeight)> = nodes	22✔
574	.iter()	22✔
575	.flat_map(\|&i\| graph.edges_directed(i, Direction::Outgoing))	50✔
576	.filter_map(\|edge\| {	36✔
577	let succ = edge.target();	36✔
578	(!nodes.contains(&succ)).then_some((succ, edge.weight().clone()))	36✔
579	})	36✔
580	.collect();	22✔
581
582	if let Some(merge_fn) = &mut weight_combo_fn {	22✔
583	outgoing_edges = merge_duplicates(outgoing_edges, merge_fn)?;	6✔
584	}	16✔
585
586	for (target, weight) in outgoing_edges.into_iter() {	22✔
587	graph.add_edge(new_node, target, weight);	14✔
588	}	14✔
589	}	18✔
590
591	Ok(())	40✔
592	}	40✔

Qiskit / rustworkx / 14562829866

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous