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