COIN-OR::LEMON - Graph Library

source: lemon/lemon/min_cost_arborescence.h @ 1337:4add05447ca0

Last change on this file since 1337:4add05447ca0 was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 24.2 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_MIN_COST_ARBORESCENCE_H
20#define LEMON_MIN_COST_ARBORESCENCE_H
21
22///\ingroup spantree
23///\file
24///\brief Minimum Cost Arborescence algorithm.
25
26#include <vector>
27
28#include <lemon/list_graph.h>
29#include <lemon/bin_heap.h>
30#include <lemon/assert.h>
31
32namespace lemon {
33
34
35  /// \brief Default traits class for MinCostArborescence class.
36  ///
37  /// Default traits class for MinCostArborescence class.
38  /// \param GR Digraph type.
39  /// \param CM Type of the cost map.
40  template <class GR, class CM>
41  struct MinCostArborescenceDefaultTraits{
42
43    /// \brief The digraph type the algorithm runs on.
44    typedef GR Digraph;
45
46    /// \brief The type of the map that stores the arc costs.
47    ///
48    /// The type of the map that stores the arc costs.
49    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
50    typedef CM CostMap;
51
52    /// \brief The value type of the costs.
53    ///
54    /// The value type of the costs.
55    typedef typename CostMap::Value Value;
56
57    /// \brief The type of the map that stores which arcs are in the
58    /// arborescence.
59    ///
60    /// The type of the map that stores which arcs are in the
61    /// arborescence.  It must conform to the \ref concepts::WriteMap
62    /// "WriteMap" concept, and its value type must be \c bool
63    /// (or convertible). Initially it will be set to \c false on each
64    /// arc, then it will be set on each arborescence arc once.
65    typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
66
67    /// \brief Instantiates a \c ArborescenceMap.
68    ///
69    /// This function instantiates a \c ArborescenceMap.
70    /// \param digraph The digraph to which we would like to calculate
71    /// the \c ArborescenceMap.
72    static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
73      return new ArborescenceMap(digraph);
74    }
75
76    /// \brief The type of the \c PredMap
77    ///
78    /// The type of the \c PredMap. It must confrom to the
79    /// \ref concepts::WriteMap "WriteMap" concept, and its value type
80    /// must be the \c Arc type of the digraph.
81    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
82
83    /// \brief Instantiates a \c PredMap.
84    ///
85    /// This function instantiates a \c PredMap.
86    /// \param digraph The digraph to which we would like to define the
87    /// \c PredMap.
88    static PredMap *createPredMap(const Digraph &digraph){
89      return new PredMap(digraph);
90    }
91
92  };
93
94  /// \ingroup spantree
95  ///
96  /// \brief Minimum Cost Arborescence algorithm class.
97  ///
98  /// This class provides an efficient implementation of the
99  /// Minimum Cost Arborescence algorithm. The arborescence is a tree
100  /// which is directed from a given source node of the digraph. One or
101  /// more sources should be given to the algorithm and it will calculate
102  /// the minimum cost subgraph that is the union of arborescences with the
103  /// given sources and spans all the nodes which are reachable from the
104  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+m).
105  ///
106  /// The algorithm also provides an optimal dual solution, therefore
107  /// the optimality of the solution can be checked.
108  ///
109  /// \param GR The digraph type the algorithm runs on.
110  /// \param CM A read-only arc map storing the costs of the
111  /// arcs. It is read once for each arc, so the map may involve in
112  /// relatively time consuming process to compute the arc costs if
113  /// it is necessary. The default map type is \ref
114  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
115  /// \tparam TR The traits class that defines various types used by the
116  /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
117  /// "MinCostArborescenceDefaultTraits<GR, CM>".
118  /// In most cases, this parameter should not be set directly,
119  /// consider to use the named template parameters instead.
120#ifndef DOXYGEN
121  template <typename GR,
122            typename CM = typename GR::template ArcMap<int>,
123            typename TR =
124              MinCostArborescenceDefaultTraits<GR, CM> >
125#else
126  template <typename GR, typename CM, typename TR>
127#endif
128  class MinCostArborescence {
129  public:
130
131    /// \brief The \ref lemon::MinCostArborescenceDefaultTraits "traits class"
132    /// of the algorithm.
133    typedef TR Traits;
134    /// The type of the underlying digraph.
135    typedef typename Traits::Digraph Digraph;
136    /// The type of the map that stores the arc costs.
137    typedef typename Traits::CostMap CostMap;
138    ///The type of the costs of the arcs.
139    typedef typename Traits::Value Value;
140    ///The type of the predecessor map.
141    typedef typename Traits::PredMap PredMap;
142    ///The type of the map that stores which arcs are in the arborescence.
143    typedef typename Traits::ArborescenceMap ArborescenceMap;
144
145    typedef MinCostArborescence Create;
146
147  private:
148
149    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
150
151    struct CostArc {
152
153      Arc arc;
154      Value value;
155
156      CostArc() {}
157      CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
158
159    };
160
161    const Digraph *_digraph;
162    const CostMap *_cost;
163
164    PredMap *_pred;
165    bool local_pred;
166
167    ArborescenceMap *_arborescence;
168    bool local_arborescence;
169
170    typedef typename Digraph::template ArcMap<int> ArcOrder;
171    ArcOrder *_arc_order;
172
173    typedef typename Digraph::template NodeMap<int> NodeOrder;
174    NodeOrder *_node_order;
175
176    typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
177    CostArcMap *_cost_arcs;
178
179    struct StackLevel {
180
181      std::vector<CostArc> arcs;
182      int node_level;
183
184    };
185
186    std::vector<StackLevel> level_stack;
187    std::vector<Node> queue;
188
189    typedef std::vector<typename Digraph::Node> DualNodeList;
190
191    DualNodeList _dual_node_list;
192
193    struct DualVariable {
194      int begin, end;
195      Value value;
196
197      DualVariable(int _begin, int _end, Value _value)
198        : begin(_begin), end(_end), value(_value) {}
199
200    };
201
202    typedef std::vector<DualVariable> DualVariables;
203
204    DualVariables _dual_variables;
205
206    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
207
208    HeapCrossRef *_heap_cross_ref;
209
210    typedef BinHeap<int, HeapCrossRef> Heap;
211
212    Heap *_heap;
213
214  protected:
215
216    MinCostArborescence() {}
217
218  private:
219
220    void createStructures() {
221      if (!_pred) {
222        local_pred = true;
223        _pred = Traits::createPredMap(*_digraph);
224      }
225      if (!_arborescence) {
226        local_arborescence = true;
227        _arborescence = Traits::createArborescenceMap(*_digraph);
228      }
229      if (!_arc_order) {
230        _arc_order = new ArcOrder(*_digraph);
231      }
232      if (!_node_order) {
233        _node_order = new NodeOrder(*_digraph);
234      }
235      if (!_cost_arcs) {
236        _cost_arcs = new CostArcMap(*_digraph);
237      }
238      if (!_heap_cross_ref) {
239        _heap_cross_ref = new HeapCrossRef(*_digraph, -1);
240      }
241      if (!_heap) {
242        _heap = new Heap(*_heap_cross_ref);
243      }
244    }
245
246    void destroyStructures() {
247      if (local_arborescence) {
248        delete _arborescence;
249      }
250      if (local_pred) {
251        delete _pred;
252      }
253      if (_arc_order) {
254        delete _arc_order;
255      }
256      if (_node_order) {
257        delete _node_order;
258      }
259      if (_cost_arcs) {
260        delete _cost_arcs;
261      }
262      if (_heap) {
263        delete _heap;
264      }
265      if (_heap_cross_ref) {
266        delete _heap_cross_ref;
267      }
268    }
269
270    Arc prepare(Node node) {
271      std::vector<Node> nodes;
272      (*_node_order)[node] = _dual_node_list.size();
273      StackLevel level;
274      level.node_level = _dual_node_list.size();
275      _dual_node_list.push_back(node);
276      for (InArcIt it(*_digraph, node); it != INVALID; ++it) {
277        Arc arc = it;
278        Node source = _digraph->source(arc);
279        Value value = (*_cost)[it];
280        if (source == node || (*_node_order)[source] == -3) continue;
281        if ((*_cost_arcs)[source].arc == INVALID) {
282          (*_cost_arcs)[source].arc = arc;
283          (*_cost_arcs)[source].value = value;
284          nodes.push_back(source);
285        } else {
286          if ((*_cost_arcs)[source].value > value) {
287            (*_cost_arcs)[source].arc = arc;
288            (*_cost_arcs)[source].value = value;
289          }
290        }
291      }
292      CostArc minimum = (*_cost_arcs)[nodes[0]];
293      for (int i = 1; i < int(nodes.size()); ++i) {
294        if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
295          minimum = (*_cost_arcs)[nodes[i]];
296        }
297      }
298      (*_arc_order)[minimum.arc] = _dual_variables.size();
299      DualVariable var(_dual_node_list.size() - 1,
300                       _dual_node_list.size(), minimum.value);
301      _dual_variables.push_back(var);
302      for (int i = 0; i < int(nodes.size()); ++i) {
303        (*_cost_arcs)[nodes[i]].value -= minimum.value;
304        level.arcs.push_back((*_cost_arcs)[nodes[i]]);
305        (*_cost_arcs)[nodes[i]].arc = INVALID;
306      }
307      level_stack.push_back(level);
308      return minimum.arc;
309    }
310
311    Arc contract(Node node) {
312      int node_bottom = bottom(node);
313      std::vector<Node> nodes;
314      while (!level_stack.empty() &&
315             level_stack.back().node_level >= node_bottom) {
316        for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) {
317          Arc arc = level_stack.back().arcs[i].arc;
318          Node source = _digraph->source(arc);
319          Value value = level_stack.back().arcs[i].value;
320          if ((*_node_order)[source] >= node_bottom) continue;
321          if ((*_cost_arcs)[source].arc == INVALID) {
322            (*_cost_arcs)[source].arc = arc;
323            (*_cost_arcs)[source].value = value;
324            nodes.push_back(source);
325          } else {
326            if ((*_cost_arcs)[source].value > value) {
327              (*_cost_arcs)[source].arc = arc;
328              (*_cost_arcs)[source].value = value;
329            }
330          }
331        }
332        level_stack.pop_back();
333      }
334      CostArc minimum = (*_cost_arcs)[nodes[0]];
335      for (int i = 1; i < int(nodes.size()); ++i) {
336        if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
337          minimum = (*_cost_arcs)[nodes[i]];
338        }
339      }
340      (*_arc_order)[minimum.arc] = _dual_variables.size();
341      DualVariable var(node_bottom, _dual_node_list.size(), minimum.value);
342      _dual_variables.push_back(var);
343      StackLevel level;
344      level.node_level = node_bottom;
345      for (int i = 0; i < int(nodes.size()); ++i) {
346        (*_cost_arcs)[nodes[i]].value -= minimum.value;
347        level.arcs.push_back((*_cost_arcs)[nodes[i]]);
348        (*_cost_arcs)[nodes[i]].arc = INVALID;
349      }
350      level_stack.push_back(level);
351      return minimum.arc;
352    }
353
354    int bottom(Node node) {
355      int k = level_stack.size() - 1;
356      while (level_stack[k].node_level > (*_node_order)[node]) {
357        --k;
358      }
359      return level_stack[k].node_level;
360    }
361
362    void finalize(Arc arc) {
363      Node node = _digraph->target(arc);
364      _heap->push(node, (*_arc_order)[arc]);
365      _pred->set(node, arc);
366      while (!_heap->empty()) {
367        Node source = _heap->top();
368        _heap->pop();
369        (*_node_order)[source] = -1;
370        for (OutArcIt it(*_digraph, source); it != INVALID; ++it) {
371          if ((*_arc_order)[it] < 0) continue;
372          Node target = _digraph->target(it);
373          switch(_heap->state(target)) {
374          case Heap::PRE_HEAP:
375            _heap->push(target, (*_arc_order)[it]);
376            _pred->set(target, it);
377            break;
378          case Heap::IN_HEAP:
379            if ((*_arc_order)[it] < (*_heap)[target]) {
380              _heap->decrease(target, (*_arc_order)[it]);
381              _pred->set(target, it);
382            }
383            break;
384          case Heap::POST_HEAP:
385            break;
386          }
387        }
388        _arborescence->set((*_pred)[source], true);
389      }
390    }
391
392
393  public:
394
395    /// \name Named Template Parameters
396
397    /// @{
398
399    template <class T>
400    struct SetArborescenceMapTraits : public Traits {
401      typedef T ArborescenceMap;
402      static ArborescenceMap *createArborescenceMap(const Digraph &)
403      {
404        LEMON_ASSERT(false, "ArborescenceMap is not initialized");
405        return 0; // ignore warnings
406      }
407    };
408
409    /// \brief \ref named-templ-param "Named parameter" for
410    /// setting \c ArborescenceMap type
411    ///
412    /// \ref named-templ-param "Named parameter" for setting
413    /// \c ArborescenceMap type.
414    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
415    /// and its value type must be \c bool (or convertible).
416    /// Initially it will be set to \c false on each arc,
417    /// then it will be set on each arborescence arc once.
418    template <class T>
419    struct SetArborescenceMap
420      : public MinCostArborescence<Digraph, CostMap,
421                                   SetArborescenceMapTraits<T> > {
422    };
423
424    template <class T>
425    struct SetPredMapTraits : public Traits {
426      typedef T PredMap;
427      static PredMap *createPredMap(const Digraph &)
428      {
429        LEMON_ASSERT(false, "PredMap is not initialized");
430        return 0; // ignore warnings
431      }
432    };
433
434    /// \brief \ref named-templ-param "Named parameter" for
435    /// setting \c PredMap type
436    ///
437    /// \ref named-templ-param "Named parameter" for setting
438    /// \c PredMap type.
439    /// It must meet the \ref concepts::WriteMap "WriteMap" concept,
440    /// and its value type must be the \c Arc type of the digraph.
441    template <class T>
442    struct SetPredMap
443      : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
444    };
445
446    /// @}
447
448    /// \brief Constructor.
449    ///
450    /// \param digraph The digraph the algorithm will run on.
451    /// \param cost The cost map used by the algorithm.
452    MinCostArborescence(const Digraph& digraph, const CostMap& cost)
453      : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
454        _arborescence(0), local_arborescence(false),
455        _arc_order(0), _node_order(0), _cost_arcs(0),
456        _heap_cross_ref(0), _heap(0) {}
457
458    /// \brief Destructor.
459    ~MinCostArborescence() {
460      destroyStructures();
461    }
462
463    /// \brief Sets the arborescence map.
464    ///
465    /// Sets the arborescence map.
466    /// \return <tt>(*this)</tt>
467    MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
468      if (local_arborescence) {
469        delete _arborescence;
470      }
471      local_arborescence = false;
472      _arborescence = &m;
473      return *this;
474    }
475
476    /// \brief Sets the predecessor map.
477    ///
478    /// Sets the predecessor map.
479    /// \return <tt>(*this)</tt>
480    MinCostArborescence& predMap(PredMap& m) {
481      if (local_pred) {
482        delete _pred;
483      }
484      local_pred = false;
485      _pred = &m;
486      return *this;
487    }
488
489    /// \name Execution Control
490    /// The simplest way to execute the algorithm is to use
491    /// one of the member functions called \c run(...). \n
492    /// If you need better control on the execution,
493    /// you have to call \ref init() first, then you can add several
494    /// source nodes with \ref addSource().
495    /// Finally \ref start() will perform the arborescence
496    /// computation.
497
498    ///@{
499
500    /// \brief Initializes the internal data structures.
501    ///
502    /// Initializes the internal data structures.
503    ///
504    void init() {
505      createStructures();
506      _heap->clear();
507      for (NodeIt it(*_digraph); it != INVALID; ++it) {
508        (*_cost_arcs)[it].arc = INVALID;
509        (*_node_order)[it] = -3;
510        (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
511        _pred->set(it, INVALID);
512      }
513      for (ArcIt it(*_digraph); it != INVALID; ++it) {
514        _arborescence->set(it, false);
515        (*_arc_order)[it] = -1;
516      }
517      _dual_node_list.clear();
518      _dual_variables.clear();
519    }
520
521    /// \brief Adds a new source node.
522    ///
523    /// Adds a new source node to the algorithm.
524    void addSource(Node source) {
525      std::vector<Node> nodes;
526      nodes.push_back(source);
527      while (!nodes.empty()) {
528        Node node = nodes.back();
529        nodes.pop_back();
530        for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
531          Node target = _digraph->target(it);
532          if ((*_node_order)[target] == -3) {
533            (*_node_order)[target] = -2;
534            nodes.push_back(target);
535            queue.push_back(target);
536          }
537        }
538      }
539      (*_node_order)[source] = -1;
540    }
541
542    /// \brief Processes the next node in the priority queue.
543    ///
544    /// Processes the next node in the priority queue.
545    ///
546    /// \return The processed node.
547    ///
548    /// \warning The queue must not be empty.
549    Node processNextNode() {
550      Node node = queue.back();
551      queue.pop_back();
552      if ((*_node_order)[node] == -2) {
553        Arc arc = prepare(node);
554        Node source = _digraph->source(arc);
555        while ((*_node_order)[source] != -1) {
556          if ((*_node_order)[source] >= 0) {
557            arc = contract(source);
558          } else {
559            arc = prepare(source);
560          }
561          source = _digraph->source(arc);
562        }
563        finalize(arc);
564        level_stack.clear();
565      }
566      return node;
567    }
568
569    /// \brief Returns the number of the nodes to be processed.
570    ///
571    /// Returns the number of the nodes to be processed in the priority
572    /// queue.
573    int queueSize() const {
574      return queue.size();
575    }
576
577    /// \brief Returns \c false if there are nodes to be processed.
578    ///
579    /// Returns \c false if there are nodes to be processed.
580    bool emptyQueue() const {
581      return queue.empty();
582    }
583
584    /// \brief Executes the algorithm.
585    ///
586    /// Executes the algorithm.
587    ///
588    /// \pre init() must be called and at least one node should be added
589    /// with addSource() before using this function.
590    ///
591    ///\note mca.start() is just a shortcut of the following code.
592    ///\code
593    ///while (!mca.emptyQueue()) {
594    ///  mca.processNextNode();
595    ///}
596    ///\endcode
597    void start() {
598      while (!emptyQueue()) {
599        processNextNode();
600      }
601    }
602
603    /// \brief Runs %MinCostArborescence algorithm from node \c s.
604    ///
605    /// This method runs the %MinCostArborescence algorithm from
606    /// a root node \c s.
607    ///
608    /// \note mca.run(s) is just a shortcut of the following code.
609    /// \code
610    /// mca.init();
611    /// mca.addSource(s);
612    /// mca.start();
613    /// \endcode
614    void run(Node s) {
615      init();
616      addSource(s);
617      start();
618    }
619
620    ///@}
621
622    /// \name Query Functions
623    /// The result of the %MinCostArborescence algorithm can be obtained
624    /// using these functions.\n
625    /// Either run() or start() must be called before using them.
626
627    /// @{
628
629    /// \brief Returns the cost of the arborescence.
630    ///
631    /// Returns the cost of the arborescence.
632    Value arborescenceCost() const {
633      Value sum = 0;
634      for (ArcIt it(*_digraph); it != INVALID; ++it) {
635        if (arborescence(it)) {
636          sum += (*_cost)[it];
637        }
638      }
639      return sum;
640    }
641
642    /// \brief Returns \c true if the arc is in the arborescence.
643    ///
644    /// Returns \c true if the given arc is in the arborescence.
645    /// \param arc An arc of the digraph.
646    /// \pre \ref run() must be called before using this function.
647    bool arborescence(Arc arc) const {
648      return (*_pred)[_digraph->target(arc)] == arc;
649    }
650
651    /// \brief Returns a const reference to the arborescence map.
652    ///
653    /// Returns a const reference to the arborescence map.
654    /// \pre \ref run() must be called before using this function.
655    const ArborescenceMap& arborescenceMap() const {
656      return *_arborescence;
657    }
658
659    /// \brief Returns the predecessor arc of the given node.
660    ///
661    /// Returns the predecessor arc of the given node.
662    /// \pre \ref run() must be called before using this function.
663    Arc pred(Node node) const {
664      return (*_pred)[node];
665    }
666
667    /// \brief Returns a const reference to the pred map.
668    ///
669    /// Returns a const reference to the pred map.
670    /// \pre \ref run() must be called before using this function.
671    const PredMap& predMap() const {
672      return *_pred;
673    }
674
675    /// \brief Indicates that a node is reachable from the sources.
676    ///
677    /// Indicates that a node is reachable from the sources.
678    bool reached(Node node) const {
679      return (*_node_order)[node] != -3;
680    }
681
682    /// \brief Indicates that a node is processed.
683    ///
684    /// Indicates that a node is processed. The arborescence path exists
685    /// from the source to the given node.
686    bool processed(Node node) const {
687      return (*_node_order)[node] == -1;
688    }
689
690    /// \brief Returns the number of the dual variables in basis.
691    ///
692    /// Returns the number of the dual variables in basis.
693    int dualNum() const {
694      return _dual_variables.size();
695    }
696
697    /// \brief Returns the value of the dual solution.
698    ///
699    /// Returns the value of the dual solution. It should be
700    /// equal to the arborescence value.
701    Value dualValue() const {
702      Value sum = 0;
703      for (int i = 0; i < int(_dual_variables.size()); ++i) {
704        sum += _dual_variables[i].value;
705      }
706      return sum;
707    }
708
709    /// \brief Returns the number of the nodes in the dual variable.
710    ///
711    /// Returns the number of the nodes in the dual variable.
712    int dualSize(int k) const {
713      return _dual_variables[k].end - _dual_variables[k].begin;
714    }
715
716    /// \brief Returns the value of the dual variable.
717    ///
718    /// Returns the the value of the dual variable.
719    Value dualValue(int k) const {
720      return _dual_variables[k].value;
721    }
722
723    /// \brief LEMON iterator for getting a dual variable.
724    ///
725    /// This class provides a common style LEMON iterator for getting a
726    /// dual variable of \ref MinCostArborescence algorithm.
727    /// It iterates over a subset of the nodes.
728    class DualIt {
729    public:
730
731      /// \brief Constructor.
732      ///
733      /// Constructor for getting the nodeset of the dual variable
734      /// of \ref MinCostArborescence algorithm.
735      DualIt(const MinCostArborescence& algorithm, int variable)
736        : _algorithm(&algorithm)
737      {
738        _index = _algorithm->_dual_variables[variable].begin;
739        _last = _algorithm->_dual_variables[variable].end;
740      }
741
742      /// \brief Conversion to \c Node.
743      ///
744      /// Conversion to \c Node.
745      operator Node() const {
746        return _algorithm->_dual_node_list[_index];
747      }
748
749      /// \brief Increment operator.
750      ///
751      /// Increment operator.
752      DualIt& operator++() {
753        ++_index;
754        return *this;
755      }
756
757      /// \brief Validity checking
758      ///
759      /// Checks whether the iterator is invalid.
760      bool operator==(Invalid) const {
761        return _index == _last;
762      }
763
764      /// \brief Validity checking
765      ///
766      /// Checks whether the iterator is valid.
767      bool operator!=(Invalid) const {
768        return _index != _last;
769      }
770
771    private:
772      const MinCostArborescence* _algorithm;
773      int _index, _last;
774    };
775
776    /// @}
777
778  };
779
780  /// \ingroup spantree
781  ///
782  /// \brief Function type interface for MinCostArborescence algorithm.
783  ///
784  /// Function type interface for MinCostArborescence algorithm.
785  /// \param digraph The digraph the algorithm runs on.
786  /// \param cost An arc map storing the costs.
787  /// \param source The source node of the arborescence.
788  /// \retval arborescence An arc map with \c bool (or convertible) value
789  /// type that stores the arborescence.
790  /// \return The total cost of the arborescence.
791  ///
792  /// \sa MinCostArborescence
793  template <typename Digraph, typename CostMap, typename ArborescenceMap>
794  typename CostMap::Value minCostArborescence(const Digraph& digraph,
795                                              const CostMap& cost,
796                                              typename Digraph::Node source,
797                                              ArborescenceMap& arborescence) {
798    typename MinCostArborescence<Digraph, CostMap>
799      ::template SetArborescenceMap<ArborescenceMap>
800      ::Create mca(digraph, cost);
801    mca.arborescenceMap(arborescence);
802    mca.run(source);
803    return mca.arborescenceCost();
804  }
805
806}
807
808#endif
Note: See TracBrowser for help on using the repository browser.