diff -r 50a153b08f07 -r 186aa53d2802 src/lemon/suurballe.h --- a/src/lemon/suurballe.h Thu Oct 07 17:21:27 2004 +0000 +++ b/src/lemon/suurballe.h Fri Oct 08 13:07:51 2004 +0000 @@ -68,14 +68,16 @@ typedef ConstMap ConstMap; - //Input const Graph& G; + Node s; + Node t; + //Auxiliary variables //This is the capacity map for the mincostflow problem ConstMap const1map; //This MinCostFlow instance will actually solve the problem - MinCostFlow mincost_flow; + MinCostFlow min_cost_flow; //Container to store found paths std::vector< std::vector > paths; @@ -83,39 +85,40 @@ public : - /// The constructor of the class. + /*! \brief The constructor of the class. - ///\param _G The directed graph the algorithm runs on. - ///\param _length The length (weight or cost) of the edges. - Suurballe(Graph& _G, LengthMap& _length) : G(_G), - const1map(1), mincost_flow(_G, _length, const1map){} + \param _G The directed graph the algorithm runs on. + \param _length The length (weight or cost) of the edges. + \param _s Source node. + \param _t Target node. + */ + Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) : + G(_G), s(_s), t(_t), const1map(1), + min_cost_flow(_G, _length, const1map, _s, _t) { } ///Runs the algorithm. ///Runs the algorithm. ///Returns k if there are at least k edge-disjoint paths from s to t. - ///Otherwise it returns the number of found edge-disjoint paths from s to t. + ///Otherwise it returns the number of edge-disjoint paths found + ///from s to t. /// - ///\param s The source node. - ///\param t The target node. ///\param k How many paths are we looking for? /// - int run(Node s, Node t, int k) { - - int i = mincost_flow.run(s,t,k); - + int run(int k) { + int i = min_cost_flow.run(k); //Let's find the paths //We put the paths into stl vectors (as an inner representation). //In the meantime we lose the information stored in 'reversed'. //We suppose the lengths to be positive now. - //We don't want to change the flow of mincost_flow, so we make a copy + //We don't want to change the flow of min_cost_flow, so we make a copy //The name here suggests that the flow has only 0/1 values. EdgeIntMap reversed(G); for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) - reversed[e] = mincost_flow.getFlow()[e]; + reversed[e] = min_cost_flow.getFlow()[e]; paths.clear(); //total_length=0; @@ -143,39 +146,32 @@ } - ///Returns the total length of the paths + ///Returns the total length of the paths. ///This function gives back the total length of the found paths. - ///\pre \ref run() must - ///be called before using this function. Length totalLength(){ - return mincost_flow.totalLength(); + return min_cost_flow.totalLength(); } ///Returns the found flow. ///This function returns a const reference to the EdgeMap \c flow. - ///\pre \ref run() must - ///be called before using this function. - const EdgeIntMap &getFlow() const { return mincost_flow.flow;} + const EdgeIntMap &getFlow() const { return min_cost_flow.flow;} /// Returns the optimal dual solution ///This function returns a const reference to the NodeMap ///\c potential (the dual solution). - /// \pre \ref run() must be called before using this function. - const EdgeIntMap &getPotential() const { return mincost_flow.potential;} + const EdgeIntMap &getPotential() const { return min_cost_flow.potential;} ///Checks whether the complementary slackness holds. ///This function checks, whether the given solution is optimal. - ///It should return true after calling \ref run() ///Currently this function only checks optimality, ///doesn't bother with feasibility ///It is meant for testing purposes. - /// bool checkComplementarySlackness(){ - return mincost_flow.checkComplementarySlackness(); + return min_cost_flow.checkComplementarySlackness(); } ///Read the found paths.