SPUL: Shortest Path with Unique Labels


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


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


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


Tom Kamphans, Michael Stelzer


Sándor Fekete, Tom Kamphans, Michael Stelzer
Shortest Paths with Pairwise-Distinct Edge Labels: Finding Biochemical Pathways in Metabolic Networks
Technical Report, arXiv:1012.5024v1

Michael Stelzer, Jibin Sun, Tom Kamphans, Sándor P. Fekete, An-Ping Zeng
An extended bioreaction database that significantly improves reconstruction and analysis of genome-scale metabolic networks
Integrative Biology 3(11), pp. 1071-1086, 2011.

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