1.1 --- a/lemon/min_cost_arborescence.h Fri Apr 24 12:12:14 2009 +0100
1.2 +++ b/lemon/min_cost_arborescence.h Sun Apr 26 16:44:53 2009 +0200
1.3 @@ -36,7 +36,7 @@
1.4 ///
1.5 /// Default traits class for MinCostArborescence class.
1.6 /// \param GR Digraph type.
1.7 - /// \param CM Type of cost map.
1.8 + /// \param CM Type of the cost map.
1.9 template <class GR, class CM>
1.10 struct MinCostArborescenceDefaultTraits{
1.11
1.12 @@ -46,7 +46,7 @@
1.13 /// \brief The type of the map that stores the arc costs.
1.14 ///
1.15 /// The type of the map that stores the arc costs.
1.16 - /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.17 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.18 typedef CM CostMap;
1.19
1.20 /// \brief The value type of the costs.
1.21 @@ -58,23 +58,26 @@
1.22 /// arborescence.
1.23 ///
1.24 /// The type of the map that stores which arcs are in the
1.25 - /// arborescence. It must meet the \ref concepts::WriteMap
1.26 - /// "WriteMap" concept. Initially it will be set to false on each
1.27 - /// arc. After it will set all arborescence arcs once.
1.28 + /// arborescence. It must conform to the \ref concepts::WriteMap
1.29 + /// "WriteMap" concept, and its value type must be \c bool
1.30 + /// (or convertible). Initially it will be set to \c false on each
1.31 + /// arc, then it will be set on each arborescence arc once.
1.32 typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
1.33
1.34 /// \brief Instantiates a \c ArborescenceMap.
1.35 ///
1.36 /// This function instantiates a \c ArborescenceMap.
1.37 - /// \param digraph is the graph, to which we would like to
1.38 - /// calculate the \c ArborescenceMap.
1.39 + /// \param digraph The digraph to which we would like to calculate
1.40 + /// the \c ArborescenceMap.
1.41 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
1.42 return new ArborescenceMap(digraph);
1.43 }
1.44
1.45 /// \brief The type of the \c PredMap
1.46 ///
1.47 - /// The type of the \c PredMap. It is a node map with an arc value type.
1.48 + /// The type of the \c PredMap. It must confrom to the
1.49 + /// \ref concepts::WriteMap "WriteMap" concept, and its value type
1.50 + /// must be the \c Arc type of the digraph.
1.51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.52
1.53 /// \brief Instantiates a \c PredMap.
1.54 @@ -92,32 +95,29 @@
1.55 ///
1.56 /// \brief Minimum Cost Arborescence algorithm class.
1.57 ///
1.58 - /// This class provides an efficient implementation of
1.59 + /// This class provides an efficient implementation of the
1.60 /// Minimum Cost Arborescence algorithm. The arborescence is a tree
1.61 /// which is directed from a given source node of the digraph. One or
1.62 - /// more sources should be given for the algorithm and it will calculate
1.63 - /// the minimum cost subgraph which are union of arborescences with the
1.64 + /// more sources should be given to the algorithm and it will calculate
1.65 + /// the minimum cost subgraph that is the union of arborescences with the
1.66 /// given sources and spans all the nodes which are reachable from the
1.67 /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
1.68 ///
1.69 - /// The algorithm provides also an optimal dual solution, therefore
1.70 + /// The algorithm also provides an optimal dual solution, therefore
1.71 /// the optimality of the solution can be checked.
1.72 ///
1.73 - /// \param GR The digraph type the algorithm runs on. The default value
1.74 - /// is \ref ListDigraph.
1.75 - /// \param CM This read-only ArcMap determines the costs of the
1.76 + /// \param GR The digraph type the algorithm runs on.
1.77 + /// \param CM A read-only arc map storing the costs of the
1.78 /// arcs. It is read once for each arc, so the map may involve in
1.79 - /// relatively time consuming process to compute the arc cost if
1.80 + /// relatively time consuming process to compute the arc costs if
1.81 /// it is necessary. The default map type is \ref
1.82 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
1.83 /// \param TR Traits class to set various data types used
1.84 /// by the algorithm. The default traits class is
1.85 /// \ref MinCostArborescenceDefaultTraits
1.86 - /// "MinCostArborescenceDefaultTraits<GR, CM>". See \ref
1.87 - /// MinCostArborescenceDefaultTraits for the documentation of a
1.88 - /// MinCostArborescence traits class.
1.89 + /// "MinCostArborescenceDefaultTraits<GR, CM>".
1.90 #ifndef DOXYGEN
1.91 - template <typename GR = ListDigraph,
1.92 + template <typename GR,
1.93 typename CM = typename GR::template ArcMap<int>,
1.94 typename TR =
1.95 MinCostArborescenceDefaultTraits<GR, CM> >
1.96 @@ -127,7 +127,8 @@
1.97 class MinCostArborescence {
1.98 public:
1.99
1.100 - /// The traits.
1.101 + /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
1.102 + /// of the algorithm.
1.103 typedef TR Traits;
1.104 /// The type of the underlying digraph.
1.105 typedef typename Traits::Digraph Digraph;
1.106 @@ -395,7 +396,7 @@
1.107 /// @{
1.108
1.109 template <class T>
1.110 - struct DefArborescenceMapTraits : public Traits {
1.111 + struct SetArborescenceMapTraits : public Traits {
1.112 typedef T ArborescenceMap;
1.113 static ArborescenceMap *createArborescenceMap(const Digraph &)
1.114 {
1.115 @@ -405,33 +406,40 @@
1.116 };
1.117
1.118 /// \brief \ref named-templ-param "Named parameter" for
1.119 - /// setting ArborescenceMap type
1.120 + /// setting \c ArborescenceMap type
1.121 ///
1.122 /// \ref named-templ-param "Named parameter" for setting
1.123 - /// ArborescenceMap type
1.124 + /// \c ArborescenceMap type.
1.125 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
1.126 + /// and its value type must be \c bool (or convertible).
1.127 + /// Initially it will be set to \c false on each arc,
1.128 + /// then it will be set on each arborescence arc once.
1.129 template <class T>
1.130 - struct DefArborescenceMap
1.131 + struct SetArborescenceMap
1.132 : public MinCostArborescence<Digraph, CostMap,
1.133 - DefArborescenceMapTraits<T> > {
1.134 + SetArborescenceMapTraits<T> > {
1.135 };
1.136
1.137 template <class T>
1.138 - struct DefPredMapTraits : public Traits {
1.139 + struct SetPredMapTraits : public Traits {
1.140 typedef T PredMap;
1.141 static PredMap *createPredMap(const Digraph &)
1.142 {
1.143 LEMON_ASSERT(false, "PredMap is not initialized");
1.144 + return 0; // ignore warnings
1.145 }
1.146 };
1.147
1.148 /// \brief \ref named-templ-param "Named parameter" for
1.149 - /// setting PredMap type
1.150 + /// setting \c PredMap type
1.151 ///
1.152 /// \ref named-templ-param "Named parameter" for setting
1.153 - /// PredMap type
1.154 + /// \c PredMap type.
1.155 + /// It must meet the \ref concepts::WriteMap "WriteMap" concept,
1.156 + /// and its value type must be the \c Arc type of the digraph.
1.157 template <class T>
1.158 - struct DefPredMap
1.159 - : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
1.160 + struct SetPredMap
1.161 + : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
1.162 };
1.163
1.164 /// @}
1.165 @@ -464,9 +472,9 @@
1.166 return *this;
1.167 }
1.168
1.169 - /// \brief Sets the arborescence map.
1.170 + /// \brief Sets the predecessor map.
1.171 ///
1.172 - /// Sets the arborescence map.
1.173 + /// Sets the predecessor map.
1.174 /// \return <tt>(*this)</tt>
1.175 MinCostArborescence& predMap(PredMap& m) {
1.176 if (local_pred) {
1.177 @@ -477,159 +485,6 @@
1.178 return *this;
1.179 }
1.180
1.181 - /// \name Query Functions
1.182 - /// The result of the %MinCostArborescence algorithm can be obtained
1.183 - /// using these functions.\n
1.184 - /// Before the use of these functions,
1.185 - /// either run() or start() must be called.
1.186 -
1.187 - /// @{
1.188 -
1.189 - /// \brief Returns a reference to the arborescence map.
1.190 - ///
1.191 - /// Returns a reference to the arborescence map.
1.192 - const ArborescenceMap& arborescenceMap() const {
1.193 - return *_arborescence;
1.194 - }
1.195 -
1.196 - /// \brief Returns true if the arc is in the arborescence.
1.197 - ///
1.198 - /// Returns true if the arc is in the arborescence.
1.199 - /// \param arc The arc of the digraph.
1.200 - /// \pre \ref run() must be called before using this function.
1.201 - bool arborescence(Arc arc) const {
1.202 - return (*_pred)[_digraph->target(arc)] == arc;
1.203 - }
1.204 -
1.205 - /// \brief Returns a reference to the pred map.
1.206 - ///
1.207 - /// Returns a reference to the pred map.
1.208 - const PredMap& predMap() const {
1.209 - return *_pred;
1.210 - }
1.211 -
1.212 - /// \brief Returns the predecessor arc of the given node.
1.213 - ///
1.214 - /// Returns the predecessor arc of the given node.
1.215 - Arc pred(Node node) const {
1.216 - return (*_pred)[node];
1.217 - }
1.218 -
1.219 - /// \brief Returns the cost of the arborescence.
1.220 - ///
1.221 - /// Returns the cost of the arborescence.
1.222 - Value arborescenceValue() const {
1.223 - Value sum = 0;
1.224 - for (ArcIt it(*_digraph); it != INVALID; ++it) {
1.225 - if (arborescence(it)) {
1.226 - sum += (*_cost)[it];
1.227 - }
1.228 - }
1.229 - return sum;
1.230 - }
1.231 -
1.232 - /// \brief Indicates that a node is reachable from the sources.
1.233 - ///
1.234 - /// Indicates that a node is reachable from the sources.
1.235 - bool reached(Node node) const {
1.236 - return (*_node_order)[node] != -3;
1.237 - }
1.238 -
1.239 - /// \brief Indicates that a node is processed.
1.240 - ///
1.241 - /// Indicates that a node is processed. The arborescence path exists
1.242 - /// from the source to the given node.
1.243 - bool processed(Node node) const {
1.244 - return (*_node_order)[node] == -1;
1.245 - }
1.246 -
1.247 - /// \brief Returns the number of the dual variables in basis.
1.248 - ///
1.249 - /// Returns the number of the dual variables in basis.
1.250 - int dualNum() const {
1.251 - return _dual_variables.size();
1.252 - }
1.253 -
1.254 - /// \brief Returns the value of the dual solution.
1.255 - ///
1.256 - /// Returns the value of the dual solution. It should be
1.257 - /// equal to the arborescence value.
1.258 - Value dualValue() const {
1.259 - Value sum = 0;
1.260 - for (int i = 0; i < int(_dual_variables.size()); ++i) {
1.261 - sum += _dual_variables[i].value;
1.262 - }
1.263 - return sum;
1.264 - }
1.265 -
1.266 - /// \brief Returns the number of the nodes in the dual variable.
1.267 - ///
1.268 - /// Returns the number of the nodes in the dual variable.
1.269 - int dualSize(int k) const {
1.270 - return _dual_variables[k].end - _dual_variables[k].begin;
1.271 - }
1.272 -
1.273 - /// \brief Returns the value of the dual variable.
1.274 - ///
1.275 - /// Returns the the value of the dual variable.
1.276 - const Value& dualValue(int k) const {
1.277 - return _dual_variables[k].value;
1.278 - }
1.279 -
1.280 - /// \brief Lemon iterator for get a dual variable.
1.281 - ///
1.282 - /// Lemon iterator for get a dual variable. This class provides
1.283 - /// a common style lemon iterator which gives back a subset of
1.284 - /// the nodes.
1.285 - class DualIt {
1.286 - public:
1.287 -
1.288 - /// \brief Constructor.
1.289 - ///
1.290 - /// Constructor for get the nodeset of the variable.
1.291 - DualIt(const MinCostArborescence& algorithm, int variable)
1.292 - : _algorithm(&algorithm)
1.293 - {
1.294 - _index = _algorithm->_dual_variables[variable].begin;
1.295 - _last = _algorithm->_dual_variables[variable].end;
1.296 - }
1.297 -
1.298 - /// \brief Conversion to node.
1.299 - ///
1.300 - /// Conversion to node.
1.301 - operator Node() const {
1.302 - return _algorithm->_dual_node_list[_index];
1.303 - }
1.304 -
1.305 - /// \brief Increment operator.
1.306 - ///
1.307 - /// Increment operator.
1.308 - DualIt& operator++() {
1.309 - ++_index;
1.310 - return *this;
1.311 - }
1.312 -
1.313 - /// \brief Validity checking
1.314 - ///
1.315 - /// Checks whether the iterator is invalid.
1.316 - bool operator==(Invalid) const {
1.317 - return _index == _last;
1.318 - }
1.319 -
1.320 - /// \brief Validity checking
1.321 - ///
1.322 - /// Checks whether the iterator is valid.
1.323 - bool operator!=(Invalid) const {
1.324 - return _index != _last;
1.325 - }
1.326 -
1.327 - private:
1.328 - const MinCostArborescence* _algorithm;
1.329 - int _index, _last;
1.330 - };
1.331 -
1.332 - /// @}
1.333 -
1.334 /// \name Execution Control
1.335 /// The simplest way to execute the algorithm is to use
1.336 /// one of the member functions called \c run(...). \n
1.337 @@ -689,7 +544,7 @@
1.338 ///
1.339 /// \return The processed node.
1.340 ///
1.341 - /// \warning The queue must not be empty!
1.342 + /// \warning The queue must not be empty.
1.343 Node processNextNode() {
1.344 Node node = queue.back();
1.345 queue.pop_back();
1.346 @@ -712,7 +567,8 @@
1.347
1.348 /// \brief Returns the number of the nodes to be processed.
1.349 ///
1.350 - /// Returns the number of the nodes to be processed.
1.351 + /// Returns the number of the nodes to be processed in the priority
1.352 + /// queue.
1.353 int queueSize() const {
1.354 return queue.size();
1.355 }
1.356 @@ -754,14 +610,170 @@
1.357 /// mca.addSource(s);
1.358 /// mca.start();
1.359 /// \endcode
1.360 - void run(Node node) {
1.361 + void run(Node s) {
1.362 init();
1.363 - addSource(node);
1.364 + addSource(s);
1.365 start();
1.366 }
1.367
1.368 ///@}
1.369
1.370 + /// \name Query Functions
1.371 + /// The result of the %MinCostArborescence algorithm can be obtained
1.372 + /// using these functions.\n
1.373 + /// Either run() or start() must be called before using them.
1.374 +
1.375 + /// @{
1.376 +
1.377 + /// \brief Returns the cost of the arborescence.
1.378 + ///
1.379 + /// Returns the cost of the arborescence.
1.380 + Value arborescenceCost() const {
1.381 + Value sum = 0;
1.382 + for (ArcIt it(*_digraph); it != INVALID; ++it) {
1.383 + if (arborescence(it)) {
1.384 + sum += (*_cost)[it];
1.385 + }
1.386 + }
1.387 + return sum;
1.388 + }
1.389 +
1.390 + /// \brief Returns \c true if the arc is in the arborescence.
1.391 + ///
1.392 + /// Returns \c true if the given arc is in the arborescence.
1.393 + /// \param arc An arc of the digraph.
1.394 + /// \pre \ref run() must be called before using this function.
1.395 + bool arborescence(Arc arc) const {
1.396 + return (*_pred)[_digraph->target(arc)] == arc;
1.397 + }
1.398 +
1.399 + /// \brief Returns a const reference to the arborescence map.
1.400 + ///
1.401 + /// Returns a const reference to the arborescence map.
1.402 + /// \pre \ref run() must be called before using this function.
1.403 + const ArborescenceMap& arborescenceMap() const {
1.404 + return *_arborescence;
1.405 + }
1.406 +
1.407 + /// \brief Returns the predecessor arc of the given node.
1.408 + ///
1.409 + /// Returns the predecessor arc of the given node.
1.410 + /// \pre \ref run() must be called before using this function.
1.411 + Arc pred(Node node) const {
1.412 + return (*_pred)[node];
1.413 + }
1.414 +
1.415 + /// \brief Returns a const reference to the pred map.
1.416 + ///
1.417 + /// Returns a const reference to the pred map.
1.418 + /// \pre \ref run() must be called before using this function.
1.419 + const PredMap& predMap() const {
1.420 + return *_pred;
1.421 + }
1.422 +
1.423 + /// \brief Indicates that a node is reachable from the sources.
1.424 + ///
1.425 + /// Indicates that a node is reachable from the sources.
1.426 + bool reached(Node node) const {
1.427 + return (*_node_order)[node] != -3;
1.428 + }
1.429 +
1.430 + /// \brief Indicates that a node is processed.
1.431 + ///
1.432 + /// Indicates that a node is processed. The arborescence path exists
1.433 + /// from the source to the given node.
1.434 + bool processed(Node node) const {
1.435 + return (*_node_order)[node] == -1;
1.436 + }
1.437 +
1.438 + /// \brief Returns the number of the dual variables in basis.
1.439 + ///
1.440 + /// Returns the number of the dual variables in basis.
1.441 + int dualNum() const {
1.442 + return _dual_variables.size();
1.443 + }
1.444 +
1.445 + /// \brief Returns the value of the dual solution.
1.446 + ///
1.447 + /// Returns the value of the dual solution. It should be
1.448 + /// equal to the arborescence value.
1.449 + Value dualValue() const {
1.450 + Value sum = 0;
1.451 + for (int i = 0; i < int(_dual_variables.size()); ++i) {
1.452 + sum += _dual_variables[i].value;
1.453 + }
1.454 + return sum;
1.455 + }
1.456 +
1.457 + /// \brief Returns the number of the nodes in the dual variable.
1.458 + ///
1.459 + /// Returns the number of the nodes in the dual variable.
1.460 + int dualSize(int k) const {
1.461 + return _dual_variables[k].end - _dual_variables[k].begin;
1.462 + }
1.463 +
1.464 + /// \brief Returns the value of the dual variable.
1.465 + ///
1.466 + /// Returns the the value of the dual variable.
1.467 + Value dualValue(int k) const {
1.468 + return _dual_variables[k].value;
1.469 + }
1.470 +
1.471 + /// \brief LEMON iterator for getting a dual variable.
1.472 + ///
1.473 + /// This class provides a common style LEMON iterator for getting a
1.474 + /// dual variable of \ref MinCostArborescence algorithm.
1.475 + /// It iterates over a subset of the nodes.
1.476 + class DualIt {
1.477 + public:
1.478 +
1.479 + /// \brief Constructor.
1.480 + ///
1.481 + /// Constructor for getting the nodeset of the dual variable
1.482 + /// of \ref MinCostArborescence algorithm.
1.483 + DualIt(const MinCostArborescence& algorithm, int variable)
1.484 + : _algorithm(&algorithm)
1.485 + {
1.486 + _index = _algorithm->_dual_variables[variable].begin;
1.487 + _last = _algorithm->_dual_variables[variable].end;
1.488 + }
1.489 +
1.490 + /// \brief Conversion to \c Node.
1.491 + ///
1.492 + /// Conversion to \c Node.
1.493 + operator Node() const {
1.494 + return _algorithm->_dual_node_list[_index];
1.495 + }
1.496 +
1.497 + /// \brief Increment operator.
1.498 + ///
1.499 + /// Increment operator.
1.500 + DualIt& operator++() {
1.501 + ++_index;
1.502 + return *this;
1.503 + }
1.504 +
1.505 + /// \brief Validity checking
1.506 + ///
1.507 + /// Checks whether the iterator is invalid.
1.508 + bool operator==(Invalid) const {
1.509 + return _index == _last;
1.510 + }
1.511 +
1.512 + /// \brief Validity checking
1.513 + ///
1.514 + /// Checks whether the iterator is valid.
1.515 + bool operator!=(Invalid) const {
1.516 + return _index != _last;
1.517 + }
1.518 +
1.519 + private:
1.520 + const MinCostArborescence* _algorithm;
1.521 + int _index, _last;
1.522 + };
1.523 +
1.524 + /// @}
1.525 +
1.526 };
1.527
1.528 /// \ingroup spantree
1.529 @@ -769,11 +781,12 @@
1.530 /// \brief Function type interface for MinCostArborescence algorithm.
1.531 ///
1.532 /// Function type interface for MinCostArborescence algorithm.
1.533 - /// \param digraph The Digraph that the algorithm runs on.
1.534 - /// \param cost The CostMap of the arcs.
1.535 - /// \param source The source of the arborescence.
1.536 - /// \retval arborescence The bool ArcMap which stores the arborescence.
1.537 - /// \return The cost of the arborescence.
1.538 + /// \param digraph The digraph the algorithm runs on.
1.539 + /// \param cost An arc map storing the costs.
1.540 + /// \param source The source node of the arborescence.
1.541 + /// \retval arborescence An arc map with \c bool (or convertible) value
1.542 + /// type that stores the arborescence.
1.543 + /// \return The total cost of the arborescence.
1.544 ///
1.545 /// \sa MinCostArborescence
1.546 template <typename Digraph, typename CostMap, typename ArborescenceMap>
1.547 @@ -782,11 +795,11 @@
1.548 typename Digraph::Node source,
1.549 ArborescenceMap& arborescence) {
1.550 typename MinCostArborescence<Digraph, CostMap>
1.551 - ::template DefArborescenceMap<ArborescenceMap>
1.552 + ::template SetArborescenceMap<ArborescenceMap>
1.553 ::Create mca(digraph, cost);
1.554 mca.arborescenceMap(arborescence);
1.555 mca.run(source);
1.556 - return mca.arborescenceValue();
1.557 + return mca.arborescenceCost();
1.558 }
1.559
1.560 }