This file briefly describes the input data and generators available at
DIMACS ftp site (dimacs.rutgers.edu). We will continue to collect
further information and strongly encourage you to contribute input
generators and benchmark instances.
I. N-body problems
* GENERATOR
pub/challenge3/n-body/generator
This directory contains an input generator for N-body problem. It can
generator uniform distributions, a Plummer model, or two nearby
Plummer models. This code is based on a generator by J. Barnes.
II. Graphs
* FORMATS
pub/challenge/graph/doc
Discussion of DIMACS Challenge graph format. See ccformat.tex for details.
pub/challenge/graph/translators
Translators for different grpah formats.
* INSTANCES
pub/challenge/graph/benchmarks/{clique,color}
Input graphs for clique and chromatic number problems (from Challenge
II). See contents.tex for details.
pub/dsj/{clique,chrom}
Similar data provided by David Johnson. See code.readme*, README for
details.
pub/dsj/partition
Input grpahs for partitioning problem.
* GENERATORS
pub/netflow/generators
This directory contains programs that generate networks and graphs.
Most are in the DIMACS format.
This Directory Contains:
universal.c : A very portable random number generator, as C-language
function calls. Read the in-line code.
matching/ : A directory of generators for matching problems.
network/ : A directory containing generators for network problems.
pub/netflow/generators/matching
This directory contains instance generators for matching problems.
asnmat.a : Awk program to convert DIMACS .asn format to
.edge format.
clusters.c : Generates points within a circle which are clustered
according to some input parameters. Documentation is
in code. To compile: cc clusters.c -lm
dcube.c : Generates points uniform within a d-dimensional cube.
Documentation is in the code.
hardcard.f : Generates (nongeometric) graphs which Gabow has shown
will be hard for Edmond's cardinality matching algorithm.
Provided by R. B. Mattingly. This is a Fortran program.
To compile: f77 hardcard.f
neighbor.c : Takes a graph in .geom format and a command line argument
k. Produces a graph in .edge format. Vertex i is has an
edge to vertices [i-k, i-1]. See the code for more
documentation.
NOTE: a version which includes the p line and which is
slightly more robust was installed July 26.
random.c : Generates a random undirected graph with m edges. Edge
weights are uniformly distributed within a specified range.
See the code for further documentation.
NOTE: the original version contains a bug. The fixed
version was installed July 22.
t.f : Generates a sequence of K one-connected triangles
in .edge format.
Written in Fortran. These graphs tend to generate
a lot of blossoms.
Contributed by N. Ritchey and B. Mattingly
tt.f : Generates a sequence of K tri-connected triangles
in .edge format.
Written in Fortran.
Contributed by N. Ritchey and B. Mattingly
fractals/ : Subdirectory containing generators of fractal-like instances,
in .geom format.