Switch branches/tags
Nothing to show
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
..
Failed to load latest commit information.
Makefile
README
init_nonrandom.cpp
io.cpp
label_balance_edges.cpp
label_balance_edges_maxcut.cpp
label_balance_verts.cpp
label_prop.cpp
pulp.cpp
pulp.h
pulp_main.cpp
rand.cpp

README

***********************************************************
****:::::'########:::::::::::::'##:::::::'########:::::****
****::::: ##.... ##:::::::::::: ##::::::: ##.... ##::::****
****::::: ##:::: ##:::::::::::: ##::::::: ##:::: ##::::****
****::::: ########::'##::::'##: ##::::::: ########:::::****
****::::: ##.....::: ##:::: ##: ##::::::: ##.....::::::****
****::::: ##:::::::: ##:::: ##: ##::::::: ##:::::::::::****
****::::: ##::::::::. #######:: ########: ##:::::::::::****
****:::::..::::::::::.......:::........::..::::::::::::****
***********************************************************
*********************** Version 0.2 ***********************
********************************************************************************

 PuLP: Multi-Objective Multi-Constraint Partitioning using Label Propagation
              Copyright (2014) Sandia Corporation

Questions?  Contact George M. Slota    (gmslota@sandia.gov)
                    Siva Rajamanickam  (srajama@sandia.gov)

If used, please cite:

[1] George M. Slota, Kamesh Madduri, and Sivasankaran Rajamanickam, Complex Network Partitioning Using Label Partitioning, to appear in the SIAM Journal on Scientific Computing (SISC).

[2] George M. Slota, Kamesh Madduri, and Sivasankaran Rajamanickam, PuLP: Scalable Multi-Objective Multi-Constraint Partitioning for Small-World Networks, in the Proceedings of the 2nd IEEE Conference on Big Data (BigData 2014).

********************************************************************************
Version info:

v0.2 -- 7 June 2015
--Support for weighted vertices and edges

v0.11 -- 9 May 2016
--Updates to label prop initialization and minor changes throughout

v0.1 -- 9 December 2015
--Initial release


********************************************************************************
To make:

1.) Set CXX in Makefile to your c++ compiler, adjust CXXFLAGS if necessary
-OpenMP 3.0 support is required for parallel execution
-No other dependencies needed

2.) $ make pulp
-This will make the pulp executable

3.) $ make libpulp
-This will make libpulp.a static library for use with pulp.h header


********************************************************************************
To run:

$ ./pulp [graphfile] [num parts] [options]

[graphfile] is of adjacency list (METIS) format, n is number of vertices, m is number of undirected edges, fmt is optional and described below, and vertex ids are 1-indexed:
n m fmt
v2 v3 v4
v1 v3 v5 v6 v8
v1 v2 
... etc

PuLP also supports vertex and edge weights, where fmt is the format specified by:
fmt = blank or 000 = no weights
fmt = 001 = edge weights
fmt = 010 = vertex weight
fmt = 011 = both vertex and edges weights

Vertex weights 'vW' are given as the first value in each line:
n m 010
vW1 v2 v3 v4
vW2 v1 v3 v5 v6 v8
vW3 v1 v2 
... etc

Edge weights 'eW' are given after each edge:
n m 001
v2 eW12 v3 eW13 v4 eW14
v1 eW21 v3 eW23 v5 eW25 v6 eW26 v8 eW28
v1 eW31 v2 eW32 
... etc

And both can be used concurrently:
n m 011
vW1 v2 eW12 v3 eW13 v4 eW14
vW2 v1 eW21 v3 eW23 v5 eW25 v6 eW26 v8 eW28
vW3 v1 eW31 v2 eW32 
... etc

[num parts] is the number of desired partitions (>=2)

Options:
  -v [#.#]:
      Vertex balance constraint [default: 1.10 (10%)]
  -e [#.#]:
      Edge balance constraint [default: none; 1.50 (50%) when -c option is used]
  -c:
      Attempt to minimize per-part cut in addition to total edge cut
  -l:
      Do label propagation-based initialization instead of BFS initialization
  -m [#]:
      Generate multiple partitions [default: 1]
  -o [file]:
      Output parts file [default: graphname.part.numparts(.#)]
  -i [file]:
      Input parts file [default: none]
  -q:
      Evaluate generated partition quality

[Input/Output Files] has n lines. Each line contains a single integer [0...(num parts-1)] that corresponds to the part assignment of the vertex identifier of that line number. I.e., a '5' on line 7 would indicate that vertex 7 is assigned to part 5.


********************************************************************************
Examples:

1.) Generate 16 parts of Live Journal network with default vertex balance constraint, only minimizing edge cut, and using the default BFS-based initialization; perform quality evaluation

$ ./pulp LiveJournal.adj 16 -q


2.) Generate 16 parts of Live Journal network with tighter vertex balance constraint (3%), only minimizing edge cut, and using label propagation-based initialization

$ ./pulp LiveJournal.adj 16 -v 1.03 -l


3.) Generate 128 parts of Live Journal network with tighter vertex balance constraint and looser edge balance constraint while minimizing edge cut and using BSF-based initialization

$./pulp LiveJournal.adj 128 -v 1.03 -e 2.5


4.) Generate 128 parts of Live Journal network with tighter vertex balance constraint and looser edge balance constraint while minimizing both edge cut and max per-part edge cut, write output part file to temp.parts

$./pulp LiveJournal.adj 128 -v 1.03 -e 2.5 -c -o temp.parts


5.) Generate 16 parts of Live Journal network with tighter vertex balance constraint and looser edge balance constraint while minimizing both edge cut and max per-part edge cut, reading in an initial partition, and writing output part file to temp.parts

$./pulp LiveJournal.adj 128 -v 1.03 -e 2.5 -c -i input.parts -o temp.parts


6.) Generate 5 different partitionings of Live Journal network each having 16 parts with tighter vertex balance constraint and looser edge balance constraint while doing label propagation-based initialization

$./pulp LiveJournal.adj 128 -v 1.03 -e 2.5 -o temp.parts -m 5 -l
Note: outputs will be written to temp.parts.0, temp.parts.1, ..., temp.parts.4


********************************************************************************
Notes:

1.) The use case for PuLP is small-world graphs with skewed degree distributions. Other partitioners are more well-suited for handling regular mesh-like graphs. PuLP can partition such graphs quickly, but the quality won't be as high as when using other tools.

2.) Be careful when determining vertex and edge balance constraints, as you might create a problem for which there is no solution; PuLP will take longer to execute and the output won't be as nice as you're expecting.

3.) Sometimes the initialization routines produce a very bad initial partition for the subsequent balancing stages. Re-running PuLP might help if that's the case.


********************************************************************************
Known issues:

1.) There is minimal error checking for inputs, so the exact format listed above for [graphfile] is required. Be careful with the formats and values of the other optional inputs otherwise unexpected behavior may result.

2.) No options exist for adjusting iteration counts for various algorithm loops, however, these can be changed in the source files.

3.) Currently, there is a 32-bit limitation in the internal graph storage format and algorithmic data structures.

4.) Multiple vertex and edge weights are currently not supported. This is planned for future versions.