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

- -c
*n* 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

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