Graph Partitioning Framework

SGL provides a a framework for partitioning graphs 1 that can be used to provides common off of the shelf partitions, as well as a way to construct novel graph partitioning algorithms and schemes.

Diffusive Rebalance

One of the graph repartitioners that SGL provides is a diffusive rebalancing partitioner that takes a graph that is already partitioned in some way (possibly using the implicit block partition) and rebalances it to minimize each partition's weight and edge cut.

For example, if we have a graph g whose vertex properties contain a field rank() which we would like to use as the vertex weight to rebalance, we can do the following:

// Create a weight map that uses the rank property as weight
using weight_map_type = graph_internal_property_map<view_type, get_weight_property>;
weight_map_type weight_map{g, get_weight_property{}};

// Repartition the graph using a diffusive method
rebalance_diffusive(g, weight_map);


The weight map that we created relies on a functor that can extract the weight for each property. The following will suffice:

struct get_weight_property
{
using value_type = double;
template<typename Property>
value_type get(Property p)
{
return p.rank();
}
};


Using this method, the graph will be repartitioned based on the rank value for each vertex.

Global Rebalance

A more straightforward repartitioning algorithm is a global repartitioning method that does not take edge cuts or locality into account, and moves vertices greedily to minimize the difference between partition weights.

This method is cheaper to compute than the diffusive method.

As an example, it can be called as follows:

// Create a weight map that uses the rank property as weight
using weight_map_type = graph_internal_property_map<view_type, get_weight_property>;
weight_map_type weight_map{g, get_weight_property{}};

// Repartition the graph using a diffusive method
rebalance_global(g, weight_map);


1 Castet, Nicolas (2013). A Parallel Graph Partitioner for STAPL. Master's thesis, Texas A&M University. Available electronically from http://hdl.handle.net/1969.1/149590.