Combinatorial optimization in networks with Shared Risk Link Groups

This page provides a program implementing methods presented in [CPRV16] for solving the minimum color st-path, the pair of color disjoint st-paths and the minimum color st-cut problems in (multi-)colored graphs. It also implements algorithms to transform a multi-colored graph into a mono-color graph with as few colors of span>1 as possible.

The program is provided 'as is', with absolutely no warranty. It is written in Python and Cython to be used with the open-source mathematical software SageMath. It has been developped and used with Sagemath version 6.8 (stable release).

You may use and distribute this code, provided that you cite the paper describing our algorithms, [CPRV16]. Please let us know if you find the program useful, if you find a bug, or have any improvement.


  • Program: the archive contains a README file, the Python/Cython source code, and a set of colored-graphs.