This repository holds the code for two approximation algorithms for partitioning graphs into balanced parts. It also contains code used to generate a specific set of planar graphs that were used to test these algorithms.
The spectural algorithm, Ncuts.cpp, requires the LAPACK library as well its c interface LAPACKE. Please refer to the LAPACKE documentation for instructions on how to properly set it up.
Graphs generated and used in this repo are undirected and use the following format:
p edge V E
e u1 v1 w1
e u2 v2 w2
e u3 v3 w3
...
Where V is the number of vertices in the graph, E the number of edges in the graph, ux the index of a vertex at one end of an edge, vx the index of a vertex at the other end of the edge and wx is the weight of the edge.
To compile the executables, simply run the following command:
make
To run the spectural clustering algorithm, run the following command replacing GRAPH_FILE and NUMBER_OF_BLOCKS with the name of the graphfile you wish to partition and the number of blocks you desire respectively.
./NCuts GRAPH_FILE NUMBER_OF_BLOCKS
To run the dynamic programming algorithm, run the following command replacing GRAPH_FILE and NUMBER_OF_BLOCKS with the name of the graphfile you wish to partition and the number of blocks you desire respectively.
./DPCuts GRAPH_FILE NUMBER_OF_BLOCKS