# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1225219193 0
# Node ID 2f64c4a692a87056623c6fffafd76432806ee593
# Parent 956a29f3088780b83149718f6ae7756cb187d5fe
Port Suurballe algorithm from svn -r3512
diff -r 956a29f30887 -r 2f64c4a692a8 lemon/Makefile.am
--- a/lemon/Makefile.am Tue Oct 28 18:33:51 2008 +0100
+++ b/lemon/Makefile.am Tue Oct 28 18:39:53 2008 +0000
@@ -40,6 +40,7 @@
lemon/path.h \
lemon/random.h \
lemon/smart_graph.h \
+ lemon/suurballe.h \
lemon/time_measure.h \
lemon/tolerance.h \
lemon/unionfind.h
diff -r 956a29f30887 -r 2f64c4a692a8 lemon/suurballe.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/suurballe.h Tue Oct 28 18:39:53 2008 +0000
@@ -0,0 +1,499 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_SUURBALLE_H
+#define LEMON_SUURBALLE_H
+
+///\ingroup shortest_path
+///\file
+///\brief An algorithm for finding arc-disjoint paths between two
+/// nodes having minimum total length.
+
+#include <vector>
+#include <lemon/bin_heap.h>
+#include <lemon/path.h>
+
+namespace lemon {
+
+ /// \addtogroup shortest_path
+ /// @{
+
+ /// \brief Implementation of an algorithm for finding arc-disjoint
+ /// paths between two nodes having minimum total length.
+ ///
+ /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
+ /// finding arc-disjoint paths having minimum total length (cost)
+ /// from a given source node to a given target node in a directed
+ /// digraph.
+ ///
+ /// In fact, this implementation is the specialization of the
+ /// \ref CapacityScaling "successive shortest path" algorithm.
+ ///
+ /// \tparam Digraph The directed digraph type the algorithm runs on.
+ /// \tparam LengthMap The type of the length (cost) map.
+ ///
+ /// \warning Length values should be \e non-negative \e integers.
+ ///
+ /// \note For finding node-disjoint paths this algorithm can be used
+ /// with \ref SplitDigraphAdaptor.
+ ///
+ /// \author Attila Bernath and Peter Kovacs
+
+ template < typename Digraph,
+ typename LengthMap = typename Digraph::template ArcMap<int> >
+ class Suurballe
+ {
+ TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+ typedef typename LengthMap::Value Length;
+ typedef ConstMap<Arc, int> ConstArcMap;
+ typedef typename Digraph::template NodeMap<Arc> PredMap;
+
+ public:
+
+ /// The type of the flow map.
+ typedef typename Digraph::template ArcMap<int> FlowMap;
+ /// The type of the potential map.
+ typedef typename Digraph::template NodeMap<Length> PotentialMap;
+ /// The type of the path structures.
+ typedef SimplePath<Digraph> Path;
+
+ private:
+
+ /// \brief Special implementation of the \ref Dijkstra algorithm
+ /// for finding shortest paths in the residual network.
+ ///
+ /// \ref ResidualDijkstra is a special implementation of the
+ /// \ref Dijkstra algorithm for finding shortest paths in the
+ /// residual network of the digraph with respect to the reduced arc
+ /// lengths and modifying the node potentials according to the
+ /// distance of the nodes.
+ class ResidualDijkstra
+ {
+ typedef typename Digraph::template NodeMap<int> HeapCrossRef;
+ typedef BinHeap<Length, HeapCrossRef> Heap;
+
+ private:
+
+ // The directed digraph the algorithm runs on
+ const Digraph &_graph;
+
+ // The main maps
+ const FlowMap &_flow;
+ const LengthMap &_length;
+ PotentialMap &_potential;
+
+ // The distance map
+ PotentialMap _dist;
+ // The pred arc map
+ PredMap &_pred;
+ // The processed (i.e. permanently labeled) nodes
+ std::vector<Node> _proc_nodes;
+
+ Node _s;
+ Node _t;
+
+ public:
+
+ /// Constructor.
+ ResidualDijkstra( const Digraph &digraph,
+ const FlowMap &flow,
+ const LengthMap &length,
+ PotentialMap &potential,
+ PredMap &pred,
+ Node s, Node t ) :
+ _graph(digraph), _flow(flow), _length(length), _potential(potential),
+ _dist(digraph), _pred(pred), _s(s), _t(t) {}
+
+ /// \brief Runs the algorithm. Returns \c true if a path is found
+ /// from the source node to the target node.
+ bool run() {
+ HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
+ Heap heap(heap_cross_ref);
+ heap.push(_s, 0);
+ _pred[_s] = INVALID;
+ _proc_nodes.clear();
+
+ // Processing nodes
+ while (!heap.empty() && heap.top() != _t) {
+ Node u = heap.top(), v;
+ Length d = heap.prio() + _potential[u], nd;
+ _dist[u] = heap.prio();
+ heap.pop();
+ _proc_nodes.push_back(u);
+
+ // Traversing outgoing arcs
+ for (OutArcIt e(_graph, u); e != INVALID; ++e) {
+ if (_flow[e] == 0) {
+ v = _graph.target(e);
+ switch(heap.state(v)) {
+ case Heap::PRE_HEAP:
+ heap.push(v, d + _length[e] - _potential[v]);
+ _pred[v] = e;
+ break;
+ case Heap::IN_HEAP:
+ nd = d + _length[e] - _potential[v];
+ if (nd < heap[v]) {
+ heap.decrease(v, nd);
+ _pred[v] = e;
+ }
+ break;
+ case Heap::POST_HEAP:
+ break;
+ }
+ }
+ }
+
+ // Traversing incoming arcs
+ for (InArcIt e(_graph, u); e != INVALID; ++e) {
+ if (_flow[e] == 1) {
+ v = _graph.source(e);
+ switch(heap.state(v)) {
+ case Heap::PRE_HEAP:
+ heap.push(v, d - _length[e] - _potential[v]);
+ _pred[v] = e;
+ break;
+ case Heap::IN_HEAP:
+ nd = d - _length[e] - _potential[v];
+ if (nd < heap[v]) {
+ heap.decrease(v, nd);
+ _pred[v] = e;
+ }
+ break;
+ case Heap::POST_HEAP:
+ break;
+ }
+ }
+ }
+ }
+ if (heap.empty()) return false;
+
+ // Updating potentials of processed nodes
+ Length t_dist = heap.prio();
+ for (int i = 0; i < int(_proc_nodes.size()); ++i)
+ _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
+ return true;
+ }
+
+ }; //class ResidualDijkstra
+
+ private:
+
+ // The directed digraph the algorithm runs on
+ const Digraph &_graph;
+ // The length map
+ const LengthMap &_length;
+
+ // Arc map of the current flow
+ FlowMap *_flow;
+ bool _local_flow;
+ // Node map of the current potentials
+ PotentialMap *_potential;
+ bool _local_potential;
+
+ // The source node
+ Node _source;
+ // The target node
+ Node _target;
+
+ // Container to store the found paths
+ std::vector< SimplePath<Digraph> > paths;
+ int _path_num;
+
+ // The pred arc map
+ PredMap _pred;
+ // Implementation of the Dijkstra algorithm for finding augmenting
+ // shortest paths in the residual network
+ ResidualDijkstra *_dijkstra;
+
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ ///
+ /// \param digraph The directed digraph the algorithm runs on.
+ /// \param length The length (cost) values of the arcs.
+ /// \param s The source node.
+ /// \param t The target node.
+ Suurballe( const Digraph &digraph,
+ const LengthMap &length,
+ Node s, Node t ) :
+ _graph(digraph), _length(length), _flow(0), _local_flow(false),
+ _potential(0), _local_potential(false), _source(s), _target(t),
+ _pred(digraph) {}
+
+ /// Destructor.
+ ~Suurballe() {
+ if (_local_flow) delete _flow;
+ if (_local_potential) delete _potential;
+ delete _dijkstra;
+ }
+
+ /// \brief Sets the flow map.
+ ///
+ /// Sets the flow map.
+ ///
+ /// The found flow contains only 0 and 1 values. It is the union of
+ /// the found arc-disjoint paths.
+ ///
+ /// \return \c (*this)
+ Suurballe& flowMap(FlowMap &map) {
+ if (_local_flow) {
+ delete _flow;
+ _local_flow = false;
+ }
+ _flow = ↦
+ return *this;
+ }
+
+ /// \brief Sets the potential map.
+ ///
+ /// Sets the potential map.
+ ///
+ /// The potentials provide the dual solution of the underlying
+ /// minimum cost flow problem.
+ ///
+ /// \return \c (*this)
+ Suurballe& potentialMap(PotentialMap &map) {
+ if (_local_potential) {
+ delete _potential;
+ _local_potential = false;
+ }
+ _potential = ↦
+ return *this;
+ }
+
+ /// \name Execution control
+ /// The simplest way to execute the algorithm is to call the run()
+ /// function.
+ /// \n
+ /// If you only need the flow that is the union of the found
+ /// arc-disjoint paths, you may call init() and findFlow().
+
+ /// @{
+
+ /// \brief Runs the algorithm.
+ ///
+ /// Runs the algorithm.
+ ///
+ /// \param k The number of paths to be found.
+ ///
+ /// \return \c k if there are at least \c k arc-disjoint paths
+ /// from \c s to \c t. Otherwise it returns the number of
+ /// arc-disjoint paths found.
+ ///
+ /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
+ /// shortcut of the following code.
+ /// \code
+ /// s.init();
+ /// s.findFlow(k);
+ /// s.findPaths();
+ /// \endcode
+ int run(int k = 2) {
+ init();
+ findFlow(k);
+ findPaths();
+ return _path_num;
+ }
+
+ /// \brief Initializes the algorithm.
+ ///
+ /// Initializes the algorithm.
+ void init() {
+ // Initializing maps
+ if (!_flow) {
+ _flow = new FlowMap(_graph);
+ _local_flow = true;
+ }
+ if (!_potential) {
+ _potential = new PotentialMap(_graph);
+ _local_potential = true;
+ }
+ for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
+ for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
+
+ _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
+ *_potential, _pred,
+ _source, _target );
+ }
+
+ /// \brief Executes the successive shortest path algorithm to find
+ /// an optimal flow.
+ ///
+ /// Executes the successive shortest path algorithm to find a
+ /// minimum cost flow, which is the union of \c k or less
+ /// arc-disjoint paths.
+ ///
+ /// \return \c k if there are at least \c k arc-disjoint paths
+ /// from \c s to \c t. Otherwise it returns the number of
+ /// arc-disjoint paths found.
+ ///
+ /// \pre \ref init() must be called before using this function.
+ int findFlow(int k = 2) {
+ // Finding shortest paths
+ _path_num = 0;
+ while (_path_num < k) {
+ // Running Dijkstra
+ if (!_dijkstra->run()) break;
+ ++_path_num;
+
+ // Setting the flow along the found shortest path
+ Node u = _target;
+ Arc e;
+ while ((e = _pred[u]) != INVALID) {
+ if (u == _graph.target(e)) {
+ (*_flow)[e] = 1;
+ u = _graph.source(e);
+ } else {
+ (*_flow)[e] = 0;
+ u = _graph.target(e);
+ }
+ }
+ }
+ return _path_num;
+ }
+
+ /// \brief Computes the paths from the flow.
+ ///
+ /// Computes the paths from the flow.
+ ///
+ /// \pre \ref init() and \ref findFlow() must be called before using
+ /// this function.
+ void findPaths() {
+ // Creating the residual flow map (the union of the paths not
+ // found so far)
+ FlowMap res_flow(_graph);
+ for(ArcIt a(_graph);a!=INVALID;++a) res_flow[a]=(*_flow)[a];
+
+ paths.clear();
+ paths.resize(_path_num);
+ for (int i = 0; i < _path_num; ++i) {
+ Node n = _source;
+ while (n != _target) {
+ OutArcIt e(_graph, n);
+ for ( ; res_flow[e] == 0; ++e) ;
+ n = _graph.target(e);
+ paths[i].addBack(e);
+ res_flow[e] = 0;
+ }
+ }
+ }
+
+ /// @}
+
+ /// \name Query Functions
+ /// The result of the algorithm can be obtained using these
+ /// functions.
+ /// \n The algorithm should be executed before using them.
+
+ /// @{
+
+ /// \brief Returns a const reference to the arc map storing the
+ /// found flow.
+ ///
+ /// Returns a const reference to the arc map storing the flow that
+ /// is the union of the found arc-disjoint paths.
+ ///
+ /// \pre \ref run() or findFlow() must be called before using this
+ /// function.
+ const FlowMap& flowMap() const {
+ return *_flow;
+ }
+
+ /// \brief Returns a const reference to the node map storing the
+ /// found potentials (the dual solution).
+ ///
+ /// Returns a const reference to the node map storing the found
+ /// potentials that provide the dual solution of the underlying
+ /// minimum cost flow problem.
+ ///
+ /// \pre \ref run() or findFlow() must be called before using this
+ /// function.
+ const PotentialMap& potentialMap() const {
+ return *_potential;
+ }
+
+ /// \brief Returns the flow on the given arc.
+ ///
+ /// Returns the flow on the given arc.
+ /// It is \c 1 if the arc is involved in one of the found paths,
+ /// otherwise it is \c 0.
+ ///
+ /// \pre \ref run() or findFlow() must be called before using this
+ /// function.
+ int flow(const Arc& arc) const {
+ return (*_flow)[arc];
+ }
+
+ /// \brief Returns the potential of the given node.
+ ///
+ /// Returns the potential of the given node.
+ ///
+ /// \pre \ref run() or findFlow() must be called before using this
+ /// function.
+ Length potential(const Node& node) const {
+ return (*_potential)[node];
+ }
+
+ /// \brief Returns the total length (cost) of the found paths (flow).
+ ///
+ /// Returns the total length (cost) of the found paths (flow).
+ /// The complexity of the function is \f$ O(e) \f$.
+ ///
+ /// \pre \ref run() or findFlow() must be called before using this
+ /// function.
+ Length totalLength() const {
+ Length c = 0;
+ for (ArcIt e(_graph); e != INVALID; ++e)
+ c += (*_flow)[e] * _length[e];
+ return c;
+ }
+
+ /// \brief Returns the number of the found paths.
+ ///
+ /// Returns the number of the found paths.
+ ///
+ /// \pre \ref run() or findFlow() must be called before using this
+ /// function.
+ int pathNum() const {
+ return _path_num;
+ }
+
+ /// \brief Returns a const reference to the specified path.
+ ///
+ /// Returns a const reference to the specified path.
+ ///
+ /// \param i The function returns the \c i-th path.
+ /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
+ ///
+ /// \pre \ref run() or findPaths() must be called before using this
+ /// function.
+ Path path(int i) const {
+ return paths[i];
+ }
+
+ /// @}
+
+ }; //class Suurballe
+
+ ///@}
+
+} //namespace lemon
+
+#endif //LEMON_SUURBALLE_H
diff -r 956a29f30887 -r 2f64c4a692a8 test/Makefile.am
--- a/test/Makefile.am Tue Oct 28 18:33:51 2008 +0100
+++ b/test/Makefile.am Tue Oct 28 18:39:53 2008 +0000
@@ -1,5 +1,6 @@
EXTRA_DIST += \
- test/CMakeLists.txt
+ test/CMakeLists.txt \
+ test/min_cost_flow_test.lgf
noinst_HEADERS += \
test/graph_test.h \
@@ -22,6 +23,7 @@
test/max_matching_test \
test/random_test \
test/path_test \
+ test/suurballe_test \
test/test_tools_fail \
test/test_tools_pass \
test/time_measure_test \
@@ -45,6 +47,7 @@
test_maps_test_SOURCES = test/maps_test.cc
test_max_matching_test_SOURCES = test/max_matching_test.cc
test_path_test_SOURCES = test/path_test.cc
+test_suurballe_test_SOURCES = test/suurballe_test.cc
test_random_test_SOURCES = test/random_test.cc
test_test_tools_fail_SOURCES = test/test_tools_fail.cc
test_test_tools_pass_SOURCES = test/test_tools_pass.cc
diff -r 956a29f30887 -r 2f64c4a692a8 test/min_cost_flow_test.lgf
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/min_cost_flow_test.lgf Tue Oct 28 18:39:53 2008 +0000
@@ -0,0 +1,44 @@
+@nodes
+label supply1 supply2 supply3
+1 0 20 27
+2 0 -4 0
+3 0 0 0
+4 0 0 0
+5 0 9 0
+6 0 -6 0
+7 0 0 0
+8 0 0 0
+9 0 3 0
+10 0 -2 0
+11 0 0 0
+12 0 -20 -27
+
+@arcs
+ cost capacity lower1 lower2
+1 2 70 11 0 8
+1 3 150 3 0 1
+1 4 80 15 0 2
+2 8 80 12 0 0
+3 5 140 5 0 3
+4 6 60 10 0 1
+4 7 80 2 0 0
+4 8 110 3 0 0
+5 7 60 14 0 0
+5 11 120 12 0 0
+6 3 0 3 0 0
+6 9 140 4 0 0
+6 10 90 8 0 0
+7 1 30 5 0 0
+8 12 60 16 0 4
+9 12 50 6 0 0
+10 12 70 13 0 5
+10 2 100 7 0 0
+10 7 60 10 0 0
+11 10 20 14 0 6
+12 11 30 10 0 0
+
+@attributes
+source 1
+target 12
+
+@end
diff -r 956a29f30887 -r 2f64c4a692a8 test/suurballe_test.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/suurballe_test.cc Tue Oct 28 18:39:53 2008 +0000
@@ -0,0 +1,160 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <iostream>
+#include <fstream>
+
+#include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/path.h>
+#include <lemon/suurballe.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+// Checks the feasibility of the flow
+template <typename Digraph, typename FlowMap>
+bool checkFlow( const Digraph& gr, const FlowMap& flow,
+ typename Digraph::Node s, typename Digraph::Node t,
+ int value )
+{
+ TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+ for (ArcIt e(gr); e != INVALID; ++e)
+ if (!(flow[e] == 0 || flow[e] == 1)) return false;
+
+ for (NodeIt n(gr); n != INVALID; ++n) {
+ int sum = 0;
+ for (OutArcIt e(gr, n); e != INVALID; ++e)
+ sum += flow[e];
+ for (InArcIt e(gr, n); e != INVALID; ++e)
+ sum -= flow[e];
+ if (n == s && sum != value) return false;
+ if (n == t && sum != -value) return false;
+ if (n != s && n != t && sum != 0) return false;
+ }
+
+ return true;
+}
+
+// Checks the optimalitiy of the flow
+template < typename Digraph, typename CostMap,
+ typename FlowMap, typename PotentialMap >
+bool checkOptimality( const Digraph& gr, const CostMap& cost,
+ const FlowMap& flow, const PotentialMap& pi )
+{
+ // Checking the Complementary Slackness optimality condition
+ TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+ bool opt = true;
+ for (ArcIt e(gr); e != INVALID; ++e) {
+ typename CostMap::Value red_cost =
+ cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
+ opt = (flow[e] == 0 && red_cost >= 0) ||
+ (flow[e] == 1 && red_cost <= 0);
+ if (!opt) break;
+ }
+ return opt;
+}
+
+// Checks a path
+template < typename Digraph, typename Path >
+bool checkPath( const Digraph& gr, const Path& path,
+ typename Digraph::Node s, typename Digraph::Node t)
+{
+ // Checking the Complementary Slackness optimality condition
+ TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+ Node n = s;
+ for (int i = 0; i < path.length(); ++i) {
+ if (gr.source(path.nth(i)) != n) return false;
+ n = gr.target(path.nth(i));
+ }
+ return n == t;
+}
+
+
+int main()
+{
+ DIGRAPH_TYPEDEFS(ListDigraph);
+
+ // Reading the test digraph
+ ListDigraph digraph;
+ ListDigraph::ArcMap<int> length(digraph);
+ Node source, target;
+
+ std::string fname;
+ if(getenv("srcdir"))
+ fname = std::string(getenv("srcdir"));
+ else fname = ".";
+ fname += "/test/min_cost_flow_test.lgf";
+
+ std::ifstream input(fname.c_str());
+ check(input, "Input file '" << fname << "' not found");
+ DigraphReader<ListDigraph>(digraph, input).
+ arcMap("cost", length).
+ node("source", source).
+ node("target", target).
+ run();
+ input.close();
+
+ // Finding 2 paths
+ {
+ Suurballe<ListDigraph> suurballe(digraph, length, source, target);
+ check(suurballe.run(2) == 2, "Wrong number of paths");
+ check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
+ "The flow is not feasible");
+ check(suurballe.totalLength() == 510, "The flow is not optimal");
+ check(checkOptimality(digraph, length, suurballe.flowMap(),
+ suurballe.potentialMap()),
+ "Wrong potentials");
+ for (int i = 0; i < suurballe.pathNum(); ++i)
+ check(checkPath(digraph, suurballe.path(i), source, target),
+ "Wrong path");
+ }
+
+ // Finding 3 paths
+ {
+ Suurballe<ListDigraph> suurballe(digraph, length, source, target);
+ check(suurballe.run(3) == 3, "Wrong number of paths");
+ check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
+ "The flow is not feasible");
+ check(suurballe.totalLength() == 1040, "The flow is not optimal");
+ check(checkOptimality(digraph, length, suurballe.flowMap(),
+ suurballe.potentialMap()),
+ "Wrong potentials");
+ for (int i = 0; i < suurballe.pathNum(); ++i)
+ check(checkPath(digraph, suurballe.path(i), source, target),
+ "Wrong path");
+ }
+
+ // Finding 5 paths (only 3 can be found)
+ {
+ Suurballe<ListDigraph> suurballe(digraph, length, source, target);
+ check(suurballe.run(5) == 3, "Wrong number of paths");
+ check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
+ "The flow is not feasible");
+ check(suurballe.totalLength() == 1040, "The flow is not optimal");
+ check(checkOptimality(digraph, length, suurballe.flowMap(),
+ suurballe.potentialMap()),
+ "Wrong potentials");
+ for (int i = 0; i < suurballe.pathNum(); ++i)
+ check(checkPath(digraph, suurballe.path(i), source, target),
+ "Wrong path");
+ }
+
+ return 0;
+}