1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/min_cost_arborescence.h Thu Dec 10 17:05:35 2009 +0100
1.3 @@ -0,0 +1,807 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_MIN_COST_ARBORESCENCE_H
1.23 +#define LEMON_MIN_COST_ARBORESCENCE_H
1.24 +
1.25 +///\ingroup spantree
1.26 +///\file
1.27 +///\brief Minimum Cost Arborescence algorithm.
1.28 +
1.29 +#include <vector>
1.30 +
1.31 +#include <lemon/list_graph.h>
1.32 +#include <lemon/bin_heap.h>
1.33 +#include <lemon/assert.h>
1.34 +
1.35 +namespace lemon {
1.36 +
1.37 +
1.38 + /// \brief Default traits class for MinCostArborescence class.
1.39 + ///
1.40 + /// Default traits class for MinCostArborescence class.
1.41 + /// \param GR Digraph type.
1.42 + /// \param CM Type of the cost map.
1.43 + template <class GR, class CM>
1.44 + struct MinCostArborescenceDefaultTraits{
1.45 +
1.46 + /// \brief The digraph type the algorithm runs on.
1.47 + typedef GR Digraph;
1.48 +
1.49 + /// \brief The type of the map that stores the arc costs.
1.50 + ///
1.51 + /// The type of the map that stores the arc costs.
1.52 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.53 + typedef CM CostMap;
1.54 +
1.55 + /// \brief The value type of the costs.
1.56 + ///
1.57 + /// The value type of the costs.
1.58 + typedef typename CostMap::Value Value;
1.59 +
1.60 + /// \brief The type of the map that stores which arcs are in the
1.61 + /// arborescence.
1.62 + ///
1.63 + /// The type of the map that stores which arcs are in the
1.64 + /// arborescence. It must conform to the \ref concepts::WriteMap
1.65 + /// "WriteMap" concept, and its value type must be \c bool
1.66 + /// (or convertible). Initially it will be set to \c false on each
1.67 + /// arc, then it will be set on each arborescence arc once.
1.68 + typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
1.69 +
1.70 + /// \brief Instantiates a \c ArborescenceMap.
1.71 + ///
1.72 + /// This function instantiates a \c ArborescenceMap.
1.73 + /// \param digraph The digraph to which we would like to calculate
1.74 + /// the \c ArborescenceMap.
1.75 + static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
1.76 + return new ArborescenceMap(digraph);
1.77 + }
1.78 +
1.79 + /// \brief The type of the \c PredMap
1.80 + ///
1.81 + /// The type of the \c PredMap. It must confrom to the
1.82 + /// \ref concepts::WriteMap "WriteMap" concept, and its value type
1.83 + /// must be the \c Arc type of the digraph.
1.84 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.85 +
1.86 + /// \brief Instantiates a \c PredMap.
1.87 + ///
1.88 + /// This function instantiates a \c PredMap.
1.89 + /// \param digraph The digraph to which we would like to define the
1.90 + /// \c PredMap.
1.91 + static PredMap *createPredMap(const Digraph &digraph){
1.92 + return new PredMap(digraph);
1.93 + }
1.94 +
1.95 + };
1.96 +
1.97 + /// \ingroup spantree
1.98 + ///
1.99 + /// \brief Minimum Cost Arborescence algorithm class.
1.100 + ///
1.101 + /// This class provides an efficient implementation of the
1.102 + /// Minimum Cost Arborescence algorithm. The arborescence is a tree
1.103 + /// which is directed from a given source node of the digraph. One or
1.104 + /// more sources should be given to the algorithm and it will calculate
1.105 + /// the minimum cost subgraph that is the union of arborescences with the
1.106 + /// given sources and spans all the nodes which are reachable from the
1.107 + /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
1.108 + ///
1.109 + /// The algorithm also provides an optimal dual solution, therefore
1.110 + /// the optimality of the solution can be checked.
1.111 + ///
1.112 + /// \param GR The digraph type the algorithm runs on.
1.113 + /// \param CM A read-only arc map storing the costs of the
1.114 + /// arcs. It is read once for each arc, so the map may involve in
1.115 + /// relatively time consuming process to compute the arc costs if
1.116 + /// it is necessary. The default map type is \ref
1.117 + /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
1.118 + /// \param TR Traits class to set various data types used
1.119 + /// by the algorithm. The default traits class is
1.120 + /// \ref MinCostArborescenceDefaultTraits
1.121 + /// "MinCostArborescenceDefaultTraits<GR, CM>".
1.122 +#ifndef DOXYGEN
1.123 + template <typename GR,
1.124 + typename CM = typename GR::template ArcMap<int>,
1.125 + typename TR =
1.126 + MinCostArborescenceDefaultTraits<GR, CM> >
1.127 +#else
1.128 + template <typename GR, typename CM, typedef TR>
1.129 +#endif
1.130 + class MinCostArborescence {
1.131 + public:
1.132 +
1.133 + /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
1.134 + /// of the algorithm.
1.135 + typedef TR Traits;
1.136 + /// The type of the underlying digraph.
1.137 + typedef typename Traits::Digraph Digraph;
1.138 + /// The type of the map that stores the arc costs.
1.139 + typedef typename Traits::CostMap CostMap;
1.140 + ///The type of the costs of the arcs.
1.141 + typedef typename Traits::Value Value;
1.142 + ///The type of the predecessor map.
1.143 + typedef typename Traits::PredMap PredMap;
1.144 + ///The type of the map that stores which arcs are in the arborescence.
1.145 + typedef typename Traits::ArborescenceMap ArborescenceMap;
1.146 +
1.147 + typedef MinCostArborescence Create;
1.148 +
1.149 + private:
1.150 +
1.151 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.152 +
1.153 + struct CostArc {
1.154 +
1.155 + Arc arc;
1.156 + Value value;
1.157 +
1.158 + CostArc() {}
1.159 + CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
1.160 +
1.161 + };
1.162 +
1.163 + const Digraph *_digraph;
1.164 + const CostMap *_cost;
1.165 +
1.166 + PredMap *_pred;
1.167 + bool local_pred;
1.168 +
1.169 + ArborescenceMap *_arborescence;
1.170 + bool local_arborescence;
1.171 +
1.172 + typedef typename Digraph::template ArcMap<int> ArcOrder;
1.173 + ArcOrder *_arc_order;
1.174 +
1.175 + typedef typename Digraph::template NodeMap<int> NodeOrder;
1.176 + NodeOrder *_node_order;
1.177 +
1.178 + typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
1.179 + CostArcMap *_cost_arcs;
1.180 +
1.181 + struct StackLevel {
1.182 +
1.183 + std::vector<CostArc> arcs;
1.184 + int node_level;
1.185 +
1.186 + };
1.187 +
1.188 + std::vector<StackLevel> level_stack;
1.189 + std::vector<Node> queue;
1.190 +
1.191 + typedef std::vector<typename Digraph::Node> DualNodeList;
1.192 +
1.193 + DualNodeList _dual_node_list;
1.194 +
1.195 + struct DualVariable {
1.196 + int begin, end;
1.197 + Value value;
1.198 +
1.199 + DualVariable(int _begin, int _end, Value _value)
1.200 + : begin(_begin), end(_end), value(_value) {}
1.201 +
1.202 + };
1.203 +
1.204 + typedef std::vector<DualVariable> DualVariables;
1.205 +
1.206 + DualVariables _dual_variables;
1.207 +
1.208 + typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.209 +
1.210 + HeapCrossRef *_heap_cross_ref;
1.211 +
1.212 + typedef BinHeap<int, HeapCrossRef> Heap;
1.213 +
1.214 + Heap *_heap;
1.215 +
1.216 + protected:
1.217 +
1.218 + MinCostArborescence() {}
1.219 +
1.220 + private:
1.221 +
1.222 + void createStructures() {
1.223 + if (!_pred) {
1.224 + local_pred = true;
1.225 + _pred = Traits::createPredMap(*_digraph);
1.226 + }
1.227 + if (!_arborescence) {
1.228 + local_arborescence = true;
1.229 + _arborescence = Traits::createArborescenceMap(*_digraph);
1.230 + }
1.231 + if (!_arc_order) {
1.232 + _arc_order = new ArcOrder(*_digraph);
1.233 + }
1.234 + if (!_node_order) {
1.235 + _node_order = new NodeOrder(*_digraph);
1.236 + }
1.237 + if (!_cost_arcs) {
1.238 + _cost_arcs = new CostArcMap(*_digraph);
1.239 + }
1.240 + if (!_heap_cross_ref) {
1.241 + _heap_cross_ref = new HeapCrossRef(*_digraph, -1);
1.242 + }
1.243 + if (!_heap) {
1.244 + _heap = new Heap(*_heap_cross_ref);
1.245 + }
1.246 + }
1.247 +
1.248 + void destroyStructures() {
1.249 + if (local_arborescence) {
1.250 + delete _arborescence;
1.251 + }
1.252 + if (local_pred) {
1.253 + delete _pred;
1.254 + }
1.255 + if (_arc_order) {
1.256 + delete _arc_order;
1.257 + }
1.258 + if (_node_order) {
1.259 + delete _node_order;
1.260 + }
1.261 + if (_cost_arcs) {
1.262 + delete _cost_arcs;
1.263 + }
1.264 + if (_heap) {
1.265 + delete _heap;
1.266 + }
1.267 + if (_heap_cross_ref) {
1.268 + delete _heap_cross_ref;
1.269 + }
1.270 + }
1.271 +
1.272 + Arc prepare(Node node) {
1.273 + std::vector<Node> nodes;
1.274 + (*_node_order)[node] = _dual_node_list.size();
1.275 + StackLevel level;
1.276 + level.node_level = _dual_node_list.size();
1.277 + _dual_node_list.push_back(node);
1.278 + for (InArcIt it(*_digraph, node); it != INVALID; ++it) {
1.279 + Arc arc = it;
1.280 + Node source = _digraph->source(arc);
1.281 + Value value = (*_cost)[it];
1.282 + if (source == node || (*_node_order)[source] == -3) continue;
1.283 + if ((*_cost_arcs)[source].arc == INVALID) {
1.284 + (*_cost_arcs)[source].arc = arc;
1.285 + (*_cost_arcs)[source].value = value;
1.286 + nodes.push_back(source);
1.287 + } else {
1.288 + if ((*_cost_arcs)[source].value > value) {
1.289 + (*_cost_arcs)[source].arc = arc;
1.290 + (*_cost_arcs)[source].value = value;
1.291 + }
1.292 + }
1.293 + }
1.294 + CostArc minimum = (*_cost_arcs)[nodes[0]];
1.295 + for (int i = 1; i < int(nodes.size()); ++i) {
1.296 + if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
1.297 + minimum = (*_cost_arcs)[nodes[i]];
1.298 + }
1.299 + }
1.300 + (*_arc_order)[minimum.arc] = _dual_variables.size();
1.301 + DualVariable var(_dual_node_list.size() - 1,
1.302 + _dual_node_list.size(), minimum.value);
1.303 + _dual_variables.push_back(var);
1.304 + for (int i = 0; i < int(nodes.size()); ++i) {
1.305 + (*_cost_arcs)[nodes[i]].value -= minimum.value;
1.306 + level.arcs.push_back((*_cost_arcs)[nodes[i]]);
1.307 + (*_cost_arcs)[nodes[i]].arc = INVALID;
1.308 + }
1.309 + level_stack.push_back(level);
1.310 + return minimum.arc;
1.311 + }
1.312 +
1.313 + Arc contract(Node node) {
1.314 + int node_bottom = bottom(node);
1.315 + std::vector<Node> nodes;
1.316 + while (!level_stack.empty() &&
1.317 + level_stack.back().node_level >= node_bottom) {
1.318 + for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) {
1.319 + Arc arc = level_stack.back().arcs[i].arc;
1.320 + Node source = _digraph->source(arc);
1.321 + Value value = level_stack.back().arcs[i].value;
1.322 + if ((*_node_order)[source] >= node_bottom) continue;
1.323 + if ((*_cost_arcs)[source].arc == INVALID) {
1.324 + (*_cost_arcs)[source].arc = arc;
1.325 + (*_cost_arcs)[source].value = value;
1.326 + nodes.push_back(source);
1.327 + } else {
1.328 + if ((*_cost_arcs)[source].value > value) {
1.329 + (*_cost_arcs)[source].arc = arc;
1.330 + (*_cost_arcs)[source].value = value;
1.331 + }
1.332 + }
1.333 + }
1.334 + level_stack.pop_back();
1.335 + }
1.336 + CostArc minimum = (*_cost_arcs)[nodes[0]];
1.337 + for (int i = 1; i < int(nodes.size()); ++i) {
1.338 + if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
1.339 + minimum = (*_cost_arcs)[nodes[i]];
1.340 + }
1.341 + }
1.342 + (*_arc_order)[minimum.arc] = _dual_variables.size();
1.343 + DualVariable var(node_bottom, _dual_node_list.size(), minimum.value);
1.344 + _dual_variables.push_back(var);
1.345 + StackLevel level;
1.346 + level.node_level = node_bottom;
1.347 + for (int i = 0; i < int(nodes.size()); ++i) {
1.348 + (*_cost_arcs)[nodes[i]].value -= minimum.value;
1.349 + level.arcs.push_back((*_cost_arcs)[nodes[i]]);
1.350 + (*_cost_arcs)[nodes[i]].arc = INVALID;
1.351 + }
1.352 + level_stack.push_back(level);
1.353 + return minimum.arc;
1.354 + }
1.355 +
1.356 + int bottom(Node node) {
1.357 + int k = level_stack.size() - 1;
1.358 + while (level_stack[k].node_level > (*_node_order)[node]) {
1.359 + --k;
1.360 + }
1.361 + return level_stack[k].node_level;
1.362 + }
1.363 +
1.364 + void finalize(Arc arc) {
1.365 + Node node = _digraph->target(arc);
1.366 + _heap->push(node, (*_arc_order)[arc]);
1.367 + _pred->set(node, arc);
1.368 + while (!_heap->empty()) {
1.369 + Node source = _heap->top();
1.370 + _heap->pop();
1.371 + (*_node_order)[source] = -1;
1.372 + for (OutArcIt it(*_digraph, source); it != INVALID; ++it) {
1.373 + if ((*_arc_order)[it] < 0) continue;
1.374 + Node target = _digraph->target(it);
1.375 + switch(_heap->state(target)) {
1.376 + case Heap::PRE_HEAP:
1.377 + _heap->push(target, (*_arc_order)[it]);
1.378 + _pred->set(target, it);
1.379 + break;
1.380 + case Heap::IN_HEAP:
1.381 + if ((*_arc_order)[it] < (*_heap)[target]) {
1.382 + _heap->decrease(target, (*_arc_order)[it]);
1.383 + _pred->set(target, it);
1.384 + }
1.385 + break;
1.386 + case Heap::POST_HEAP:
1.387 + break;
1.388 + }
1.389 + }
1.390 + _arborescence->set((*_pred)[source], true);
1.391 + }
1.392 + }
1.393 +
1.394 +
1.395 + public:
1.396 +
1.397 + /// \name Named Template Parameters
1.398 +
1.399 + /// @{
1.400 +
1.401 + template <class T>
1.402 + struct SetArborescenceMapTraits : public Traits {
1.403 + typedef T ArborescenceMap;
1.404 + static ArborescenceMap *createArborescenceMap(const Digraph &)
1.405 + {
1.406 + LEMON_ASSERT(false, "ArborescenceMap is not initialized");
1.407 + return 0; // ignore warnings
1.408 + }
1.409 + };
1.410 +
1.411 + /// \brief \ref named-templ-param "Named parameter" for
1.412 + /// setting \c ArborescenceMap type
1.413 + ///
1.414 + /// \ref named-templ-param "Named parameter" for setting
1.415 + /// \c ArborescenceMap type.
1.416 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
1.417 + /// and its value type must be \c bool (or convertible).
1.418 + /// Initially it will be set to \c false on each arc,
1.419 + /// then it will be set on each arborescence arc once.
1.420 + template <class T>
1.421 + struct SetArborescenceMap
1.422 + : public MinCostArborescence<Digraph, CostMap,
1.423 + SetArborescenceMapTraits<T> > {
1.424 + };
1.425 +
1.426 + template <class T>
1.427 + struct SetPredMapTraits : public Traits {
1.428 + typedef T PredMap;
1.429 + static PredMap *createPredMap(const Digraph &)
1.430 + {
1.431 + LEMON_ASSERT(false, "PredMap is not initialized");
1.432 + return 0; // ignore warnings
1.433 + }
1.434 + };
1.435 +
1.436 + /// \brief \ref named-templ-param "Named parameter" for
1.437 + /// setting \c PredMap type
1.438 + ///
1.439 + /// \ref named-templ-param "Named parameter" for setting
1.440 + /// \c PredMap type.
1.441 + /// It must meet the \ref concepts::WriteMap "WriteMap" concept,
1.442 + /// and its value type must be the \c Arc type of the digraph.
1.443 + template <class T>
1.444 + struct SetPredMap
1.445 + : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
1.446 + };
1.447 +
1.448 + /// @}
1.449 +
1.450 + /// \brief Constructor.
1.451 + ///
1.452 + /// \param digraph The digraph the algorithm will run on.
1.453 + /// \param cost The cost map used by the algorithm.
1.454 + MinCostArborescence(const Digraph& digraph, const CostMap& cost)
1.455 + : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
1.456 + _arborescence(0), local_arborescence(false),
1.457 + _arc_order(0), _node_order(0), _cost_arcs(0),
1.458 + _heap_cross_ref(0), _heap(0) {}
1.459 +
1.460 + /// \brief Destructor.
1.461 + ~MinCostArborescence() {
1.462 + destroyStructures();
1.463 + }
1.464 +
1.465 + /// \brief Sets the arborescence map.
1.466 + ///
1.467 + /// Sets the arborescence map.
1.468 + /// \return <tt>(*this)</tt>
1.469 + MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
1.470 + if (local_arborescence) {
1.471 + delete _arborescence;
1.472 + }
1.473 + local_arborescence = false;
1.474 + _arborescence = &m;
1.475 + return *this;
1.476 + }
1.477 +
1.478 + /// \brief Sets the predecessor map.
1.479 + ///
1.480 + /// Sets the predecessor map.
1.481 + /// \return <tt>(*this)</tt>
1.482 + MinCostArborescence& predMap(PredMap& m) {
1.483 + if (local_pred) {
1.484 + delete _pred;
1.485 + }
1.486 + local_pred = false;
1.487 + _pred = &m;
1.488 + return *this;
1.489 + }
1.490 +
1.491 + /// \name Execution Control
1.492 + /// The simplest way to execute the algorithm is to use
1.493 + /// one of the member functions called \c run(...). \n
1.494 + /// If you need more control on the execution,
1.495 + /// first you must call \ref init(), then you can add several
1.496 + /// source nodes with \ref addSource().
1.497 + /// Finally \ref start() will perform the arborescence
1.498 + /// computation.
1.499 +
1.500 + ///@{
1.501 +
1.502 + /// \brief Initializes the internal data structures.
1.503 + ///
1.504 + /// Initializes the internal data structures.
1.505 + ///
1.506 + void init() {
1.507 + createStructures();
1.508 + _heap->clear();
1.509 + for (NodeIt it(*_digraph); it != INVALID; ++it) {
1.510 + (*_cost_arcs)[it].arc = INVALID;
1.511 + (*_node_order)[it] = -3;
1.512 + (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
1.513 + _pred->set(it, INVALID);
1.514 + }
1.515 + for (ArcIt it(*_digraph); it != INVALID; ++it) {
1.516 + _arborescence->set(it, false);
1.517 + (*_arc_order)[it] = -1;
1.518 + }
1.519 + _dual_node_list.clear();
1.520 + _dual_variables.clear();
1.521 + }
1.522 +
1.523 + /// \brief Adds a new source node.
1.524 + ///
1.525 + /// Adds a new source node to the algorithm.
1.526 + void addSource(Node source) {
1.527 + std::vector<Node> nodes;
1.528 + nodes.push_back(source);
1.529 + while (!nodes.empty()) {
1.530 + Node node = nodes.back();
1.531 + nodes.pop_back();
1.532 + for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
1.533 + Node target = _digraph->target(it);
1.534 + if ((*_node_order)[target] == -3) {
1.535 + (*_node_order)[target] = -2;
1.536 + nodes.push_back(target);
1.537 + queue.push_back(target);
1.538 + }
1.539 + }
1.540 + }
1.541 + (*_node_order)[source] = -1;
1.542 + }
1.543 +
1.544 + /// \brief Processes the next node in the priority queue.
1.545 + ///
1.546 + /// Processes the next node in the priority queue.
1.547 + ///
1.548 + /// \return The processed node.
1.549 + ///
1.550 + /// \warning The queue must not be empty.
1.551 + Node processNextNode() {
1.552 + Node node = queue.back();
1.553 + queue.pop_back();
1.554 + if ((*_node_order)[node] == -2) {
1.555 + Arc arc = prepare(node);
1.556 + Node source = _digraph->source(arc);
1.557 + while ((*_node_order)[source] != -1) {
1.558 + if ((*_node_order)[source] >= 0) {
1.559 + arc = contract(source);
1.560 + } else {
1.561 + arc = prepare(source);
1.562 + }
1.563 + source = _digraph->source(arc);
1.564 + }
1.565 + finalize(arc);
1.566 + level_stack.clear();
1.567 + }
1.568 + return node;
1.569 + }
1.570 +
1.571 + /// \brief Returns the number of the nodes to be processed.
1.572 + ///
1.573 + /// Returns the number of the nodes to be processed in the priority
1.574 + /// queue.
1.575 + int queueSize() const {
1.576 + return queue.size();
1.577 + }
1.578 +
1.579 + /// \brief Returns \c false if there are nodes to be processed.
1.580 + ///
1.581 + /// Returns \c false if there are nodes to be processed.
1.582 + bool emptyQueue() const {
1.583 + return queue.empty();
1.584 + }
1.585 +
1.586 + /// \brief Executes the algorithm.
1.587 + ///
1.588 + /// Executes the algorithm.
1.589 + ///
1.590 + /// \pre init() must be called and at least one node should be added
1.591 + /// with addSource() before using this function.
1.592 + ///
1.593 + ///\note mca.start() is just a shortcut of the following code.
1.594 + ///\code
1.595 + ///while (!mca.emptyQueue()) {
1.596 + /// mca.processNextNode();
1.597 + ///}
1.598 + ///\endcode
1.599 + void start() {
1.600 + while (!emptyQueue()) {
1.601 + processNextNode();
1.602 + }
1.603 + }
1.604 +
1.605 + /// \brief Runs %MinCostArborescence algorithm from node \c s.
1.606 + ///
1.607 + /// This method runs the %MinCostArborescence algorithm from
1.608 + /// a root node \c s.
1.609 + ///
1.610 + /// \note mca.run(s) is just a shortcut of the following code.
1.611 + /// \code
1.612 + /// mca.init();
1.613 + /// mca.addSource(s);
1.614 + /// mca.start();
1.615 + /// \endcode
1.616 + void run(Node s) {
1.617 + init();
1.618 + addSource(s);
1.619 + start();
1.620 + }
1.621 +
1.622 + ///@}
1.623 +
1.624 + /// \name Query Functions
1.625 + /// The result of the %MinCostArborescence algorithm can be obtained
1.626 + /// using these functions.\n
1.627 + /// Either run() or start() must be called before using them.
1.628 +
1.629 + /// @{
1.630 +
1.631 + /// \brief Returns the cost of the arborescence.
1.632 + ///
1.633 + /// Returns the cost of the arborescence.
1.634 + Value arborescenceCost() const {
1.635 + Value sum = 0;
1.636 + for (ArcIt it(*_digraph); it != INVALID; ++it) {
1.637 + if (arborescence(it)) {
1.638 + sum += (*_cost)[it];
1.639 + }
1.640 + }
1.641 + return sum;
1.642 + }
1.643 +
1.644 + /// \brief Returns \c true if the arc is in the arborescence.
1.645 + ///
1.646 + /// Returns \c true if the given arc is in the arborescence.
1.647 + /// \param arc An arc of the digraph.
1.648 + /// \pre \ref run() must be called before using this function.
1.649 + bool arborescence(Arc arc) const {
1.650 + return (*_pred)[_digraph->target(arc)] == arc;
1.651 + }
1.652 +
1.653 + /// \brief Returns a const reference to the arborescence map.
1.654 + ///
1.655 + /// Returns a const reference to the arborescence map.
1.656 + /// \pre \ref run() must be called before using this function.
1.657 + const ArborescenceMap& arborescenceMap() const {
1.658 + return *_arborescence;
1.659 + }
1.660 +
1.661 + /// \brief Returns the predecessor arc of the given node.
1.662 + ///
1.663 + /// Returns the predecessor arc of the given node.
1.664 + /// \pre \ref run() must be called before using this function.
1.665 + Arc pred(Node node) const {
1.666 + return (*_pred)[node];
1.667 + }
1.668 +
1.669 + /// \brief Returns a const reference to the pred map.
1.670 + ///
1.671 + /// Returns a const reference to the pred map.
1.672 + /// \pre \ref run() must be called before using this function.
1.673 + const PredMap& predMap() const {
1.674 + return *_pred;
1.675 + }
1.676 +
1.677 + /// \brief Indicates that a node is reachable from the sources.
1.678 + ///
1.679 + /// Indicates that a node is reachable from the sources.
1.680 + bool reached(Node node) const {
1.681 + return (*_node_order)[node] != -3;
1.682 + }
1.683 +
1.684 + /// \brief Indicates that a node is processed.
1.685 + ///
1.686 + /// Indicates that a node is processed. The arborescence path exists
1.687 + /// from the source to the given node.
1.688 + bool processed(Node node) const {
1.689 + return (*_node_order)[node] == -1;
1.690 + }
1.691 +
1.692 + /// \brief Returns the number of the dual variables in basis.
1.693 + ///
1.694 + /// Returns the number of the dual variables in basis.
1.695 + int dualNum() const {
1.696 + return _dual_variables.size();
1.697 + }
1.698 +
1.699 + /// \brief Returns the value of the dual solution.
1.700 + ///
1.701 + /// Returns the value of the dual solution. It should be
1.702 + /// equal to the arborescence value.
1.703 + Value dualValue() const {
1.704 + Value sum = 0;
1.705 + for (int i = 0; i < int(_dual_variables.size()); ++i) {
1.706 + sum += _dual_variables[i].value;
1.707 + }
1.708 + return sum;
1.709 + }
1.710 +
1.711 + /// \brief Returns the number of the nodes in the dual variable.
1.712 + ///
1.713 + /// Returns the number of the nodes in the dual variable.
1.714 + int dualSize(int k) const {
1.715 + return _dual_variables[k].end - _dual_variables[k].begin;
1.716 + }
1.717 +
1.718 + /// \brief Returns the value of the dual variable.
1.719 + ///
1.720 + /// Returns the the value of the dual variable.
1.721 + Value dualValue(int k) const {
1.722 + return _dual_variables[k].value;
1.723 + }
1.724 +
1.725 + /// \brief LEMON iterator for getting a dual variable.
1.726 + ///
1.727 + /// This class provides a common style LEMON iterator for getting a
1.728 + /// dual variable of \ref MinCostArborescence algorithm.
1.729 + /// It iterates over a subset of the nodes.
1.730 + class DualIt {
1.731 + public:
1.732 +
1.733 + /// \brief Constructor.
1.734 + ///
1.735 + /// Constructor for getting the nodeset of the dual variable
1.736 + /// of \ref MinCostArborescence algorithm.
1.737 + DualIt(const MinCostArborescence& algorithm, int variable)
1.738 + : _algorithm(&algorithm)
1.739 + {
1.740 + _index = _algorithm->_dual_variables[variable].begin;
1.741 + _last = _algorithm->_dual_variables[variable].end;
1.742 + }
1.743 +
1.744 + /// \brief Conversion to \c Node.
1.745 + ///
1.746 + /// Conversion to \c Node.
1.747 + operator Node() const {
1.748 + return _algorithm->_dual_node_list[_index];
1.749 + }
1.750 +
1.751 + /// \brief Increment operator.
1.752 + ///
1.753 + /// Increment operator.
1.754 + DualIt& operator++() {
1.755 + ++_index;
1.756 + return *this;
1.757 + }
1.758 +
1.759 + /// \brief Validity checking
1.760 + ///
1.761 + /// Checks whether the iterator is invalid.
1.762 + bool operator==(Invalid) const {
1.763 + return _index == _last;
1.764 + }
1.765 +
1.766 + /// \brief Validity checking
1.767 + ///
1.768 + /// Checks whether the iterator is valid.
1.769 + bool operator!=(Invalid) const {
1.770 + return _index != _last;
1.771 + }
1.772 +
1.773 + private:
1.774 + const MinCostArborescence* _algorithm;
1.775 + int _index, _last;
1.776 + };
1.777 +
1.778 + /// @}
1.779 +
1.780 + };
1.781 +
1.782 + /// \ingroup spantree
1.783 + ///
1.784 + /// \brief Function type interface for MinCostArborescence algorithm.
1.785 + ///
1.786 + /// Function type interface for MinCostArborescence algorithm.
1.787 + /// \param digraph The digraph the algorithm runs on.
1.788 + /// \param cost An arc map storing the costs.
1.789 + /// \param source The source node of the arborescence.
1.790 + /// \retval arborescence An arc map with \c bool (or convertible) value
1.791 + /// type that stores the arborescence.
1.792 + /// \return The total cost of the arborescence.
1.793 + ///
1.794 + /// \sa MinCostArborescence
1.795 + template <typename Digraph, typename CostMap, typename ArborescenceMap>
1.796 + typename CostMap::Value minCostArborescence(const Digraph& digraph,
1.797 + const CostMap& cost,
1.798 + typename Digraph::Node source,
1.799 + ArborescenceMap& arborescence) {
1.800 + typename MinCostArborescence<Digraph, CostMap>
1.801 + ::template SetArborescenceMap<ArborescenceMap>
1.802 + ::Create mca(digraph, cost);
1.803 + mca.arborescenceMap(arborescence);
1.804 + mca.run(source);
1.805 + return mca.arborescenceCost();
1.806 + }
1.807 +
1.808 +}
1.809 +
1.810 +#endif