# Changeset 623:7c1324b35d89 in lemon-1.2 for lemon

Ignore:
Timestamp:
04/25/09 02:12:41 (13 years ago)
Branch:
default
Phase:
public
Message:

Modify the interface of Suurballe (#266, #181)

• Move the parameters s and t from the constructor to the run() function. It makes the interface capable for multiple run(s,t,k) calls (possible improvement in the future) and it is more similar to Dijkstra.
• Simliarly init() and findFlow(k) were replaced by init(s) and findFlow(t,k). The separation of parameters s and t is for the future plans of supporting multiple targets with one source node. For more information see #181.
• LEMON_ASSERT for the Length type (check if it is integer).
• Doc improvements.
• Rearrange query functions.
• Extend test file.
File:
1 edited

Unmodified
Added
Removed
• ## lemon/suurballe.h

 r584 #include #include #include #include /// from a given source node to a given target node in a digraph. /// /// In fact, this implementation is the specialization of the /// \ref CapacityScaling "successive shortest path" algorithm. /// Note that this problem is a special case of the \ref min_cost_flow /// "minimum cost flow problem". This implementation is actually an /// efficient specialized version of the \ref CapacityScaling /// "Successive Shortest Path" algorithm directly for this problem. /// Therefore this class provides query functions for flow values and /// node potentials (the dual solution) just like the minimum cost flow /// algorithms. /// /// \tparam GR The digraph type the algorithm runs on. /// The default value is \c ListDigraph. /// \tparam LEN The type of the length (cost) map. /// The default value is Digraph::ArcMap. /// \tparam LEN The type of the length map. /// The default value is GR::ArcMap. /// /// \warning Length values should be \e non-negative \e integers. /// /// \note For finding node-disjoint paths this algorithm can be used /// with \ref SplitNodes. /// along with the \ref SplitNodes adaptor. #ifdef DOXYGEN template #else template < typename GR = ListDigraph, template < typename GR, typename LEN = typename GR::template ArcMap > #endif /// The type of the lengths. typedef typename LengthMap::Value Length; #ifdef DOXYGEN /// The type of the flow map. typedef GR::ArcMap FlowMap; /// The type of the potential map. typedef GR::NodeMap PotentialMap; #else /// The type of the flow map. typedef typename Digraph::template ArcMap FlowMap; /// The type of the potential map. typedef typename Digraph::template NodeMap PotentialMap; #endif /// The type of the path structures. typedef SimplePath Path; typedef SimplePath Path; private: /// \brief Special implementation of the 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. // ResidualDijkstra is a special implementation of the // Dijkstra algorithm for finding shortest paths in the // residual network with respect to the reduced arc lengths // and modifying the node potentials according to the // distance of the nodes. class ResidualDijkstra { /// Constructor. ResidualDijkstra( const Digraph &digraph, ResidualDijkstra( const Digraph &graph, const FlowMap &flow, const LengthMap &length, PredMap &pred, Node s, Node t ) : _graph(digraph), _flow(flow), _length(length), _potential(potential), _dist(digraph), _pred(pred), _s(s), _t(t) {} _graph(graph), _flow(flow), _length(length), _potential(potential), _dist(graph), _pred(pred), _s(s), _t(t) {} /// \brief Run the algorithm. It returns \c true if a path is found /// Constructor. /// /// \param digraph The digraph the algorithm runs on. /// \param graph The 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) {} Suurballe( const Digraph &graph, const LengthMap &length ) : _graph(graph), _length(length), _flow(0), _local_flow(false), _potential(0), _local_potential(false), _pred(graph) { LEMON_ASSERT(std::numeric_limits::is_integer, "The length type of Suurballe must be integer"); } /// Destructor. /// /// This function sets the flow map. /// /// The found flow contains only 0 and 1 values. It is the union of /// the found arc-disjoint paths. /// If it is not used before calling \ref run() or \ref init(), /// an instance will be allocated automatically. The destructor /// deallocates this automatically allocated map, of course. /// /// The found flow contains only 0 and 1 values, since it is the /// union of the found arc-disjoint paths. /// /// \return (*this) /// /// This function sets the potential map. /// /// The potentials provide the dual solution of the underlying /// minimum cost flow problem. /// If it is not used before calling \ref run() or \ref init(), /// an instance will be allocated automatically. The destructor /// deallocates this automatically allocated map, of course. /// /// The node potentials provide the dual solution of the underlying /// \ref min_cost_flow "minimum cost flow problem". /// /// \return (*this) /// This function runs the algorithm. /// /// \param s The source node. /// \param t The target node. /// \param k The number of paths to be found. /// /// arc-disjoint paths found. /// /// \note Apart from the return value, s.run(k) is just a /// shortcut of the following code. /// \note Apart from the return value, s.run(s, t, k) is /// just a shortcut of the following code. /// \code ///   s.init(); ///   s.findFlow(k); ///   s.init(s); ///   s.findFlow(t, k); ///   s.findPaths(); /// \endcode int run(int k = 2) { init(); findFlow(k); int run(const Node& s, const Node& t, int k = 2) { init(s); findFlow(t, k); findPaths(); return _path_num; /// /// This function initializes the algorithm. void init() { /// /// \param s The source node. void init(const Node& s) { _source = s; // Initialize maps if (!_flow) { 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 Execute the successive shortest path algorithm to find /// an optimal flow. } /// \brief Execute the algorithm to find an optimal flow. /// /// This function executes the successive shortest path algorithm to /// find a minimum cost flow, which is the union of \c k or less /// find a minimum cost flow, which is the union of \c k (or less) /// arc-disjoint paths. /// /// \param t The target node. /// \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 in the digraph. Otherwise it returns the number of /// arc-disjoint paths found. /// the source node to the given node \c t in the digraph. /// 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) { int findFlow(const Node& t, int k = 2) { _target = t; _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred, _source, _target ); // Find shortest paths _path_num = 0; /// \brief Compute the paths from the flow. /// /// This function computes the paths from the flow. /// This function computes the paths from the found minimum cost flow, /// which is the union of some arc-disjoint paths. /// /// \pre \ref init() and \ref findFlow() must be called before using /// this function. void findPaths() { // Create 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]; /// @{ /// \brief Return a const reference to the arc map storing the /// found flow. /// /// This function 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 \ref findFlow() must be called before using /// this function. const FlowMap& flowMap() const { return *_flow; } /// \brief Return a const reference to the node map storing the /// found potentials (the dual solution). /// /// This function 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 \ref findFlow() must be called before using /// this function. const PotentialMap& potentialMap() const { return *_potential; } /// \brief Return the flow on the given arc. /// /// This function 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 \ref findFlow() must be called before using /// this function. int flow(const Arc& arc) const { return (*_flow)[arc]; } /// \brief Return the potential of the given node. /// /// This function returns the potential of the given node. /// /// \pre \ref run() or \ref findFlow() must be called before using /// this function. Length potential(const Node& node) const { return (*_potential)[node]; } /// \brief Return the total length (cost) of the found paths (flow). /// /// This function returns the total length (cost) of the found paths /// (flow). The complexity of the function is O(e). /// \brief Return the total length of the found paths. /// /// This function returns the total length of the found paths, i.e. /// the total cost of the found flow. /// The complexity of the function is O(e). /// /// \pre \ref run() or \ref findFlow() must be called before using } /// \brief Return the flow value on the given arc. /// /// This function returns the flow value on the given arc. /// It is \c 1 if the arc is involved in one of the found arc-disjoint /// paths, otherwise it is \c 0. /// /// \pre \ref run() or \ref findFlow() must be called before using /// this function. int flow(const Arc& arc) const { return (*_flow)[arc]; } /// \brief Return a const reference to an arc map storing the /// found flow. /// /// This function returns a const reference to an arc map storing /// the flow that is the union of the found arc-disjoint paths. /// /// \pre \ref run() or \ref findFlow() must be called before using /// this function. const FlowMap& flowMap() const { return *_flow; } /// \brief Return the potential of the given node. /// /// This function returns the potential of the given node. /// The node potentials provide the dual solution of the /// underlying \ref min_cost_flow "minimum cost flow problem". /// /// \pre \ref run() or \ref findFlow() must be called before using /// this function. Length potential(const Node& node) const { return (*_potential)[node]; } /// \brief Return a const reference to a node map storing the /// found potentials (the dual solution). /// /// This function returns a const reference to a node map storing /// the found potentials that provide the dual solution of the /// underlying \ref min_cost_flow "minimum cost flow problem". /// /// \pre \ref run() or \ref findFlow() must be called before using /// this function. const PotentialMap& potentialMap() const { return *_potential; } /// \brief Return the number of the found paths. /// /// This function returns a const reference to the specified path. /// /// \param i The function returns the \c i-th path. /// \param i The function returns the i-th path. /// \c i must be between \c 0 and %pathNum()-1. ///
Note: See TracChangeset for help on using the changeset viewer.