COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/min_cost_arborescence.h @ 618:b95898314e09

Last change on this file since 618:b95898314e09 was 584:33c6b6e755cd, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Small doc improvements (#263)

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