Integrated Network Decomposition & Dynamic programming for Graph Optimization problems
C++ C Objective-C Shell CSS R Other
Latest commit 4bf6618 Sep 28, 2013 @bdsullivan Merge pull request #41 from bdsullivan/testing
Merging new feature calculations and improvements from graph-survey
Permalink
Failed to load latest commit information.
MSVC editing MSVC README.txt Aug 31, 2013
bin add bin and lib directories May 10, 2012
lib add bin and lib directories May 10, 2012
lib_branchd Added "doc" and "clean_doc" options to Makefile. Apr 26, 2013
lib_graphd Resolving merge conflicts for survey/merge-2.0 and testing branch. Sep 27, 2013
lib_ptreed Add Petsc and Slepc options to build system Jul 2, 2013
lib_treed Add Petsc and Slepc options to build system Jul 2, 2013
madness Removing madness binaries and generated makefile from git May 28, 2013
max_wis Add Petsc and Slepc options to build system Jul 2, 2013
sample_graphs Initial commit to repository May 9, 2012
scripts Script to process and merge graph stats into a common csv file. May 9, 2013
uthash-1.9.3 Initial commit to repository May 9, 2012
util Merge branch 'fix-avg-path' Sep 26, 2013
viz Add Petsc and Slepc options to build system Jul 2, 2013
.gitignore Merge branch 'master' into openmp May 31, 2013
AUTHORS Update AUTHORS Aug 15, 2013
INSTALL Adding example with wget and build commands of how to incorporate met… Nov 5, 2012
LICENSE Minor fix to LICENSE to meet ORNL requirements. Aug 22, 2012
Makefile Merge branch 'master' into openmp Jun 5, 2013
README.md Adding example for running graph_stats Sep 27, 2013
make.inc CSG adding make.inc back in Aug 30, 2013
make.inc.parallel Resolving merge conflicts for survey/merge-2.0 and testing branch. Sep 27, 2013
make.inc.serial Resolving merge conflicts for survey/merge-2.0 and testing branch. Sep 27, 2013
thirdparty.txt Updating instructions for SuiteSparse. Allowing earlier exit on seria… Aug 22, 2012
uncrustify.cfg adding uncrustify configuration for inddgo Apr 18, 2013

README.md

Installing INDDGO

To install INDDGO, follow the steps listed in the INSTALL file.

As described in INSTALL and thirdparty.txt, INDDGO can be compiled with several optional packages. The METIS software package is highly recommended for performance, as it enables several more efficient elimination heuristics, as well as a much faster graph triangulation routine.

For visualization, we have provided routines which produce DOT output compatible with the graphviz package (http://www.graphviz.org/). These files can be passed directly to any one of the layout executables (such as neato or dot) after graphviz is installed.

Note that although it is not a prerequisite for using INDDGO, if you wish to use the optional functionality of solving mixed integer programming formulations of MWIS, you should have glpsol installed and available.

Running INDDGO binaries

The main INDDGO binaries are placed in the "bin" subdirectory of your source tree.

The default binaries created by INSTALL include executables to:

  • generate partial k-trees (./bin/gen_pkt)
  • compute elimination orderings, tree decompositions, and maximum weighted independent sets (./bin/serial_wis and/or ./bin/parallel_wis)
  • provide various visualization output (./bin/td_viz)
  • calculate a wide variety of graph features and statistics (./bin/graph_stats)

Currently, all tree decomposition functionality is accessible through the weighted independent set executables - flags are provided to disable the problem-specific dynamic programming portion of the code (e.g. -decompose_only).

All binaries respect the -h flag for printing a comprehensive usage message detailing required input and all options. Note that not all options are supported yet in the parallel_wis executable.

When running parallel versions of INDDGO, you must set the following environment variables:

  • PTD_NUM_THREADS
  • OMP_NUM_THREADS
  • MAD_NUM_THREADS

NOTE: It is assumed the input graph for weighted independent set is connected. If it is not, these executables will find and run on the largest connected component. All components will be written to separate .comp files, and the one used will be identified through a message to standard out.

Examples of common use cases

Two sample input graph files, as well as an example tree decomposition file and elimination order file can be found in the sample_graphs directory. All examples use these files. The optimal MWIS value for each is in the comments at the top of the DIMACS file. Additional information on both input and output formatting for the weighted independent set binaries is in max_wis/README.

Generating Test Data

Create 3 partial k-trees on 1000 vertices with width 20, 60 percent of full k-tree edges, randomized vertex labels, and names of the form mygraph.1000.20.60_.dimacs

  • ./bin/gen_pkt -t 3 -n 1000 -k 20 -p 60 -r -fn ./sample_graphs/mygraph

Find Tree Decomposition

Generate a tree decomposition (serial) and save elimination ordering and decomposition to file for future use.

  • ./bin/serial_wis -f sample_graphs/1dc.64.dimacs -gavril -mind -decompose_only -w sample_graphs/1dc.64.tree -eorder sample_graphs/1dc.64.mind.eorder

Run MWIS (serial, find set)

Computes max weighted independent set and saves vertices to solution file named .WIS.sol

  • ./bin/serial_wis -f sample_graphs/1dc.64.dimacs -gavril -mind

Run MWIS (serial, find objective)

Computes objective (set weight) only, but reduces memory use drastically.

  • ./bin/serial_wis -f sample_graphs/1dc.64.dimacs -gavril -mind -no_reconstruct -del_ch

Run MWIS (all parallel)

Complete run from graph to final solution. Requires PARMETIS.

  • export MAD_NUM_THREADS=4
  • export OMP_NUM_THREADS=4
  • export PTD_NUM_THREADS=4
  • mpirun -n 4 ./bin/parallel_wis -f sample_graphs/1dc.64.dimacs -gavril -mind -pbag -parmetis

Run MWIS (only DP parallel)

Reads EO from file, serial tree decomposition, parallel (MADNESS) DP.

  • export MAD_NUM_THREADS=4
  • export OMP_NUM_THREADS=4
  • export PTD_NUM_THREADS=4
  • mpirun -n 4 ./bin/parallel_wis -ord sample_graphs/1dc.64.mind.eorder -f sample_graphs/1dc.64.dimacs -gavril

Generate visualization

Create a basic DOT file of the tree decomposition for use with graphviz where bags are labelled with the vertices they contain (sample graphviz command: neato -Tpdf -o tree.pdf tree.dot).

  • ./bin/td_viz -f ./sample_graphs/1dc.64.dimacs -t ./sample_graphs/1dc.64.tree -e

Calculate graph statistics

Generates a set of output files containing the results of your selection of a broad spectrum of graph statistics (run with -h to see all options) when calculated on the specified input graph. The single value statistics are stored in sample_graphs/pkt-stats.stats, and that file lists where to find any features that create a vector (or more) of data. Note that without BOOST, distance-based features may not be available.

  • ./bin/graph_stats -i ./sample_graphs/1dc.64.dimacs -t dimacs -p ./sample_graphs/pkt-stats -m edge_density,degree_dist,global_cc,avg_cc,assortativity,eccentricity,expansion,avg_shortest_path -r

More information on the output formats for the weighted independent set executables is in the README in max_wis.

Getting Help

To get help with or discuss INDDGO, join the mailing list at inddgo-info@googlegroups.com

Licensing

The INDDGO software suite is generally covered by the BSD 3-clause license found in LICENSE. The madness runtime snapshot is included under the terms found in madness/LICENSE. The SuperWrap functionality for interfacing with CHOLMOD from SuiteSparse is included under the terms found in lib_treed/SuperWrap_LICENSE.