#include <lemon/suurballe.h>
Graph | The directed graph type the algorithm runs on. | |
LengthMap | The type of the length map (values should be nonnegative). |
Public Member Functions | |
Suurballe (Graph &_G, LengthMap &_length, Node _s, Node _t) | |
The constructor of the class. | |
int | run (int k) |
Runs the algorithm. | |
Length | totalLength () |
Returns the total length of the paths. | |
const EdgeIntMap & | getFlow () const |
Returns the found flow. | |
const EdgeIntMap & | getPotential () const |
Returns the optimal dual solution. | |
bool | checkComplementarySlackness () |
Checks whether the complementary slackness holds. | |
template<typename Path> | |
void | getPath (Path &p, size_t j) |
Read the found paths. |
_G | The directed graph the algorithm runs on. | |
_length | The length (weight or cost) of the edges. | |
_s | Source node. | |
_t | Target node. |
int run | ( | int | k | ) | [inline] |
Runs the algorithm. Returns k if there are at least k edge-disjoint paths from s to t. Otherwise it returns the number of edge-disjoint paths found from s to t.
k | How many paths are we looking for? |
Length totalLength | ( | ) | [inline] |
This function gives back the total length of the found paths.
const EdgeIntMap& getFlow | ( | ) | const [inline] |
This function returns a const reference to the EdgeMap flow
.
const EdgeIntMap& getPotential | ( | ) | const [inline] |
This function returns a const reference to the NodeMap potential
(the dual solution).
bool checkComplementarySlackness | ( | ) | [inline] |
This function checks, whether the given solution is optimal. Currently this function only checks optimality, doesn't bother with feasibility. It is meant for testing purposes.
void getPath | ( | Path & | p, | |
size_t | j | |||
) | [inline] |
This function gives back the j-th
path in argument p. Assumes that run()
has been run and nothing has changed since then.
p
is constructed to be a path of graph G
. If j
is not less than the result of previous run
, then the result here will be an empty path (j
can be 0 as well).Path | The type of the path structure to put the result to (must meet lemon path concept). | |
p | The path to put the result to. | |
j | Which path you want to get from the found paths (in a real application you would get the found paths iteratively). |