Struct coupe::FiducciaMattheyses

pub struct FiducciaMattheyses {
    pub max_passes: Option<usize>,
    pub max_moves_per_pass: Option<usize>,
    pub max_imbalance: Option<f64>,
    pub max_bad_move_in_a_row: usize,
}

FiducciaMattheyses

An implementation of the original Fiduccia Mattheyses topologic algorithm for graph partitioning.

This algorithm repeats an iterative pass during which a set of graph vertices are assigned to a new part, reducing the overall cutsize of the partition. As opposed to the Kernighan-Lin algorithm, during each pass iteration, only one vertex is moved at a time. The algorithm thus does not preserve partition weights balance and may produce an unbalanced partition.

For partitioning in more than two parts, see ArcSwap.

Example

use coupe::Partition as _;
use coupe::Point2D;

//    swap
// 0  1  0  1
// +--+--+--+
// |  |  |  |
// +--+--+--+
// 0  0  1  1
let points = [
    Point2D::new(0., 0.),
    Point2D::new(1., 0.),
    Point2D::new(2., 0.),
    Point2D::new(3., 0.),
    Point2D::new(0., 1.),
    Point2D::new(1., 1.),
    Point2D::new(2., 1.),
    Point2D::new(3., 1.),
];
let weights = [1.0; 8];
let mut partition = [0, 0, 1, 1, 0, 1, 0, 1];

let mut adjacency = sprs::CsMat::empty(sprs::CSR, 0);
adjacency.insert(0, 1, 1);
adjacency.insert(1, 2, 1);
adjacency.insert(2, 3, 1);
adjacency.insert(4, 5, 1);
adjacency.insert(5, 6, 1);
adjacency.insert(6, 7, 1);
adjacency.insert(0, 4, 1);
adjacency.insert(1, 5, 1);
adjacency.insert(2, 6, 1);
adjacency.insert(3, 7, 1);

// symmetry
adjacency.insert(1, 0, 1);
adjacency.insert(2, 1, 1);
adjacency.insert(3, 2, 1);
adjacency.insert(5, 4, 1);
adjacency.insert(6, 5, 1);
adjacency.insert(7, 6, 1);
adjacency.insert(4, 0, 1);
adjacency.insert(5, 1, 1);
adjacency.insert(6, 2, 1);
adjacency.insert(7, 3, 1);

// Set the imbalance tolerance to 25% to provide enough room for FM to do
// the swap.
coupe::FiducciaMattheyses { max_imbalance: Some(0.25), ..Default::default() }
    .partition(&mut partition, (adjacency.view(), &weights))?;

assert_eq!(partition, [0, 0, 1, 1, 0, 0, 1, 1]);

Reference

Fiduccia, C. M., Mattheyses, R. M. (1982). A linear-time heuristic for improving network partitions. DAC’82: Proceeding of the 19th Design Automation Conference.

Fields

max_passes: Option<usize>

If Some(max) then the algorithm will not do more than max passes. If None then it will stop on the first non-fruitful pass.

max_moves_per_pass: Option<usize>

If Some(max) then the algorithm will not do more than max moves per pass. If None then passes will stop when no more vertices yield a positive gain, and no more bad moves can be made.

max_imbalance: Option<f64>

If Some(max) then the algorithm will not move vertices in ways that the imbalance goes over max. If None, then it will default to the imbalance of the input partition.

max_bad_move_in_a_row: usize

How many moves that yield negative gains can be made before a pass ends.

Trait Implementations

impl Clone for FiducciaMattheyses

fn clone(&self) -> FiducciaMattheyses

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for FiducciaMattheyses

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

Formats the value using the given formatter.

impl Default for FiducciaMattheyses

fn default() -> FiducciaMattheyses

Returns the “default value” for a type.

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

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 FiducciaMattheyses