Trait ContractNodesSimpleDirected

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

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

Required Associated Types

type Error<Ex: Error>: Error

The error type returned by contraction.

Required Methods

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

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

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> ContractNodesSimpleDirected for GraphMap<N, E, Directed>

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, 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 StableGraph<N, E, Directed, 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, 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>,

Implementors