falk-hueffner / color-coding Goto Github PK

This package contains the source code accompanying the paper

Falk Hüffner, Sebastian Wernicke, and Thomas Zichner:
Algorithm engineering for color-coding with applications to signaling
pathway detection.
Algorithmica, 52(2):114–132, 2008.
http://dx.doi.org/10.1007/s00453-007-9008-7
http://falk.hueffner.de/color-coding-algorithmica07.pdf

A slightly updated description is in the thesis

Falk Hüffner:
Algorithms and Experiments for Parameterized Approaches to Hard Graph Problems.
PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2007.
http://hueffner.de/falk/diss-hueffner07.pdf


Command line program
====================

It can solve two problems (see paper):

* Find minimum-weight paths of a prespecified length in a weighted
  undirected graph.
* Path queries.

The program is written in ISO C++. It has only been tested on Unix
systems, but should be portable to other systems. Sources can be
obtained at http://theinf1.informatik.uni-jena.de/colorcoding/. They
are distributed under the terms of the GNU General Public License
(GPL, see COPYING).

It has been tested on:

* Debian GNU/Linux (x86-64) with GNU g++ 4.3.5 and 4.4.5

Previous versions have been tested on:

* Debian GNU/Linux (i386) 3.1 with GNU g++ 3.3.5, 3.4.4, and 4.1.0
* Digital Unix 5.1 (Alpha) with GNU g++ 3.3.2 and DEC C++ V6.3-008
  (needs the "-std strict_ansi" option)
* Solaris 9 (UltraSPARC) with GNU g++ 4.0.2
* Windows XP/Cygwin 1.4

If you have the "make" utility (as any Unix system has), you can
compile with "make".

The program is called "colorcoding". By default, it reads a graph from
standard input and writes the paths found to standard output. The
graph format is a simple text format, where each line describes one
edge, given by its two endpoints and the edge weight separated by
whitespace:

v0 v1 0.32
v1 v2 1.22
v2 v0 0.01

Vertex names can be any combination of letters, digits, and _. Note
that this graph format cannot describe degree-0 vertices; however,
they are irrelevant for finding paths anyway.

The output is a set of (by default 100) paths of minimum weight in the
graph. Each line describes one path by giving its total weight and the
list of vertices. Example:

# ./colorcoding < example.graph 
1.73 10 3 5 4 7 2 1 6

There are many options that affect program behavior; see ./colorcoding -h
for a listing.

Version history
---------------

1.0	2006-05-10	initial release
1.1	2006-11-01	path query functionality added
1.1.1	2008-10-26	missing files added to .tar.gz
1.1.2	2010-08-13	add -w option
			add -L option
			fix some minor bugs

-- Falk Hüffner (http://hueffner.de/falk/)