Trait ContractNodesDirected

pub trait ContractNodesDirected: Data {
    type Error: Error;

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

Required Associated Types

type Error: Error

The error type returned by contraction.

Required Methods

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

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

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

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

impl<N, E, Ix> ContractNodesDirected for StableGraph<N, E, Directed, Ix>

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

Implementors