Mongoose User Guide
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 21
Mongoose User Guide, Version 2.0.4
Scott Kolodziej, Nuri Yeralan, Tim Davis, William W. Hager
May 25, 2019
Contents
1 Overview 3
1.1 Coarsening and Renement Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Quadratic Programming and Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Fiduccia-Mattheyses Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Availability 5
2.1 GettingtheCode ........................................... 5
2.2 Prerequisites.............................................. 5
2.3 Compilation .............................................. 5
3 Using Mongoose as an Executable 7
3.1 License................................................. 9
4 Using Mongoose in C++ 9
4.1 SampleC++Program ........................................ 9
4.2 CreatingaGraph ........................................... 10
4.2.1 CreatingaGraphManually.................................. 10
4.2.2 Creating a Graph from a Sparse Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2.3 Creating a Graph from a Matrix Market File . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 C++API ............................................... 12
4.4 ANoteonMemoryManagement................................... 14
5 Using Mongoose in MATLAB 14
5.1 To Install the MATLAB Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2 SampleMATLABProgram ...................................... 14
5.3 MATLABAPI ............................................. 16
1
6 Options 17
6.1 CoarseningOptions .......................................... 17
6.2 Initial Guess/Partitioning Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.3 WaterdanceOptions.......................................... 19
6.4 Fiduccia-MattheyesOptions...................................... 19
6.5 Quadratic Programming Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.6 Final Partition Target Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.7 OtherOptions............................................. 21
7 References 21
2
1 Overview
Mongoose is a graph partitioning library that can quickly compute edge cuts in arbitrary graphs [2]. Given a
graph with a vertex set Vand edge set E, an edge cut is a partitioning of the graph into two subgraphs that are
balanced (contain the same number of vertices) and the connectivity between the subgraphs is minimized (few
edges are in the cut).
Finding high quality edge cuts quickly is an important part of circuit simulation, parallel and distributed computing,
and sparse matrix algorithms.
1.1 Coarsening and Renement Framework
Mongoose uses a coarsening and renement framework (sometimes referred to as a multilevel framework [5, 6]).
Rather than attempt to compute an edge cut on the input graph directly, Mongoose rst coarsens the graph by
computing a vertex matching and contracting the graph to form a smaller, but structurally similar, graph.
Coarsening
Initial Partition
Refinement
Figure 1: Coarsening and Renement
Mongoose uses a variety of methods to coarsen the input graph, including random matching and heavy-edge
matching. Additionally, Mongoose oers stall-reducing vertex matching strategies called Brotherly (or two-hop)
matching and Community matching. Brotherly matching allows vertices who share a neighbor to be matched,
even if they have no edge directly connecting them, and community matching allows two vertices whose neighbors
are matched together to be matched together. These methods are advantageous in eciently coarsening certain
3
classes of graphs, notably social networking graphs, where the vertex degree can vary greatly.
Heavy Edge
Match
Brotherly Matches
Adoption Match
(3-Way)
Coarsen
Figure 2: Brotherly Matching
Brotherly Matches
Community Match
Heavy-Edge
Match
Coarsen
Figure 3: Community Matching
Another matching strategy used in Mongoose is known as Adoption matching. If an unmatched vertex has no
unmatched neighbors, it can be grouped into a 3-way matching with a neighboring matched vertex. These
strategies allow the graph to be coarsened quickly even when the graph is highly irregular, which in turn decreases
memory requirements and overall computational time.
1.2 Quadratic Programming and Optimization
Mongoose is known as a hybrid graph partitioner, as it uses multiple methods in tandem to nd higher quality
cuts eciently. The rst such method Mongoose employs is quadratic programming (QP). The edge cut problem
was formatted as a continuous quadratic programming problem by Hager and Krylyuk [4]. This formulation is
solved (rather, improved) using a gradient projection algorithm and a modied version of NAPHEAP, a quadratic
knapsack solver [1].
The quadratic program used is shown below. Hager and Krylyuk have proven that the global optimum to this
quadratic program yields the solution to the graph partitioning problem (but note that both are NP-hard problems
to solve).
min
x∈Rn(1−x)T(A+I)xsubject to 0≤x≤1, ℓ ≤1Tx≤u,
ℓand uare lower and upper bounds on the desired size of one partition, and Ais the adjacency matrix of the
graph.
1.3 Fiduccia-Mattheyses Algorithm
In addition to the quadratic programming approach for rening an edge cut, a standard implementation of the
Fiduccia-Mattheyses algorithm [3] is also provided. This involves swapping vertices from one part to the other in
an eort to improve the edge cut quality. Some vertices are swapped even if no immediate improvement is found
in an attempt to escape a locally optimal solution. However, if no improvement is found after a number of swaps,
the change is reverted.
The Fiduccia-Mattheyses (FM) implementation in Mongoose utilizes heaps for high eciency.
4
2 Availability
2.1 Getting the Code
Mongoose is available on GitHub at https://github.com/ScottKolo/Mongoose. The code can be
downloaded using git using the following command:
git clone https://github.com/ScottKolo/Mongoose
Alternatively, Mongoose can be downloaded as a zip archive from the following URL:
https://github.com/ScottKolo/Mongoose/archive/edgesep.zip
Mongoose also appears as a component package of SuiteSparse, http://suitesparse.com.
2.2 Prerequisites
Mongoose requires CMake 2.8 and any ISO/IEC 14882:1998 compliant C++ compiler. Mongoose has been tested
to work with GNU GCC 4.4+ and LLVM Clang 3.5+ on Linux, and Apple Xcode 6.4+ on macOS.
2.3 Compilation
Once downloaded, Mongoose can be compiled using the following commands:
cd Mongoose
make
After compilation, the Mongoose demo can be run using ./bin/demo:
./bin/demo
********************************************************************************
Mongoose Graph Partitioning Library, Version 2.0.2 July 5, 2018
Copyright (C) 2017−2018
Scott P. Kolodziej, Nuri S. Yeralan, Timothy A. Davis, William W. Hager
Mongoose is licensed under Version 3 of the GNU General Public License.
Mongoose is also available under other licenses; contact authors for details.
********************************************************************************
Computing an edge cut for Erdos971.mtx...
Cut Cost: 1.1e+02
Cut Imbalance: zero (a perfect balance)
Trial Time: 1.9ms
********************************************************************************
Computing an edge cut for G51.mtx...
Cut Cost: 1.5e+03
5
Cut Imbalance: zero (a perfect balance)
Trial Time: 8.4ms
********************************************************************************
Computing an edge cut for GD97_b.mtx...
Cut Cost: 2.6e+03
Cut Imbalance: 1.1%
Trial Time: 0.19ms
********************************************************************************
Computing an edge cut for Pd.mtx...
Cut Cost: 1
Cut Imbalance: 0.0062%
Trial Time: 12ms
********************************************************************************
Computing an edge cut for bcspwr01.mtx...
Cut Cost: 3
Cut Imbalance: 1.3%
Trial Time: 0.18ms
********************************************************************************
Computing an edge cut for bcspwr02.mtx...
Cut Cost: 5
Cut Imbalance: 1%
Trial Time: 0.17ms
********************************************************************************
Computing an edge cut for bcspwr03.mtx...
Cut Cost: 11
Cut Imbalance: zero (a perfect balance)
Trial Time: 0.34ms
********************************************************************************
Computing an edge cut for bcspwr04.mtx...
Cut Cost: 25
Cut Imbalance: zero (a perfect balance)
Trial Time: 0.75ms
********************************************************************************
Computing an edge cut for bcspwr05.mtx...
Cut Cost: 12
Cut Imbalance: 0.11%
Trial Time: 0.91ms
********************************************************************************
Computing an edge cut for bcspwr06.mtx...
Cut Cost: 7
Cut Imbalance: zero (a perfect balance)
Trial Time: 2.4ms
********************************************************************************
Computing an edge cut for bcspwr07.mtx...
Cut Cost: 7
Cut Imbalance: zero (a perfect balance)
Trial Time: 2.6ms
********************************************************************************
Computing an edge cut for bcspwr08.mtx...
Cut Cost: 25
Cut Imbalance: zero (a perfect balance)
Trial Time: 2.2ms
6
********************************************************************************
Computing an edge cut for bcspwr09.mtx...
Cut Cost: 11
Cut Imbalance: 0.029%
Trial Time: 5.4ms
********************************************************************************
Computing an edge cut for bcspwr10.mtx...
Cut Cost: 25
Cut Imbalance: zero (a perfect balance)
Trial Time: 8.6ms
********************************************************************************
Computing an edge cut for dwt_992.mtx...
Cut Cost: 1.9e+02
Cut Imbalance: zero (a perfect balance)
Trial Time: 4.7ms
********************************************************************************
Computing an edge cut for jagmesh7.mtx...
Cut Cost: 27
Cut Imbalance: zero (a perfect balance)
Trial Time: 2.8ms
********************************************************************************
Computing an edge cut for NotreDame_www.mtx...
Cut Cost: 1.9e+02
Cut Imbalance: 0.00015%
Trial Time: 6.2e+02ms
********************************************************************************
Total Demo Time: 0.67s
Demo complete; all tests passed
To run the complete test suite, the command make test can be used. Note that Python 2.7+ must be installed.
Additionally, this user guide can be generated from source with the command make userguide. XeLaTeX
(commonly included in LaTeX distributions) must be installed.
3 Using Mongoose as an Executable
In addition to the demo executable, the mongoose executable is built at ./bin/mongoose. This executable
can be used to partition a graph given a Matrix Market le:
mongoose <MM-input-file.mtx> [output-file]
The mongoose executable generates a text le with two blocks: a JSON-formatted information block with timing
and cut quality metrics, and the partitioning information itself. The partitioning information is listed with one
vertex per line, with the vertex number followed by the part (0 for part A, 1 for part B).
For example, the following can be used to partition the NotreDame_www.mtx matrix:
7
cd build
./bin/mongoose ../Matrix/NotreDame_www.mtx NotreDame_www_out.mtx
********************************************************************************
Mongoose Graph Partitioning Library, Version 2.0.2 July 5, 2018
Copyright (C) 2017−2018
Scott P. Kolodziej, Nuri S. Yeralan, Timothy A. Davis, William W. Hager
Mongoose is licensed under Version 3 of the GNU General Public License.
Mongoose is also available under other licenses; contact authors for details.
********************************************************************************
Total Edge Separator Time: 0.256587s
Matching: 0.03576s
Coarsening: 0.05597s
Refinement: 0.01149s
FM: 0.002221s
QP: 0.1448s
IO: 0.3147s
Cut Properties:
Cut Size: 320
Cut Cost: 165
Imbalance: 1.535e−06
The output le name is optional. If omitted, the default is mongoose_out.txt. For this matrix, the output
le looks like the following:
{
”InputFile”:”../Matrix/NotreDame_www.mtx”,
”Timing”: {
”Total”: 0.256587,
”Matching”: 0.035762,
”Coarsening”: 0.055973,
”Refinement”: 0.011487,
”FM”: 0.002221,
”QP”: 0.144759,
”IO”: 0.314704
},
”CutSize”: 320,
”CutCost”: 165,
”Imbalance”: 1.53502e−06
}
0 0
1 0
2 0
3 0
...
218 1
219 0
...
325660 1
8
325661 1
325662 1
325664 0
325665 0
...
325727 0
325728 0
3.1 License
Mongoose is licensed under the GNU Public License version 3 (GPLv3). Full text of the license can be found
int Mongoose/Doc/License.txt. For a commercial license, please contact Dr. Timothy A. Davis at
davis@tamu.edu.
4 Using Mongoose in C++
4.1 Sample C++ Program
1#include ”Mongoose.hpp”
2#include <iostream>
3#include <iomanip>
4#include <math.h>
5
6using namespace Mongoose;
7using namespace std;
8
9int main(int argn, const char **argv)
10 {
11 EdgeCut_Options *options = EdgeCut_Options::create();
12 if (!options) return EXIT_FAILURE; // Return an error if we failed.
13
14 options−>matching_strategy = HEMSRdeg;
15 options−>initial_cut_type = InitialEdgeCut_QP;
16
17 Graph *graph = read_graph(argv[1]);
18 if (!graph)
19 {
20 options−>~EdgeCut_Options();
21 return EXIT_FAILURE;
22 }
23
24 // Call Mongoose to compute an edge separator
25 EdgeCut *result = edge_cut(graph, options);
26
27 cout << ”Partitioning Complete!” << endl;
28 cout << ”Cut Cost: ” << setprecision(2) << result−>cut_cost << endl;
9
29 cout << ”Cut Imbalance: ” << setprecision(2) << fabs(100*result−>imbalance) << ”%” << endl;
30
31 options−>~EdgeCut_Options();
32 graph−>~Graph();
33 result−>~EdgeCut();
34
35 /*Return success */
36 return EXIT_SUCCESS;
37 }
4.2 Creating a Graph
There are several dierent ways to create a Graph class instance for use in Mongoose.
The input graph to Mongoose is undirected, and can optionally be a weighted graph. The graph is held in
compressed-sparse column form, or equivalently compressed-sparse row form since the adjacency matrix is sym-
metric. The graph is represented by the following components:
•Int n: the number of vertices in the graph.
•Int nz: the number of nonzero entries in the adjacency matrix, which is twice the number edges.
•Int p [n+1]: the column pointer vector of size n+1.
•Int i [nz]: the adjacency lists held in a single array. The adjacency list of vertex jis held in i [p [j]
... p [j+1]-1]. Self-edges must not appear. The graph must be undirected, and so the adjacency
matrix must be symmetric.
•double x [nz]: an optional array of edge weights, where x [p [j] ... p [j+1]-1] are the edge
weights of the corresponding edges in the adjacency list of vertex j. If xis NULL, then the edges all have
weight 1.
•double w [n]: an optional array of vertex weights, where vertex jhas weight w [j]. If wis NULL,
then the vertices all have weight 1.
Note that the Int type is generally a 64-bit (long) integer type. It is dened as typedef SuiteSparse_long
Int; which is further dened as #define SuiteSparse_long long in SuiteSparse_cong.
4.2.1 Creating a Graph Manually
To create a graph manually, the following constructor is used:
static Graph *create(const Int _n,
const Int _nz,
Int *_p = NULL,
10
Int *_i = NULL,
double *_x = NULL,
double *_w = NULL);
Using the manual constructor, the number of vertices (or dimension of the matrix, Int _n) and the num-
ber of edges (or nonzero entries in the matrix, Int _nz) must both be specied. The column pointer vector
Int *_p and row index vector Int *_i must either be specied by the user, or, if left NULL, they will be
allocated such that _p = (Int *)SuiteSparse_calloc(n + 1, sizeof(Int)); and _i = (Int
*)SuiteSparse_malloc(nz, sizeof(Int));. The edge weights double *_x and the vertex weights
double *_w can either be specied, or, if left NULL, will be assumed to be one for all edges and vertices,
respectively.
Here are some examples:
•Graph::create(20, 50); creates a Graph with 20 vertices and 50 edges, but no data. Graph->p
and Graph->i are allocated by Mongoose to store exactly 20 columns (vertices) and 50 nonzero elements
(edges). This allows the user to populate Graph->p and Graph->i manually. All edge and vertex weights
are assumed to be one.
•Graph::create(20, 50, _p, _i); creates a Graph with 20 vertices and 50 edges with the pattern
specied. Graph->p and Graph->i are shallow copies of the arguments _p and _i and will not be freed
upon calling the destructor. All edge and vertex weights are assumed to be one.
•Graph::create(20, 50, _p, _i, _x); creates a Graph with 20 vertices and 50 edges with the
pattern and edge weights specied. Graph->p,Graph->i, and Graph->x are shallow copies of the
arguments _p,_i, and _x, and will not be freed upon calling the destructor. Edge weights are specied
by _x, but vertex weights are assumed to be one.
•Graph::create(20, 50, _p, _i, _x, _w); creates a Graph with 20 vertices and 50 edges
with edge and vertex weights specied. Graph->p,Graph->i,Graph->x, and Graph->w are shallow
copies of the arguments _p,_i,_x, and _w, and will not be freed upon calling the destructor. Edge
weights are specied by _x, and vertex weights are specied by _w.
4.2.2 Creating a Graph from a Sparse Matrix
Another way to create a Mongoose::Graph is from a pre-existing CSparse matrix struct.
static Graph *Create(cs *matrix);
Using this constructor, a CSparse matrix struct can be passed directly, with shallow copies made of cs->p,
cs->i, and cs->x. Note that this constructor is equivalent to calling the following for a CSparse matrix cs *A:
Graph::create(const Int A->n, A->p[A->n], A->p, A->i, A->x, NULL);
11
4.2.3 Creating a Graph from a Matrix Market File
Perhaps the easiest way to create a Graph instance is from a le. Mongoose provides easy le input helpers to
read, sanitize, and format a Matrix Market le. The matrix contained in the le must be sparse, real, and square.
If the matrix is not symmetric, it will be made symmetric by computing 1
2(A+AT). If a diagonal is present, it
will be removed.
Graph *read_graph(const std::string &filename);
Graph *read_graph(const char *filename);
For example, to read in the Matrix Market le jagmesh7.mtx located in the Mongoose sample matrix directory,
the following code can be used:
Mongoose::read_graph(“../Matrix/jagmesh7.mtx”);
4.3 C++ API
The following functions are available in the C++ API. After Mongoose is compiled, a static library version of
Mongoose is built at Mongoose/build/Lib/libmongoose.a. Include the Mongoose.hpp header le
located in Mongoose/Include and link with the static library to enable the following API functions. Both
the static and dynamic libraries, and the include le can then be installed for system-wide use with sudo make
install in the top-level Mongoose directory.
•Graph *read_graph(const std::string &filename);
•Graph *read_graph(const char *filename);
Mongoose::read_graph will attempt to read a Matrix Market le with the given lename and convert
it to a Mongoose Graph instance. The matrix contained in the le must be sparse, real, and square. If the
matrix is not symmetric, it will be made symmetric by computing 1
2(A+AT). If a diagonal is present, it
will be removed.
Mongoose::read_graph(const std::string &filename) accepts a C++-style std::string,
while Mongoose::read_graph(const char *filename) accepts a C-style null-terminated string.
•EdgeCut edge_cut(const Graph *);
•EdgeCut edge_cut(const Graph *, const EdgeCut_Options *);
Mongoose::edge_cut will attempt to compute an edge cut of the provided Mongoose::Graph object.
An EdgeCut_Options struct can also be supplied to modify how the edge cut is computed – otherwise,
the default options are used (see Section 6). The resulting partitioning information is returned as an
EdgeCut struct.
The EdgeCut struct is shown below.
12
1struct EdgeCut
2{
3bool *partition; /** T/F denoting partition side */
4Int n; /** # vertices */
5
6/** Cut Cost Metrics *****************************************************/
7double cut_cost; /** Sum of edge weights in cut set */
8Int cut_size; /** Number of edges in cut set */
9double w0; /** Sum of partition 0 vertex weights */
10 double w1; /** Sum of partition 1 vertex weights */
11 double imbalance; /** Degree to which the partitioning
12 is imbalanced, and this is
13 computed as (0.5 −w0/W). */
14
15 // Destructor
16 ~EdgeCut();
17 };
•static EdgeCut_Options *create();
Mongoose::EdgeCut_Options::create will return an EdgeCut_Options struct with default
state (see Section 6 for details about option elds and defaults). To run Mongoose with specic options,
call EdgeCut_Options::create and modify the struct as needed.
•static Graph *create(const Int _n,
const Int _nz,
Int *_p = NULL,
Int *_i = NULL,
double *_x = NULL,
double *_w = NULL);
•static Graph *create(cs *matrix);
Mongoose::Graph::create is the primary constructor for the Graph class. There are two versions:
one to manually specify attributes of the Graph, and one to form a Graph from a CSparse struct.
Using the manual constructor, the number of vertices (or dimension of the matrix, Int _n) and the number
of edges (or nonzero entries in the matrix, Int _nz) must both be specied. The column pointer vector
Int *_p and row index vector Int *_i must either be specied by the user, or, if left NULL, they will
be allocated such that _p = (Int *)SuiteSparse_calloc(n + 1, sizeof(Int)); and _i
= (Int *)SuiteSparse_malloc(nz, sizeof(Int));. The edge weights double *_x and the
vertex weights double *_w can either be specied, or, if left NULL, will be assumed to be one for all
edges and vertices, respectively.
Note that Mongoose will NOT free pointers passed to it, and that all pointers are shallow copies (i.e.
Mongoose does not make a copy of any data passed into it).
13
•∼EdgeCut_Options(); is the destructor for the EdgeCut_Options struct. If the user creates an
EdgeCut_Options struct using EdgeCut_Options::create, the user is also responsible for destruc-
ting it.
•∼Graph(); is the destructor for the Graph class. If the user creates a Graph class instance using
Graph::create, the user is also responsible for destructing it.
•∼EdgeCut(); is the destructor for the EdgeCut struct. After calling edge_cut(), the returned struct
must be destructed when the user is nished reading data from it.
4.4 A Note on Memory Management
Mongoose uses three primary data structures to pass information: the Graph class, the EdgeCut struct, and
the EdgeCut_Options struct. They are all dynamically allocated and must be destructed.
• For each Graph::create, there should be a matching Graph::∼Graph().
• For each EdgeCut_Options::create, there should be a matching EdgeCut_Options::∼EdgeCut_Options();
• For each call to edge_cut, there should be a matching EdgeCut::∼EdgeCut();
Lastly, Mongoose will NOT free pointers passed to it, and that all pointers are shallow copies (i.e. Mongoose
does not make a copy of any data passed into it). Freeing memory referenced by Mongoose prior to Mongoose
completing will result in a segmentation fault.
5 Using Mongoose in MATLAB
5.1 To Install the MATLAB Interface
To compile Mongoose for MATLAB, go to the MATLAB directory and type mongoose_make in the MATLAB
command window. Be sure to use a compiler supported by MATLAB. Type doc mex in MATLAB, or visit https:
//www.mathworks.com/support/compilers.html for details. For example, GCC 5.5.0 on Linux is not
supported by MATLAB R2017A, and it will not successfully compile Mongoose for that version of MATLAB.
MATLAB R2018b supports GCC 6.3.x on Linux.
5.2 Sample MATLAB Program
Below is a sample MATLAB program using the Mongoose MATLAB API. First, it loads in a matrix, sanitizes it,
and then partitions it using edge and vertex weights, then only edge weights, and the no weights.
1% A simple demo to demonstrate Mongoose. Reads in a matrix, sanitizes it,
2% and partitions it several different ways.
3function mongoose_demo
4
5% Obtain the adjacency matrix
6matfile_data = matfile(’494_bus.mat’);
14
7Prob = matfile_data.Problem;
8A = Prob.A;
9[m ~] = size(A);
10
11 % Sanitize the adjacency matrix: remove diagonal elements, make edge weights
12 % positive, and make sure it is symmetric. If the matrix is not symmetric
13 % or square, a symmetric matrix (A+A’)/2 is built.
14 A = sanitize(A);
15
16 % Create a vertex weight vector and create a heavy vertex
17 V = ones(1,m);
18 V(10) = 300;
19
20 % Create a set of default options and modify the target balance
21 O = edgecut_options();
22 O.target_split = 0.3;
23
24 % Run Mongoose to partition the graph with edge and vertex weights.
25 partVert = edgecut(A, O, V);
26
27 fprintf(’\n\nPartitioning graph with edge and vertex weights\n\n’);
28 fprintf(’=== Cut Info ===\n’);
29 fprintf(’Cut Size: %d\n’,full(sum(partVert .*sum(sign(A)))));
30 fprintf(’Cut Weight: %d\n\n’,full(sum(partVert .*sum(A))));
31 fprintf(’=== Balance Info ===\n’);
32 fprintf(’Target Split: 0.3\n’);
33 fprintf(’Actual Split: %1.4f\n’,sum(partVert .*V) / sum(V));
34 fprintf(’Unweighted Split: %1.4f\n’,sum(partVert) / m);
35
36 % Run Mongoose to partition the graph with no vertex weights.
37
38 partEdge = edgecut(A, O);
39
40 fprintf(’\n\nPartitioning graph with only edge weights\n\n’);
41 fprintf(’=== Cut Info ===\n’);
42 fprintf(’Cut Size: %d\n’,full(sum(partEdge .*sum(sign(A)))));
43 fprintf(’Cut Weight: %d\n\n’,full(sum(partEdge .*sum(A))));
44 fprintf(’=== Balance Info ===\n’);
45 fprintf(’Target Split: 0.5\n’);
46 fprintf(’Actual Split: %1.4f\n’,sum(partEdge) / m);
47
48 % Remove edge weights
49 A = sanitize(A, 1);
50
51 % Run Mongoose to partition the graph with no edge weights.
52 % Note that only the graph is passed as an argument, so default
53 % options are assumed.
54 partPattern = edgecut(A);
55
56 fprintf(’\n\nPartitioning graph with only edge weights\n\n’);
57 fprintf(’=== Cut Info ===\n’);
58 fprintf(’Cut Size: %d\n’,full(sum(partPattern .*sum(sign(A)))));
15
59 fprintf(’Cut Weight: %d\n\n’,full(sum(partPattern .*sum(A))));
60 fprintf(’=== Balance Info ===\n’);
61 fprintf(’Target Split: 0.5\n’);
62 fprintf(’Actual Split: %1.4f\n’,sum(partPattern) / m);
63
64 figure(’Position’, [100, 100, 1000, 400]);
65
66 % Plot the original matrix before permutation
67 subplot(1, 2, 1);
68 spy(A)
69 title(’Before Partitioning’)
70
71 % Plot the matrix after the permutation
72 subplot(1, 2, 2);
73 perm = [find(partEdge) find(1−partEdge)];
74 A_perm = A(perm, perm); % Permute the matrix
75 spy(A_perm)
76 title(’After Partitioning’)
77
78 % Set overall title
79 suptitle(’HB/494\_bus’)
80
81 end
5.3 MATLAB API
•function [G_coarse, A_coarse, map] = coarsen (G, Opts,A)
coarsen is used to coarsen an adjacency matrix (G) one level (one round of matching). An optional
edgecut_options struct (Opts) can be specied, as well as vertex weights (A).
•function options = edgecut_options()
edgecut_options() returns an options struct with defaults set. If modications to the default options
are needed, call edgecut_options() and modify the struct as needed. See section 6 for details on
available option elds.
•function partition = edgecut (G, Opts,A)
edgecut computes an edge cut of the graph Gwith edgecut_options Opts and vertex weights A, such
that A(i) = weight(vi). The returned array, partition, is a 1×nbinary array such that
partition(i) ={0if vi∈part A
1if vi∈part B
•function [G_coarse, A_coarse, map] = safe_coarsen (G, Opts,A)
safe_coarsen attempts to coarsen a graph Gwith edgecut_options Opts and vertex weights A. Prior
16
to coarsening, safe_coarsen rst calls sanitize(G) to ensure that the graph is able to be coarsened.
•function partition = safe_edgecut(G, Opts,A)
safe_edgecut attempts to compute and edge cut for a graph Gwith edgecut_options Opts and vertex
weights A. Note that both Opts and Aare optional arguments. safe_edgecut rst calls sanitize(G)
to ensure that the graph is formatted correctly.
•function A_safe = sanitize (A, make_binary)
sanitize attempts to take an adjacency matrix Aand convert it to one that Mongoose can read and
convert to an undirected graph. Note that make_binary is optional, with the default being false.
sanitize does the following as needed:
–If the matrix is unsymmetric, it forms 1
2(AT+A).
–The diagonal is removed (set to zero).
–Edge weights are forced to be positive (w=|w|) if make_binary = false.
–Edge weights are forced to be binary (w=sign(w)) if make_binary = true.
6 Options
When calling Mongoose, an optional EdgeCut_Options struct can be provided to specify how Mongoose should
behave.
6.1 Coarsening Options
Name coarsen_limit
Type Int
Default 50
Prior to computing a cut, the input graph is repeatedly coarsened until a suciently small number of vertices
exist in the graph. This limit is specied by coarsen_limit. Larger values will result in less time being spent
on the coarsening process, but may yield poor initial cuts or may require more time in computing such an initial
cut. Smaller values may result in more time spent coarsening, as well as a resulting coarsened graph which is a
poor structural representation of the input graph.
Name matching_strategy
Type MatchingStrategy (enum)
Default HEMSR
During coarsening, a matching of vertices is computed using one of several strategies determined by the match-
ing_strategy option eld. The possible values for this eld are described below:
17
•Random, random matching. Randomly matches unmatched vertices with each other until no more than
one unmatched vertex exists.
•HEM, heavy edge matching. Matches a given vertex with an unmatched neighbor with the largest weighted
edge between them.
•HEMSR, heavy edge matching with stall-reducing matching. A pass of heavy edge matching is followed by
a brotherly, adoption, and community (if enabled) matching where vertices that have been left unmatched
by heavy edge matching are paired with vertices that share a neighbor, but may not be directly connected.
•HEMSRdeg, heavy edge matching with stall-reducing matching subject to a degree threshold. Same as
HEMSR, but the stall-reducing step is only attempted on unmatched vertices whose degree is above a
threshold, described by EdgeCut_Options::high_degree_threshold ∗(average degree of graph).
high_degree_threshold is set to 2.0by default, meaning only unmatched vertices with degree greater
than or equal to two times the average degree of the graph are considered for stall-reducing matching.
Name do_community_matching
Type bool
Default false
Community matching is a matching option to aggressively match vertices whose neighbors have already been
matched. This can help in cases where coarsening easily stalls (e.g. social networking graphs), but incurs a slight
performance overhead during coarsening.
Name high_degree_threshold
Type double
Default 2.0
When using the HEMSRdeg matching strategy, only vertices satisfying the following inequality are considered for
brotherly, adoption, and community matching:
degree(v)≥ ⌊(high_degree_threshold)·(nz
n)⌋
Note that nz
nis the average degree of the vertices in the graph.
6.2 Initial Guess/Partitioning Options
Name initial_cut_type
Type InitialEdgeCutType (enum)
Default InitialEdgeCut_QP
After coarsening, an initial partitioning is computed. This initial guess can be computed several ways:
•InitialEdgeCut_QP. This method uses the quadratic programming solver to compute an initial parti-
tioning.
18
•InitialEdgeCut_Random. This method randomly assigns vertices to a part.
•InitialEdgeCut_NaturalOrder. This method assigns the rst ⌊n/2⌋vertices listed to one part, and
the remainder to the other part.
6.3 Waterdance Options
Name num_dances
Type Int
Default 1
At each level of graph renement, both the Fiduccia-Mattheyses renement algorithm and the quadratic program-
ming algorithm are used to rene the graph. This combination of algorithms, run back-to-back, is informally
referred to as a waterdance. num_dances is used to specify the number of waterdances.
For example, if num_dances = 2, at each renement level, the FM renement will be done, then QP re-
nement, then FM and QP again.
6.4 Fiduccia-Mattheyes Options
Name use_FM
Type bool
Default true
useFM can be used to enable or disable the use of the Fiduccia-Mattheyses renement algorithm. If useFM is
false, then the FM renement is skipped.
Name FM_search_depth
Type Int
Default 50
The Fiduccia-Mattheyses algorithm attempts to make positive gain moves whenever possible. However, to better
explore the non-convex search space, the FM algorithm will make unfavorable moves in an attempt to locate
another more favorable solution. The FM_search_depth limits the number of these unfavorable moves before
the algorithm stops.
Name FM_consider_count
Type Int
Default 3
During the Fiduccia-Mattheyses algorithm, a heap is maintained of the vertices sorted by their gains. Vertices
that have fewer neighbors in the same part relative to neighbors in the opposite part are prioritized higher in the
heap (with higher gains), and are generally more likely to yield better quality cuts when swapped to the opposite
part. FM_consider_count denes the number of vertices at the top of the heap to consider swapping to the
19
opposite part before terminating. When a vertex swap being considered does not yield a better cut after moving
FM_search_depth vertices, that iteration terminates, and the next vertex in the heap is considered.
Name FM_max_num_refinements
Type Int
Default 20
FM_max_num_refinements species the number of passes the Fiduccia-Mattheyses algorithm takes over the
graph. During each pass, suboptimal moves may be attempted to escape local optima.
6.5 Quadratic Programming Options
Name use_QP_gradproj
Type bool
Default true
use_QP_gradproj can be used to enable or disable the use of the quadratic programming renement algorithm.
If use_QP_gradproj is false, then the QP renement is skipped. This may provide faster solutions at the
cost of cut quality.
Name gradproj_tolerance
Type double
Default 0.001
Convergence tolerance for the projected gradient algorithm in the quadratic programming renement approach.
Decreasing the tolerance may improve solution quality at the cost of additional computation time. It may also
be advisable to increase gradproj_iteration_limit, as a decreased tolerance may require additional iter-
ations to converge.
Name gradproj_iteration_limit
Type Int
Default 50
Maximum number of iterations for the gradient projection algorithm in the quadratic programming renement
approach. More iterations may allow the gradient projection algorithm to nd a better solution at the cost of
additional computation time.
6.6 Final Partition Target Options
Name target_split
Type double
Default 0.5
20
target_split species the desired balance of the edge cut. The default is a balanced cut (0.5). Note that
the target split takes into account weighted vertices.
Name soft_split_tolerance
Type double
Default 0
Cuts within target_split ±soft_split_tolerance are treated equally. For example, if any cut within
0.4 and 0.6 balance is acceptable, the user may specify target_split = 0.5 and soft_split_tolerance
= 0.1.
6.7 Other Options
Name random_seed
Type Int
Default 0
Random number generation is used primarily in random matching strategies (matching_strategy = Random)
and random initial guesses (initial_cut_type = InitialEdgeCut_Random). random_seed can be
used to seed the random number generator with a specic value.
7 References
References
[1] Davis, T. A., Hager, W. W., and Hungerford, J. T. An ecient hybrid algorithm for the separable
convex quadratic knapsack problem. ACM Trans. Math. Softw. 42, 3 (May 2016), 22:1–22:25.
[2] Davis, T. A., Hager, W. W., Kolodziej, S. P., and Yeralan, N. S. Algorithm XXX: Mongoose,
a graph coarsening and partitioning library. ACM Trans. Math. Softw.. Submitted.
[3] Fiduccia, C. M., and Mattheyses, R. M. A linear-time heuristic for improving network partitions. In
19th Conference on Design Automation, 1982. (June 1982), pp. 175–181.
[4] Hager, W. W., and Krylyuk, Y. Graph partitioning and continuous quadratic programming. SIAM
Journal on Discrete Mathematics 12, 4 (1999), 500–523.
[5] Hendrickson, B., and Leland, R. A multi-level algorithm for partitioning graphs. SC Conference 0
(1995), 28.
[6] Karypis, G., and Kumar, V. Analysis of multilevel graph partitioning. In Proceedings of the 1995
ACM/IEEE Conference on Supercomputing (New York, NY, USA, 1995), Supercomputing ’95, ACM.
21
