Struct metis::Graph

source ·

pub struct Graph<'a> { /* private fields */ }

Expand description

Builder structure to set up a graph partition computation.

This structure holds the required arguments for METIS to compute a partition. It also offers methods to easily set any optional argument.

Example

// Make a graph with two vertices and an edge between the two.
let xadj = &mut [0, 1, 2];
let adjncy = &mut [1, 0];

// Allocate the partition array which stores the partition of each vertex.
let mut part = [0, 0];

// There are one constraint and two parts.  The partitioning algorithm used
// is recursive bisection.  The k-way algorithm can also be used.
Graph::new(1, 2, xadj, adjncy)?
    .part_recursive(&mut part)?;

// The two vertices are placed in different parts.
assert_ne!(part[0], part[1]);

Implementations§

source §

impl<'a> Graph<'a>

source

pub fn new( ncon: Idx, nparts: Idx, xadj: &'a [Idx], adjncy: &'a [Idx] ) -> StdResult<Graph<'a>, NewGraphError>

Creates a new Graph object to be partitioned.

ncon is the number of constraints on each vertex (at least 1),
nparts is the number of parts wanted in the graph partition.

CSR (Compressed Sparse Row) is a data structure for representing sparse matrices and is the primary data structure used by METIS. A CSR formatted graph is represented with two slices: an adjacency list (adjcny) and an index list (xadj). The nodes adjacent to node n are adjncy[xadj[n]..xadj[n + 1]]. Additionally, metis requires that graphs are undirected: if (u, v) is in the graph, then (v, u) must also be in the graph.

Consider translating this simple graph to CSR format:

// 5 - 3 - 4 - 0
//     |   | /
//     2 - 1
let adjncy = [1, 4, 0, 2, 4, 1, 3, 2, 4, 5, 0, 1, 3, 3];
let xadj = [0, 2, 5, 7, 10, 13, 14];

// iterate over adjacent nodes
let mut it = xadj
    .windows(2)
    .map(|x| &adjncy[x[0]..x[1]]);

// node 0 is adjacent to nodes 1 and 4
assert_eq!(it.next().unwrap(), &[1, 4]);

// node 1 is adjacent to nodes 0, 2, and 4
assert_eq!(it.next().unwrap(), &[0, 2, 4]);

// node 2 is adjacent to nodes 1 and 3
assert_eq!(it.next().unwrap(), &[1, 3]);

// node 3 is adjacent to nodes 2, 4, and 5
assert_eq!(it.next().unwrap(), &[2, 4, 5]);

// node 4 is adjacent to nodes 0, 1, and 3
assert_eq!(it.next().unwrap(), &[0, 1, 3]);

// node 5 is adjacent to node 3
assert_eq!(it.next().unwrap(), &[3]);

assert!(it.next().is_none());

More info can be found at: https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)

Errors

The following invariants must be held, otherwise this function returns an error:

all the arrays have a length that can be held by an Idx,
ncon is strictly greater than zero,
nparts is strictly greater than zero,
xadj has at least one element (its length is the one more than the number of vertices),
xadj is sorted,
elements of xadj are positive,
the last element of xadj is the length of adjncy,
elements of adjncy are within zero and the number of vertices.

Mutability

Graph::part_kway and Graph::part_recursive may mutate the contents of xadj and adjncy, but should revert all changes before returning.

source

pub unsafe fn new_unchecked( ncon: Idx, nparts: Idx, xadj: &'a [Idx], adjncy: &'a [Idx] ) -> Graph<'a>

Creates a new Graph object to be partitioned (unchecked version).

ncon is the number of constraints on each vertex (at least 1),
nparts is the number of parts wanted in the graph partition.

Input format

xadj and adjncy are the CSR encoding of the adjacency matrix that represents the graph. xadj is the row index and adjncy is the column index.

Safety

This function still does some checks listed in “Panics” below. However, the caller is reponsible for upholding all invariants listed in the “Errors” section of Graph::new. Otherwise, the behavior of this function is undefined.

Panics

This function panics if:

any of the arrays have a length that cannot be held by an Idx, or
ncon is not strictly greater than zero, or
nparts is not strictly greater than zero, or
xadj is empty, or
the length of adjncy is different from the last element of xadj.

Mutability

Graph::part_kway and Graph::part_recursive may mutate the contents of xadj and adjncy, but should revert all changes before returning.

source

pub fn set_vwgt(self, vwgt: &'a [Idx]) -> Graph<'a>

Sets the computational weights of the vertices.

By default, all vertices have the same weight.

The ncon weights of the ith vertex must be located in vwgt[i*ncon..(i+1)*ncon], and all elements of vwgt must be positive.

Panics

This function panics if the length of vwgt is not ncon times the number of vertices.

source

pub fn set_vsize(self, vsize: &'a [Idx]) -> Graph<'a>

Sets the communication weights of the vertices.

By default, all vertices have the same communication weight.

Vertices can only have one communication weight. The length of vsize does not depend on ncon.

Panics

This function panics if the length of vsize is not the number of vertices.

source

pub fn set_adjwgt(self, adjwgt: &'a [Idx]) -> Graph<'a>

Sets the weights of the edges.

By default, all edges have the same weight.

All elements of adjwgt must be positive.

Panics

This function panics if the length of adjwgt is not equal to the length of adjncy.

source

pub fn set_tpwgts(self, tpwgts: &'a [Real]) -> Graph<'a>

Sets the target partition weights for each part and constraint.

By default, the graph is divided equally.

The target partition weight for the ith part and jth constraint is specified at tpwgts[i*ncon+j]. For each constraint j, the sum of the target partition weights must be 1.0. Meaning (0..nparts).map(|i| tpwgts[i*ncon+j]).sum() == 1.0.

Panics

This function panics if the length of tpwgts is not equal to ncon times nparts.

source

pub fn set_ubvec(self, ubvec: &'a [Real]) -> Graph<'a>

Sets the load imbalance tolerance for each constraint.

By default, it equals to 1.001 if ncon equals 1 and 1.01 otherwise.

For the ith partition and jth constraint the allowed weight is the ubvec[j]*tpwgts[i*ncon+j] fraction of the jth’s constraint total weight. The load imbalances must be greater than 1.0.

Panics

This function panics if the length of ubvec is not equal to ncon.

source

pub fn set_options(self, options: &[Idx; 40]) -> Graph<'a>

Sets the fine-tuning parameters for this partitioning.

When few options are to be set, Graph::set_option might be a better fit.

See the option module for the list of available parameters. Note that not all are applicable to a given partitioning method. Refer to the documentation of METIS (link) for more info on this.

Example

use metis::option::Opt as _;

let xadj = &[0, 1, 2];
let adjncy = &[1, 0];
let mut part = [0, 0];

// -1 is the default value.
let mut options = [-1; metis::NOPTIONS];

// four refinement iterations instead of the default 10.
options[metis::option::NIter::INDEX] = 4;

Graph::new(1, 2, xadj, adjncy)?
    .set_options(&options)
    .part_recursive(&mut part)?;

// The two vertices are placed in different parts.
assert_ne!(part[0], part[1]);

source

pub fn set_option<O>(self, option: O) -> Graph<'a>
where O: Opt,

Sets a fine-tuning parameter for this partitioning.

When options are to be set in batches, Graph::set_options might be a better fit.

See the option module for the list of available parameters. Note that not all are applicable to a given partitioning method. Refer to the documentation of METIS (link) for more info on this.

Example

let xadj = &[0, 1, 2];
let adjncy = &[1, 0];
let mut part = [0, 0];

Graph::new(1, 2, xadj, adjncy)?
    .set_option(metis::option::NIter(4))
    .part_recursive(&mut part)?;

// The two vertices are placed in different parts.
assert_ne!(part[0], part[1]);