1.1 --- a/lemon/suurballe.h Mon Oct 30 16:26:13 2006 +0000
1.2 +++ b/lemon/suurballe.h Mon Oct 30 17:22:14 2006 +0000
1.3 @@ -26,15 +26,15 @@
1.4
1.5 #include <lemon/maps.h>
1.6 #include <vector>
1.7 -#include <lemon/min_cost_flow.h>
1.8 +#include <lemon/ssp_min_cost_flow.h>
1.9
1.10 namespace lemon {
1.11
1.12 /// \addtogroup flowalgs
1.13 /// @{
1.14
1.15 - ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
1.16 - /// of minimal total length
1.17 + ///\brief Implementation of an algorithm for finding k edge-disjoint
1.18 + /// paths between 2 nodes of minimal total length
1.19 ///
1.20 /// The class \ref lemon::Suurballe implements
1.21 /// an algorithm for finding k edge-disjoint paths
1.22 @@ -49,7 +49,7 @@
1.23 ///\note It it questionable whether it is correct to call this method after
1.24 ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm
1.25 ///for finding minimum cost flows. In fact, this implementation just
1.26 - ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and
1.27 + ///wraps the SspMinCostFlow algorithms. The paper of both %Suurballe and
1.28 ///Edmonds-Karp published in 1972, therefore it is possibly right to
1.29 ///state that they are
1.30 ///independent results. Most frequently this special case is referred as
1.31 @@ -79,7 +79,7 @@
1.32 //This is the capacity map for the mincostflow problem
1.33 ConstMap const1map;
1.34 //This MinCostFlow instance will actually solve the problem
1.35 - MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
1.36 + SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
1.37
1.38 //Container to store found paths
1.39 std::vector< std::vector<Edge> > paths;
1.40 @@ -87,25 +87,24 @@
1.41 public :
1.42
1.43
1.44 - /*! \brief The constructor of the class.
1.45 -
1.46 - \param _G The directed graph the algorithm runs on.
1.47 - \param _length The length (weight or cost) of the edges.
1.48 - \param _s Source node.
1.49 - \param _t Target node.
1.50 - */
1.51 + /// \brief The constructor of the class.
1.52 + ///
1.53 + /// \param _G The directed graph the algorithm runs on.
1.54 + /// \param _length The length (weight or cost) of the edges.
1.55 + /// \param _s Source node.
1.56 + /// \param _t Target node.
1.57 Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) :
1.58 G(_G), s(_s), t(_t), const1map(1),
1.59 min_cost_flow(_G, _length, const1map, _s, _t) { }
1.60
1.61 - ///Runs the algorithm.
1.62 -
1.63 - ///Runs the algorithm.
1.64 - ///Returns k if there are at least k edge-disjoint paths from s to t.
1.65 - ///Otherwise it returns the number of edge-disjoint paths found
1.66 - ///from s to t.
1.67 + /// \brief Runs the algorithm.
1.68 ///
1.69 - ///\param k How many paths are we looking for?
1.70 + /// Runs the algorithm.
1.71 + /// Returns k if there are at least k edge-disjoint paths from s to t.
1.72 + /// Otherwise it returns the number of edge-disjoint paths found
1.73 + /// from s to t.
1.74 + ///
1.75 + /// \param k How many paths are we looking for?
1.76 ///
1.77 int run(int k) {
1.78 int i = min_cost_flow.run(k);
1.79 @@ -144,46 +143,49 @@
1.80 }
1.81
1.82
1.83 - ///Returns the total length of the paths.
1.84 -
1.85 - ///This function gives back the total length of the found paths.
1.86 + /// \brief Returns the total length of the paths.
1.87 + ///
1.88 + /// This function gives back the total length of the found paths.
1.89 Length totalLength(){
1.90 return min_cost_flow.totalLength();
1.91 }
1.92
1.93 - ///Returns the found flow.
1.94 -
1.95 - ///This function returns a const reference to the EdgeMap \c flow.
1.96 + /// \brief Returns the found flow.
1.97 + ///
1.98 + /// This function returns a const reference to the EdgeMap \c flow.
1.99 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;}
1.100
1.101 - /// Returns the optimal dual solution
1.102 -
1.103 - ///This function returns a const reference to the NodeMap
1.104 - ///\c potential (the dual solution).
1.105 + /// \brief Returns the optimal dual solution
1.106 + ///
1.107 + /// This function returns a const reference to the NodeMap \c
1.108 + /// potential (the dual solution).
1.109 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
1.110
1.111 - ///Checks whether the complementary slackness holds.
1.112 -
1.113 - ///This function checks, whether the given solution is optimal.
1.114 - ///Currently this function only checks optimality,
1.115 - ///doesn't bother with feasibility.
1.116 - ///It is meant for testing purposes.
1.117 + /// \brief Checks whether the complementary slackness holds.
1.118 + ///
1.119 + /// This function checks, whether the given solution is optimal.
1.120 + /// Currently this function only checks optimality, doesn't bother
1.121 + /// with feasibility. It is meant for testing purposes.
1.122 bool checkComplementarySlackness(){
1.123 return min_cost_flow.checkComplementarySlackness();
1.124 }
1.125
1.126 - ///Read the found paths.
1.127 -
1.128 - ///This function gives back the \c j-th path in argument p.
1.129 - ///Assumes that \c run() has been run and nothing has changed since then.
1.130 - /// \warning It is assumed that \c p is constructed to
1.131 - ///be a path of graph \c G.
1.132 - ///If \c j is not less than the result of previous \c run,
1.133 - ///then the result here will be an empty path (\c j can be 0 as well).
1.134 + /// \brief Read the found paths.
1.135 ///
1.136 - ///\param Path The type of the path structure to put the result to (must meet lemon path concept).
1.137 - ///\param p The path to put the result to.
1.138 - ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively).
1.139 + /// This function gives back the \c j-th path in argument p.
1.140 + /// Assumes that \c run() has been run and nothing has changed
1.141 + /// since then.
1.142 + ///
1.143 + /// \warning It is assumed that \c p is constructed to be a path
1.144 + /// of graph \c G. If \c j is not less than the result of
1.145 + /// previous \c run, then the result here will be an empty path
1.146 + /// (\c j can be 0 as well).
1.147 + ///
1.148 + /// \param Path The type of the path structure to put the result
1.149 + /// to (must meet lemon path concept).
1.150 + /// \param p The path to put the result to.
1.151 + /// \param j Which path you want to get from the found paths (in a
1.152 + /// real application you would get the found paths iteratively).
1.153 template<typename Path>
1.154 void getPath(Path& p, size_t j){
1.155