bdsullivan / inddgo Goto Github PK

Integrated Network Decomposition & Dynamic programming for Graph Optimization problems

License: Other

C++ 61.92% C 34.08% Shell 1.31% Objective-C 2.19% Python 0.07% CSS 0.27% Perl 0.08% R 0.08%

inddgo's Introduction

##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 [email protected]

##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.

inddgo's People

Contributors

Stargazers

Watchers

Forkers

xydinesh dagalindo jlothian zbhuang tdgoodrich cgroer dagalindotestorg csheremeta mfer mapleyustat dmitrybrown abitofalchemy mxmerz satyakisikdar

inddgo's Issues

Mac compilation

Default gcc (via xcode) is a modified 4.2.1. Edit README to note that -std=c++0x and -march=native flags are incompatible (and not needed). Also, no default fortran compiler - now that we don't distribute ARPACK, do we ever use the fortran compiler variables?

TD_NICE/knice algorithms very slow

While running td_stats, running the TD_NICE algorithm appears to be very slow, taking several orders of magnitude longer to complete than the other TD methods. Need to investigate why that is. Shows when running "td_stats -a"

is_edge crash

(moving from INDDGO-survey)

Looks like if you call is_edge and the indices are out of bounds for the size of the current graph, you get a segfault. Should do some bounds checking before even bothering to look at the neighbor list.

smbfactor.c compilation

UPDATE: Now respects CC variable, but still passes U_GNU_C flag. Is this necessary?

smbfactor.c compilation does not respect the compilers in CC variable, we may need to define two variables for CC and CXX

lib_graphd/src/Makefile, Line 6

%.o: $(METIS_PROG_DIR)/%.c
gcc $(INCLUDES) $(CFLAGS) -U__GNUC__ -c $<

gcc -I../inc/ -I/usr/local/include -I/tmp/work/d8w/smoky/metis-5.0.2//include -I/tmp/work/d8w/smoky/metis-5.0.2//libmetis -I/tmp/work/d8w/smoky/metis-5.0.2//GKlib -I/tmp/work/d8w/smoky/metis-5.0.2//programs -I/tmp/work/d8w/smoky/AMD//Include -I/tmp/work/d8w/smoky/AMD//../UFconfig -O3 -D__LOG_ENABLE__ -D__MADNESS__ -std=c++0x -Wno-strict-aliasing -Wno-deprecated -ffast-math -march=native -D__PARALLEL__ -D__OPENMP__ -fopenmp -DHAS_METIS -D_FILE_OFFSET_BITS=64 -DHAS_AMD -U__GNUC__ -c /tmp/work/d8w/smoky/metis-5.0.2//programs/smbfactor.c

UF_config -> SuiteSparse_config

Tim Davis has updated the name of his UFconfig software, and this needs to be reflected in thirdparty instructions, and sample makefiles.

Using make.inc.serial got error msg: ‘syscall’ was not declared in this scope

Hello All,
I did not see this error show up in earlier issues, does any one have a suggestion? I tried compiling on an Ubuntu system.

src/count-tri.cpp: In function ‘int main(int, char*)’:
src/count-tri.cpp:76:66: error: ‘syscall’ was not declared in this scope
printf("My TID: %ld running on CPU: %d\n", syscall(SYS_gettid), sched_getcpu());
make[1]: ** [src/count-tri.o] Error 1
make[1]: Leaving directory `/home/saguinag/Software/INDDGO/util'

empty libdir variables

Library linking fails under old gcc due to empty -L variables. Fix all LIB_DIR to include the -L in the variables (or check for empty in strings).

Edge Subdivision/MPI incompatibility

Test (in gtest) of edge_subdivision failed when compiled with MPI. This works when MPI is not used (with and without Boost and OpenMP). Not sure this function is safe for use with generic value for w. Assigned to Diego before any integration of code using this function can be merged into master.

Crashes with `-nice` strategy

INDDGO crashes on Ubuntu 16.04.1 LTS when called on the following dimacs file with -nice and any of -minmaxd, -amd, -beta, -bmf, -minf, or -mmd:

c dimacs graph
c written by concuss
p edge 4 4
e 1 2
e 1 3
e 1 4
e 2 3

The error message looks as follows:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector<bool>::_M_range_check: __n (which is 2004640752) >= this->size() (which is 4)
[1]    7208 abort (core dumped)  ~/INDDGO/bin/serial_wis -f ./broken-amd/g-16.dimacs -nice -amd

INDDGO also crashes on the following DIMACS file when called with -nice and any of -mind, -mmd, -minf, -bmf, -metmmd, -metnnd, -pktsort, or -amd:

c dimacs graph
c written by concuss
p edge 3 2
e 1 2
e 1 3

The error message looks as follows:

0000000000000004
0000000000000008
Fatal Error!
record_children_solutions:  Didn't find mask with zeroized bit??
Exiting
exception caught: :  Didn't find mask with zeroized bit??

unordered_map: old gcc

Update: unordered_map is in TR1 in older versions (pre 4.4) - can fix by changing #include to <tr1/unordered_map>. Update INSTALL file to give instructions?

In old gcc (4.2.1 on mac, specifically), unordered_map is not found and std=c++0x is unsupported.

gen_pkt crash

(moving from INDDGO-survey)
gen_pkt crashes if not all parameters are supplied; should warn instead:

9:21:30 (pts/4:bohr05.ccs.ornl.gov)% ./gen_pkt -t 1 -n 200 -k 25 -s 42
Fatal Error!
Failed to input viable parameters for n, k, p (25,200,-1)
Exiting
terminate called after throwing an instance of 'Graph::GraphException'
what(): Failed to input viable parameters for n, k, p (1341877296,4316936,745924384)

zsh: abort (core dumped) ./gen_pkt -t 1 -n 200 -k 25 -s 42
9:21:47 (pts/4:bohr05.ccs.ornl.gov)% ./gen_pkt -t 1 -n 200 -k 25 -s 42 -p 80

Generated random partial k-tree (200,25) in 0.010000 sec.
Writing file pkt.200.25.80_0.dimacs

Generalize create_largestcomponent_graph()

create_largestcomponent_graph() in GraphUtil takes in a VertexWeightedGraph, but does not appear to need this strict of a requirement.

Build failed since INDDGO/lib and INDDGO/bin is not found.

mpicxx -O3 -D__LOG_ENABLE__ -D__MADNESS__ -std=c++0x -Wno-strict-aliasing -Wno-deprecated -ffast-math -march=native -D__PARALLEL__ -D__OPENMP__ -fopenmp -DHAS_METIS -D_FILE_OFFSET_BITS=64 -DHAS_AMD ./src/weighted_ind_set.cpp ./src/main.cpp ./src/DPinfo.o /tmp/work/d8w/smoky/INDDGO/lib/libgraphd.a -I./inc -I/tmp/work/d8w/smoky/INDDGO/lib_graphd/inc -I/tmp/work/d8w/smoky/INDDGO/lib_treed/inc/ -I/tmp/work/d8w/smoky/metis-5.0.2//include -I/tmp/work/d8w/smoky/metis-5.0.2//libmetis -I/tmp/work/d8w/smoky/metis-5.0.2//GKlib -I/tmp/work/d8w/smoky/metis-5.0.2//programs -I/tmp/work/d8w/smoky/AMD//Include -I/tmp/work/d8w/smoky/UFconfig -I/tmp/work/d8w/smoky/INDDGO/uthash-1.9.3/src -I/tmp/work/d8w/smoky/INDDGO/madness/deploy/include -I/tmp/work/d8w/smoky/INDDGO/lib_ptreed/inc/ -L/tmp/work/d8w/smoky/AMD//Lib -L/tmp/work/d8w/smoky/INDDGO/madness/deploy/lib -L/tmp/work/d8w/smoky/metis-5.0.2/lib -L/tmp/work/d8w/smoky/parmetis-4.0.2/ -L/tmp/work/d8w/smoky/INDDGO/lib -L/tmp/work/d8w/smoky/INDDGO/lib_graphd/lib -L/tmp/work/d8w/smoky/INDDGO/lib_treed/lib -lm -lgraphd -ltreed -lamd -lMADworld -lpthread -lmetis -o /tmp/work/d8w/smoky/INDDGO/bin/serial_wis
/usr/bin/ld: cannot open output file /tmp/work/d8w/smoky/INDDGO/bin/serial_wis: No such file or directory

using random

doesn't seem to be needed in DimacsGraphWriter.cpp, but cannot be found on mac. can we remove?

METIS errors in GraphEO on MacOS 10.8

Errors when compiled with 64-bit METIS on MACOSX; complains about long long * to int* conversion in GraphEO. This is caused by using int* in INDDGO but idx_t* in METIS. INDDGO code should be revised to use idx_t for full compatibility.

Current workaround: compile METIS with 32 bit ints.

Separate TD functionality from DP/WIS

Create standalone executable (main function) for elimination ordering and tree decomposition related tasks, separate from weighted independent set code. Care should be taken to avoid code duplication; move functions needed by both from max_wis files to appropriate library.

CRITICAL: Metis_Node_ND failing

Discovered problem with metis-node-nd (-metnnd). Gives an error of "Input error. Incorrect ufactor." (subsequent core dump). This is not an issue specific to any given main (replicated with td_viz and serial_wis); failures in case of -gavril and -superetree options in conjuction. CRITICAL FIX.

Spacing >> for templates

Double >> in MadnessTable Processor.h fails under older versions of gcc without spaces. Need to go through and replace for backward compatibility.

gconvert

It's unclear what gconvert does. I don't see in the src code what intype and outype is. Is this meant to convert edge-list files to other graph types/formats? Or, is this suppose to convert a .tree file to some other format? It would help to list an example in the README file or when you type -h.

MAD_NUM_THREADS and initialize

In mad_main, our error checking on the environment variable occurs after the MADNESS initialize() call, so if this is not set, we could still crash out (or worse, build and get weird runtime results). Move the check up.

Makefiles: src recompile/efficiency

Update makefiles to avoid recompiling all source files for each executable e.g.:

MAD_WIS_SRC = ./src/MadnessTableProcessor.cpp ./src/mad_main.cpp ./src/weighted_ind_set.cpp src/PTD.cpp
madwis: $(SHAREDOBJ)

$(CC) $(CFLAGS) $(MAD_WIS_SRC) $(SHAREDOBJ) $(INC_DIR) $(LIB_DIR) $(LIBS) -o $(MAD_WIS_EXE)

becomes
MAD_WIS_OBJ = ./src/MadnessTableProcessor.o ./src/mad_main.o ./src/weighted_ind_set.o src/PTD.o

madwis: $(SHAREDOBJ) $(MAD_WIS_OBJ)

$(CC) $(CFLAGS) $(MAD_WIS_OBJ) $(SHAREDOBJ) $(INC_DIR) $(LIB_DIR) $(LIBS) -o $(MAD_WIS_EXE)

LDFLAGS

Is not being used in our link steps. By default this is empty, but during some testing on Mac, we needed to use it, and it wasn't included. Add to commands for linking in all Makefiles.

HWMEM on mac

/proc/self/status doesn't seem to exist on Mac (at least Lion), giving a warning and value of -1 for the memory consumption. We should at least warn about this, and at best find a cross-platform solution.