Skip to content


Repository files navigation

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.

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.

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 They
are distributed under the terms of the GNU General Public License

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

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 (


No description, website, or topics provided.







No releases published


No packages published