diff options
Diffstat (limited to 'extern/quadriflow/3rd/lemon-1.3.1/lemon/suurballe.h')
| -rw-r--r-- | extern/quadriflow/3rd/lemon-1.3.1/lemon/suurballe.h | 776 |
1 files changed, 776 insertions, 0 deletions
diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/suurballe.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/suurballe.h new file mode 100644 index 00000000000..f1338a2948f --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/suurballe.h @@ -0,0 +1,776 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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 <limits> +#include <lemon/bin_heap.h> +#include <lemon/path.h> +#include <lemon/list_graph.h> +#include <lemon/dijkstra.h> +#include <lemon/maps.h> + +namespace lemon { + + /// \brief Default traits class of Suurballe algorithm. + /// + /// Default traits class of Suurballe algorithm. + /// \tparam GR The digraph type the algorithm runs on. + /// \tparam LEN The type of the length map. + /// The default value is <tt>GR::ArcMap<int></tt>. +#ifdef DOXYGEN + template <typename GR, typename LEN> +#else + template < typename GR, + typename LEN = typename GR::template ArcMap<int> > +#endif + struct SuurballeDefaultTraits + { + /// The type of the digraph. + typedef GR Digraph; + /// The type of the length map. + typedef LEN LengthMap; + /// The type of the lengths. + typedef typename LEN::Value Length; + /// The type of the flow map. + typedef typename GR::template ArcMap<int> FlowMap; + /// The type of the potential map. + typedef typename GR::template NodeMap<Length> PotentialMap; + + /// \brief The path type + /// + /// The type used for storing the found arc-disjoint paths. + /// It must conform to the \ref lemon::concepts::Path "Path" concept + /// and it must have an \c addBack() function. + typedef lemon::Path<Digraph> Path; + + /// The cross reference type used for the heap. + typedef typename GR::template NodeMap<int> HeapCrossRef; + + /// \brief The heap type used for internal Dijkstra computations. + /// + /// The type of the heap used for internal Dijkstra computations. + /// It must conform to the \ref lemon::concepts::Heap "Heap" concept + /// and its priority type must be \c Length. + typedef BinHeap<Length, HeapCrossRef> Heap; + }; + + /// \addtogroup shortest_path + /// @{ + + /// \brief 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 digraph. + /// + /// 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. + /// \tparam LEN The type of the length map. + /// The default value is <tt>GR::ArcMap<int></tt>. + /// + /// \warning Length values should be \e non-negative. + /// + /// \note For finding \e node-disjoint paths, this algorithm can be used + /// along with the \ref SplitNodes adaptor. +#ifdef DOXYGEN + template <typename GR, typename LEN, typename TR> +#else + template < typename GR, + typename LEN = typename GR::template ArcMap<int>, + typename TR = SuurballeDefaultTraits<GR, LEN> > +#endif + class Suurballe + { + TEMPLATE_DIGRAPH_TYPEDEFS(GR); + + typedef ConstMap<Arc, int> ConstArcMap; + typedef typename GR::template NodeMap<Arc> PredMap; + + public: + + /// The type of the digraph. + typedef typename TR::Digraph Digraph; + /// The type of the length map. + typedef typename TR::LengthMap LengthMap; + /// The type of the lengths. + typedef typename TR::Length Length; + + /// The type of the flow map. + typedef typename TR::FlowMap FlowMap; + /// The type of the potential map. + typedef typename TR::PotentialMap PotentialMap; + /// The type of the path structures. + typedef typename TR::Path Path; + /// The cross reference type used for the heap. + typedef typename TR::HeapCrossRef HeapCrossRef; + /// The heap type used for internal Dijkstra computations. + typedef typename TR::Heap Heap; + + /// The \ref lemon::SuurballeDefaultTraits "traits class" of the algorithm. + typedef TR Traits; + + private: + + // 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 + { + private: + + const Digraph &_graph; + const LengthMap &_length; + const FlowMap &_flow; + PotentialMap &_pi; + PredMap &_pred; + Node _s; + Node _t; + + PotentialMap _dist; + std::vector<Node> _proc_nodes; + + public: + + // Constructor + ResidualDijkstra(Suurballe &srb) : + _graph(srb._graph), _length(srb._length), + _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred), + _s(srb._s), _t(srb._t), _dist(_graph) {} + + // Run the algorithm and return true if a path is found + // from the source node to the target node. + bool run(int cnt) { + return cnt == 0 ? startFirst() : start(); + } + + private: + + // Execute the algorithm for the first time (the flow and potential + // functions have to be identically zero). + bool startFirst() { + HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); + Heap heap(heap_cross_ref); + heap.push(_s, 0); + _pred[_s] = INVALID; + _proc_nodes.clear(); + + // Process nodes + while (!heap.empty() && heap.top() != _t) { + Node u = heap.top(), v; + Length d = heap.prio(), dn; + _dist[u] = heap.prio(); + _proc_nodes.push_back(u); + heap.pop(); + + // Traverse outgoing arcs + for (OutArcIt e(_graph, u); e != INVALID; ++e) { + v = _graph.target(e); + switch(heap.state(v)) { + case Heap::PRE_HEAP: + heap.push(v, d + _length[e]); + _pred[v] = e; + break; + case Heap::IN_HEAP: + dn = d + _length[e]; + if (dn < heap[v]) { + heap.decrease(v, dn); + _pred[v] = e; + } + break; + case Heap::POST_HEAP: + break; + } + } + } + if (heap.empty()) return false; + + // Update potentials of processed nodes + Length t_dist = heap.prio(); + for (int i = 0; i < int(_proc_nodes.size()); ++i) + _pi[_proc_nodes[i]] = _dist[_proc_nodes[i]] - t_dist; + return true; + } + + // Execute the algorithm. + bool start() { + HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); + Heap heap(heap_cross_ref); + heap.push(_s, 0); + _pred[_s] = INVALID; + _proc_nodes.clear(); + + // Process nodes + while (!heap.empty() && heap.top() != _t) { + Node u = heap.top(), v; + Length d = heap.prio() + _pi[u], dn; + _dist[u] = heap.prio(); + _proc_nodes.push_back(u); + heap.pop(); + + // Traverse 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] - _pi[v]); + _pred[v] = e; + break; + case Heap::IN_HEAP: + dn = d + _length[e] - _pi[v]; + if (dn < heap[v]) { + heap.decrease(v, dn); + _pred[v] = e; + } + break; + case Heap::POST_HEAP: + break; + } + } + } + + // Traverse 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] - _pi[v]); + _pred[v] = e; + break; + case Heap::IN_HEAP: + dn = d - _length[e] - _pi[v]; + if (dn < heap[v]) { + heap.decrease(v, dn); + _pred[v] = e; + } + break; + case Heap::POST_HEAP: + break; + } + } + } + } + if (heap.empty()) return false; + + // Update potentials of processed nodes + Length t_dist = heap.prio(); + for (int i = 0; i < int(_proc_nodes.size()); ++i) + _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist; + return true; + } + + }; //class ResidualDijkstra + + public: + + /// \name Named Template Parameters + /// @{ + + template <typename T> + struct SetFlowMapTraits : public Traits { + typedef T FlowMap; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// \c FlowMap type. + /// + /// \ref named-templ-param "Named parameter" for setting + /// \c FlowMap type. + template <typename T> + struct SetFlowMap + : public Suurballe<GR, LEN, SetFlowMapTraits<T> > { + typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create; + }; + + template <typename T> + struct SetPotentialMapTraits : public Traits { + typedef T PotentialMap; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// \c PotentialMap type. + /// + /// \ref named-templ-param "Named parameter" for setting + /// \c PotentialMap type. + template <typename T> + struct SetPotentialMap + : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > { + typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create; + }; + + template <typename T> + struct SetPathTraits : public Traits { + typedef T Path; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// \c %Path type. + /// + /// \ref named-templ-param "Named parameter" for setting \c %Path type. + /// It must conform to the \ref lemon::concepts::Path "Path" concept + /// and it must have an \c addBack() function. + template <typename T> + struct SetPath + : public Suurballe<GR, LEN, SetPathTraits<T> > { + typedef Suurballe<GR, LEN, SetPathTraits<T> > Create; + }; + + template <typename H, typename CR> + struct SetHeapTraits : public Traits { + typedef H Heap; + typedef CR HeapCrossRef; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// \c Heap and \c HeapCrossRef types. + /// + /// \ref named-templ-param "Named parameter" for setting \c Heap + /// and \c HeapCrossRef types with automatic allocation. + /// They will be used for internal Dijkstra computations. + /// The heap type must conform to the \ref lemon::concepts::Heap "Heap" + /// concept and its priority type must be \c Length. + template <typename H, + typename CR = typename Digraph::template NodeMap<int> > + struct SetHeap + : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > { + typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create; + }; + + /// @} + + private: + + // The 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 _s; + // The target node + Node _t; + + // Container to store the found paths + std::vector<Path> _paths; + int _path_num; + + // The pred arc map + PredMap _pred; + + // Data for full init + PotentialMap *_init_dist; + PredMap *_init_pred; + bool _full_init; + + protected: + + Suurballe() {} + + public: + + /// \brief Constructor. + /// + /// Constructor. + /// + /// \param graph The digraph the algorithm runs on. + /// \param length The length (cost) values of the arcs. + Suurballe( const Digraph &graph, + const LengthMap &length ) : + _graph(graph), _length(length), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _pred(graph), + _init_dist(0), _init_pred(0) + {} + + /// Destructor. + ~Suurballe() { + if (_local_flow) delete _flow; + if (_local_potential) delete _potential; + delete _init_dist; + delete _init_pred; + } + + /// \brief Set the flow map. + /// + /// This function sets the flow map. + /// 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 <tt>(*this)</tt> + Suurballe& flowMap(FlowMap &map) { + if (_local_flow) { + delete _flow; + _local_flow = false; + } + _flow = ↦ + return *this; + } + + /// \brief Set the potential map. + /// + /// This function sets the potential map. + /// 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 <tt>(*this)</tt> + 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 need to execute the algorithm many times using the same + /// source node, then you may call fullInit() once and start() + /// for each target node.\n + /// If you only need the flow that is the union of the found + /// arc-disjoint paths, then you may call findFlow() instead of + /// start(). + + /// @{ + + /// \brief Run the algorithm. + /// + /// This function runs the algorithm. + /// + /// \param s The source node. + /// \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. + /// + /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is + /// just a shortcut of the following code. + /// \code + /// s.init(s); + /// s.start(t, k); + /// \endcode + int run(const Node& s, const Node& t, int k = 2) { + init(s); + start(t, k); + return _path_num; + } + + /// \brief Initialize the algorithm. + /// + /// This function initializes the algorithm with the given source node. + /// + /// \param s The source node. + void init(const Node& s) { + _s = s; + + // Initialize maps + if (!_flow) { + _flow = new FlowMap(_graph); + _local_flow = true; + } + if (!_potential) { + _potential = new PotentialMap(_graph); + _local_potential = true; + } + _full_init = false; + } + + /// \brief Initialize the algorithm and perform Dijkstra. + /// + /// This function initializes the algorithm and performs a full + /// Dijkstra search from the given source node. It makes consecutive + /// executions of \ref start() "start(t, k)" faster, since they + /// have to perform %Dijkstra only k-1 times. + /// + /// This initialization is usually worth using instead of \ref init() + /// if the algorithm is executed many times using the same source node. + /// + /// \param s The source node. + void fullInit(const Node& s) { + // Initialize maps + init(s); + if (!_init_dist) { + _init_dist = new PotentialMap(_graph); + } + if (!_init_pred) { + _init_pred = new PredMap(_graph); + } + + // Run a full Dijkstra + typename Dijkstra<Digraph, LengthMap> + ::template SetStandardHeap<Heap> + ::template SetDistMap<PotentialMap> + ::template SetPredMap<PredMap> + ::Create dijk(_graph, _length); + dijk.distMap(*_init_dist).predMap(*_init_pred); + dijk.run(s); + + _full_init = true; + } + + /// \brief Execute the algorithm. + /// + /// This function executes the algorithm. + /// + /// \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. + /// + /// \note Apart from the return value, <tt>s.start(t, k)</tt> is + /// just a shortcut of the following code. + /// \code + /// s.findFlow(t, k); + /// s.findPaths(); + /// \endcode + int start(const Node& t, int k = 2) { + findFlow(t, k); + findPaths(); + return _path_num; + } + + /// \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) + /// 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 + /// 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(const Node& t, int k = 2) { + _t = t; + ResidualDijkstra dijkstra(*this); + + // Initialization + for (ArcIt e(_graph); e != INVALID; ++e) { + (*_flow)[e] = 0; + } + if (_full_init) { + for (NodeIt n(_graph); n != INVALID; ++n) { + (*_potential)[n] = (*_init_dist)[n]; + } + Node u = _t; + Arc e; + while ((e = (*_init_pred)[u]) != INVALID) { + (*_flow)[e] = 1; + u = _graph.source(e); + } + _path_num = 1; + } else { + for (NodeIt n(_graph); n != INVALID; ++n) { + (*_potential)[n] = 0; + } + _path_num = 0; + } + + // Find shortest paths + while (_path_num < k) { + // Run Dijkstra + if (!dijkstra.run(_path_num)) break; + ++_path_num; + + // Set the flow along the found shortest path + Node u = _t; + 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 Compute the paths from the flow. + /// + /// This function computes arc-disjoint paths from the found minimum + /// cost flow, which is the union of them. + /// + /// \pre \ref init() and \ref findFlow() must be called before using + /// this function. + void findPaths() { + 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 = _s; + while (n != _t) { + 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 results of the algorithm can be obtained using these + /// functions. + /// \n The algorithm should be executed before using them. + + /// @{ + + /// \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(m). + /// + /// \pre \ref run() or \ref 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 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 the number of the found paths. + /// + /// \pre \ref run() or \ref findFlow() must be called before using + /// this function. + int pathNum() const { + return _path_num; + } + + /// \brief Return a const reference to the specified path. + /// + /// This function returns a const reference to the specified path. + /// + /// \param i The function returns the <tt>i</tt>-th path. + /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>. + /// + /// \pre \ref run() or \ref findPaths() must be called before using + /// this function. + const Path& path(int i) const { + return _paths[i]; + } + + /// @} + + }; //class Suurballe + + ///@} + +} //namespace lemon + +#endif //LEMON_SUURBALLE_H |