Trait ContractNodesSimpleUndirected

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

    // Required method
    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>;
}

Required Associated Types

type Error<Ex: Error>: Error

Required Methods

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>,

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);

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types

impl<N, E> ContractNodesSimpleUndirected for GraphMap<N, E, Undirected>

where for<'a> N: 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>,

impl<N, E, Ix> ContractNodesSimpleUndirected for StableGraph<N, E, Undirected, Ix>

where Ix: 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>,

Implementors