Struct coupe::ArcSwap

pub struct ArcSwap {
    pub max_imbalance: Option<f64>,
}

Arc-swap

A multi-threaded variant of Fiduccia-Mattheyses, which moves vertices from one part to the other as long as the move reduces the cutset.

In contrast to the original algorithm, it is not greedy and thus does more, smaller moves. It also does not need to build up a gain table, which greatly speeds up the execution time.

Example

use coupe::Partition as _;
use coupe::Grid;

//    swap
// 0  1  0  1
// +--+--+--+
// |  |  |  |
// +--+--+--+
// 0  0  1  1

let width = std::num::NonZeroUsize::new(4).unwrap();
let height = std::num::NonZeroUsize::new(2).unwrap();
let grid = Grid::new_2d(width, height);

let weights = [1.0; 8];
let mut partition = [0, 0, 1, 1, 0, 1, 0, 1];

coupe::ArcSwap { max_imbalance: Some(0.25) }
    .partition(&mut partition, (grid, &weights))?;

Fields

max_imbalance: Option<f64>

Restrict moves made by ArcSwap such that the imbalance of the output partition is smaller than this value.

• if Some(value), ArcSwap reduces the edge cut as much as possible while keeping imbalance below value.
• if None, ArcSwap does not increase the imbalance of the input partition (same behavior as Some(imbalance(input_partition))).

Trait Implementations

impl Clone for ArcSwap

fn clone(&self) -> ArcSwap

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ArcSwap

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for ArcSwap

fn default() -> ArcSwap

Returns the “default value” for a type.

impl<'a, T, W> Partition<(T, &'a [W])> for ArcSwapwhere W: AsWeight, T: Topology<i64> + Sync,

type Metadata = Metadata

Diagnostic data returned for a specific run of the algorithm.

type Error = Error

Error details, should the algorithm fail to run.

fn partition( &mut self, part_ids: &mut [usize], (adjacency, weights): (T, &'a [W]) ) -> Result<Self::Metadata, Self::Error>

Partition the given data and output the part ID of each element in part_ids.

impl Copy for ArcSwap