Solver for DAG Partitioning
---------------------------
Build environment:
------------------
* CMake 2.8
* G++ 4.7
tested on Debian GNU/Linux squeeze
Build using commands (Linux or Cygwin shell):
---------------------------------------------
cmake CMakeLists.txt
make
How to use:
-----------
"dagpart" has a number of built-in random graph generators to solve
DAG Partitioning on. It will first run a heuristic due to Leskovec et
al (2009) and then verify using the exact algorithm whether the found
partitioning set is optimal. "dagpart" is used as follows.
To search for a partitioning set of size k in "file" (for file
format, see below), use:
./dagpart -f file -k k
To search for partitioning set of size k in graph consisting of c
complete connected components, each with n vertices, interconnected
by k random arcs, use:
./dagpart -K -n n -c c -k k
To search for partitioning set of size k in graph consisting of c
Erdos-Renyi random graphs, each with n vertices and edge probability
0.5, interconnected by k random arcs, use:
./dagpart -E -n n -c c -k k:
To search for partitioning set of size k in graph consisting of c
preferential attachment graphs with outdegree o, each with n
vertices, interconnected by k random arcs, use:
./dagpart -A -n n -c c -k k -o o:
To search for partitioning set of size k in preferential attachment
graph with outdegree o and c sinks, use:
./dagpart -C -n n -c c -o o:
If the option '-p out.dot' is used, the generated graph is written
to the file out.dot in graphviz format
Graph format:
----------------------
The input format has on each line an arc of the form "a -> b" or "b
-> a", where a and b are vertex numbers and the arc points from b to
a. For example:
1 -> 2
3 <- 2
3 -> 4
René van Bevern