Partitioning a hypergraph using Mondriaan
This guide is a step-by-step introduction to using Mondriaan for the purpose of hypergraph partitioning. For more extensive information about Mondriaan, please take a look at the user's guide.
How to download and install Mondriaan
Download the latest version of Mondriaan. Uncompress with
% tar xzvf mondriaan4.tar.gz
This will create a directory Mondriaan4
which contains all the files of the Mondriaan package.
Run
% make
which will build Mondriaan and the associated tools.
Translating a hypergraph to the weighted Matrix Market file format
In order to use Mondriaan for hypergraph partitioning, it is necessary to convert your hypergraph to the Matrix Market file format and supply it with vertex weights. The hypergraph is interpreted as a matrix where there is a column for each vertex, and a row for each hyperedge or net.
![](hypergraph.gif)
For example, we can consider the hypergraph G = (V, E)
from Figure 1 with
vertices V = {1, 2, 3, 4, 5}
and nets E = {{1}, {1, 2}, {2, 3, 4}, {3, 4}}
as a matrix A
with 5 columns and 4 rows in Matrix Market format:
%%MatrixMarket weightedmatrix coordinate pattern general 4 5 8 2 1 1 2 1 2 2 3 2 3 3 3 4 4 3 4 4 1 1 1 1 1
Here the values 4 5 8 2
indicate that this is a matrix with 4 rows (nets), 5 columns (vertices), 8 entries (total number of vertices in all nets), and weighted columns (the value 2 equals 10 in binary: weighted columns, unweighted rows).
Then after all nonzeroes, 1 1, 2 1, ...
, we find the vertex weights, which are set to 1 for all five vertices.
Providing the vertex weights is essential, because otherwise Mondriaan will by default weigh all the columns by the number of nonzeroes contained in them, which will lead to unbalanced hypergraph partitions.
Setting the proper Mondriaan options
Now that we have our hypergraph as a Matrix Market file, say foo.mtx
, we can use Mondriaan to partition it.
First we go to the tools/
directory.
% cd tools
Here the options file Mondriaan.defaults
should set SplitStrategy
to onedimcol
, because we want Mondriaan to partition the matrix columns, which correspond to the hypergraph vertices.
Then we partition foo.mtx
in two parts with a maximum imbalance of 10% by running
% ./Mondriaan foo.mtx 2 0.1
Extracting the hypergraph partitioning from the matrix partitioning
After performing the matrix partitioning, the file foo.mtx-v2
contains the vector distribution of the columns
5 2 1 1 2 1 3 2 4 2 5 1
The first line 5 2
contains the number of columns (5) and the number of parts to which they have been assigned (2).
Following this line are the column indices and the parts to which the columns have been assigned.
Because the column indices correspond directly to the vertices of our hypergraph, we see that our hypergraph has been partitioned into two parts: {1, 2, 5}
and {3, 4}
, which was to be expected if you look at Figure 1.