Shortest Path with Unique Labels

NAME

SPUL: Shortest Path with Unique Labels

DESCRIPTION

SPUL is a tool to find shortest paths in edge-labeled graphs. The shortest path have the property that a label is passed at most once.
Path of this type can be used to analyze bioreaction databases, where nodes represent metabolites and edges represent reactions. Each edge is labeled with a reaction type. Biologically feasible shortest path should not use the same reaction type twice [Rosa da Silva, 2006].
Note that this problem is NP-hard by reduction from 3-SAT [Fekete et al.].

SYNOPSIS

spul [-c<n>] [-v] [-4] <file name> <start node> [<target node>]

If no target node given: find shortest path from the given start node to every other node otherwise: find shortest path from start node to target node.

Options:

-cn method for complete search (ignored if target node is given)
- -c0 no complete search
- -c1 save memory (default)
- -c2 save time (small instances only!)
-v verbose, more debug output
-4 four-column input (default: 3)
-b for testing: perform just a reachability test using BFS
-s for testing: skip preprocessing

The input file contains the graph. Each line in the input file stores one edge. The format is:

<start node>  <target node>  <edge label>

The node labels and the edge label are strings separated by whitespace. For compatibility reasons, the following format is also possible (with the command-line option -4):

<start node>  <target node>  <dummy>  <edge label>

Dummy is a string (without whitespace) and is simply ignored.

SOURCE CODE

Download source code spul.cpp.

Compile with

g++ -O2 -g0 -o sp sp.cpp

For large instances, use (if the platform supports this)

g++ -m64 -O2 -g0 -o sp sp.cpp

AUTHORS

Tom Kamphans, Michael Stelzer

REFERENCES

Sándor Fekete, Tom Kamphans, Michael Stelzer, Jibin Sun, An-Ping Zeng
Methods for Analyzing Bioreaction Databases
submitted manuscript

An-Ping Zeng, Michael Stelzer, Jibin Sun
An Extended Bioreaction Database that Significantly Improves Reconstruction and Analysis of Genome-scale Metabolic Networks
submitted manuscript

M. Rosa da Silva
Bioinformatics tools for the visualization and structural analysis of metabolic networks
PhD thesis, TU Braunschweig, 2006.