34 |
34 |
35 /// \brief Default traits class for MinCostArborescence class. |
35 /// \brief Default traits class for MinCostArborescence class. |
36 /// |
36 /// |
37 /// Default traits class for MinCostArborescence class. |
37 /// Default traits class for MinCostArborescence class. |
38 /// \param GR Digraph type. |
38 /// \param GR Digraph type. |
39 /// \param CM Type of cost map. |
39 /// \param CM Type of the cost map. |
40 template <class GR, class CM> |
40 template <class GR, class CM> |
41 struct MinCostArborescenceDefaultTraits{ |
41 struct MinCostArborescenceDefaultTraits{ |
42 |
42 |
43 /// \brief The digraph type the algorithm runs on. |
43 /// \brief The digraph type the algorithm runs on. |
44 typedef GR Digraph; |
44 typedef GR Digraph; |
45 |
45 |
46 /// \brief The type of the map that stores the arc costs. |
46 /// \brief The type of the map that stores the arc costs. |
47 /// |
47 /// |
48 /// The type of the map that stores the arc costs. |
48 /// The type of the map that stores the arc costs. |
49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
49 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. |
50 typedef CM CostMap; |
50 typedef CM CostMap; |
51 |
51 |
52 /// \brief The value type of the costs. |
52 /// \brief The value type of the costs. |
53 /// |
53 /// |
54 /// The value type of the costs. |
54 /// The value type of the costs. |
56 |
56 |
57 /// \brief The type of the map that stores which arcs are in the |
57 /// \brief The type of the map that stores which arcs are in the |
58 /// arborescence. |
58 /// arborescence. |
59 /// |
59 /// |
60 /// The type of the map that stores which arcs are in the |
60 /// The type of the map that stores which arcs are in the |
61 /// arborescence. It must meet the \ref concepts::WriteMap |
61 /// arborescence. It must conform to the \ref concepts::WriteMap |
62 /// "WriteMap" concept. Initially it will be set to false on each |
62 /// "WriteMap" concept, and its value type must be \c bool |
63 /// arc. After it will set all arborescence arcs once. |
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. |
64 typedef typename Digraph::template ArcMap<bool> ArborescenceMap; |
65 typedef typename Digraph::template ArcMap<bool> ArborescenceMap; |
65 |
66 |
66 /// \brief Instantiates a \c ArborescenceMap. |
67 /// \brief Instantiates a \c ArborescenceMap. |
67 /// |
68 /// |
68 /// This function instantiates a \c ArborescenceMap. |
69 /// This function instantiates a \c ArborescenceMap. |
69 /// \param digraph is the graph, to which we would like to |
70 /// \param digraph The digraph to which we would like to calculate |
70 /// calculate the \c ArborescenceMap. |
71 /// the \c ArborescenceMap. |
71 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ |
72 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ |
72 return new ArborescenceMap(digraph); |
73 return new ArborescenceMap(digraph); |
73 } |
74 } |
74 |
75 |
75 /// \brief The type of the \c PredMap |
76 /// \brief The type of the \c PredMap |
76 /// |
77 /// |
77 /// The type of the \c PredMap. It is a node map with an arc value type. |
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. |
78 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
81 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
79 |
82 |
80 /// \brief Instantiates a \c PredMap. |
83 /// \brief Instantiates a \c PredMap. |
81 /// |
84 /// |
82 /// This function instantiates a \c PredMap. |
85 /// This function instantiates a \c PredMap. |
90 |
93 |
91 /// \ingroup spantree |
94 /// \ingroup spantree |
92 /// |
95 /// |
93 /// \brief Minimum Cost Arborescence algorithm class. |
96 /// \brief Minimum Cost Arborescence algorithm class. |
94 /// |
97 /// |
95 /// This class provides an efficient implementation of |
98 /// This class provides an efficient implementation of the |
96 /// Minimum Cost Arborescence algorithm. The arborescence is a tree |
99 /// Minimum Cost Arborescence algorithm. The arborescence is a tree |
97 /// which is directed from a given source node of the digraph. One or |
100 /// 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 |
101 /// more sources should be given to the algorithm and it will calculate |
99 /// the minimum cost subgraph which are union of arborescences with the |
102 /// the minimum cost subgraph that is the union of arborescences with the |
100 /// given sources and spans all the nodes which are reachable from the |
103 /// 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). |
104 /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e). |
102 /// |
105 /// |
103 /// The algorithm provides also an optimal dual solution, therefore |
106 /// The algorithm also provides an optimal dual solution, therefore |
104 /// the optimality of the solution can be checked. |
107 /// the optimality of the solution can be checked. |
105 /// |
108 /// |
106 /// \param GR The digraph type the algorithm runs on. The default value |
109 /// \param GR The digraph type the algorithm runs on. |
107 /// is \ref ListDigraph. |
110 /// \param CM A read-only arc map storing the costs of the |
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 |
111 /// 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 |
112 /// relatively time consuming process to compute the arc costs if |
111 /// it is necessary. The default map type is \ref |
113 /// it is necessary. The default map type is \ref |
112 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". |
114 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". |
113 /// \param TR Traits class to set various data types used |
115 /// \param TR Traits class to set various data types used |
114 /// by the algorithm. The default traits class is |
116 /// by the algorithm. The default traits class is |
115 /// \ref MinCostArborescenceDefaultTraits |
117 /// \ref MinCostArborescenceDefaultTraits |
116 /// "MinCostArborescenceDefaultTraits<GR, CM>". See \ref |
118 /// "MinCostArborescenceDefaultTraits<GR, CM>". |
117 /// MinCostArborescenceDefaultTraits for the documentation of a |
|
118 /// MinCostArborescence traits class. |
|
119 #ifndef DOXYGEN |
119 #ifndef DOXYGEN |
120 template <typename GR = ListDigraph, |
120 template <typename GR, |
121 typename CM = typename GR::template ArcMap<int>, |
121 typename CM = typename GR::template ArcMap<int>, |
122 typename TR = |
122 typename TR = |
123 MinCostArborescenceDefaultTraits<GR, CM> > |
123 MinCostArborescenceDefaultTraits<GR, CM> > |
124 #else |
124 #else |
125 template <typename GR, typename CM, typedef TR> |
125 template <typename GR, typename CM, typedef TR> |
126 #endif |
126 #endif |
127 class MinCostArborescence { |
127 class MinCostArborescence { |
128 public: |
128 public: |
129 |
129 |
130 /// The traits. |
130 /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" |
|
131 /// of the algorithm. |
131 typedef TR Traits; |
132 typedef TR Traits; |
132 /// The type of the underlying digraph. |
133 /// The type of the underlying digraph. |
133 typedef typename Traits::Digraph Digraph; |
134 typedef typename Traits::Digraph Digraph; |
134 /// The type of the map that stores the arc costs. |
135 /// The type of the map that stores the arc costs. |
135 typedef typename Traits::CostMap CostMap; |
136 typedef typename Traits::CostMap CostMap; |
393 /// \name Named Template Parameters |
394 /// \name Named Template Parameters |
394 |
395 |
395 /// @{ |
396 /// @{ |
396 |
397 |
397 template <class T> |
398 template <class T> |
398 struct DefArborescenceMapTraits : public Traits { |
399 struct SetArborescenceMapTraits : public Traits { |
399 typedef T ArborescenceMap; |
400 typedef T ArborescenceMap; |
400 static ArborescenceMap *createArborescenceMap(const Digraph &) |
401 static ArborescenceMap *createArborescenceMap(const Digraph &) |
401 { |
402 { |
402 LEMON_ASSERT(false, "ArborescenceMap is not initialized"); |
403 LEMON_ASSERT(false, "ArborescenceMap is not initialized"); |
403 return 0; // ignore warnings |
404 return 0; // ignore warnings |
404 } |
405 } |
405 }; |
406 }; |
406 |
407 |
407 /// \brief \ref named-templ-param "Named parameter" for |
408 /// \brief \ref named-templ-param "Named parameter" for |
408 /// setting ArborescenceMap type |
409 /// setting \c ArborescenceMap type |
409 /// |
410 /// |
410 /// \ref named-templ-param "Named parameter" for setting |
411 /// \ref named-templ-param "Named parameter" for setting |
411 /// ArborescenceMap type |
412 /// \c ArborescenceMap type. |
|
413 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept, |
|
414 /// and its value type must be \c bool (or convertible). |
|
415 /// Initially it will be set to \c false on each arc, |
|
416 /// then it will be set on each arborescence arc once. |
412 template <class T> |
417 template <class T> |
413 struct DefArborescenceMap |
418 struct SetArborescenceMap |
414 : public MinCostArborescence<Digraph, CostMap, |
419 : public MinCostArborescence<Digraph, CostMap, |
415 DefArborescenceMapTraits<T> > { |
420 SetArborescenceMapTraits<T> > { |
416 }; |
421 }; |
417 |
422 |
418 template <class T> |
423 template <class T> |
419 struct DefPredMapTraits : public Traits { |
424 struct SetPredMapTraits : public Traits { |
420 typedef T PredMap; |
425 typedef T PredMap; |
421 static PredMap *createPredMap(const Digraph &) |
426 static PredMap *createPredMap(const Digraph &) |
422 { |
427 { |
423 LEMON_ASSERT(false, "PredMap is not initialized"); |
428 LEMON_ASSERT(false, "PredMap is not initialized"); |
|
429 return 0; // ignore warnings |
424 } |
430 } |
425 }; |
431 }; |
426 |
432 |
427 /// \brief \ref named-templ-param "Named parameter" for |
433 /// \brief \ref named-templ-param "Named parameter" for |
428 /// setting PredMap type |
434 /// setting \c PredMap type |
429 /// |
435 /// |
430 /// \ref named-templ-param "Named parameter" for setting |
436 /// \ref named-templ-param "Named parameter" for setting |
431 /// PredMap type |
437 /// \c PredMap type. |
|
438 /// It must meet the \ref concepts::WriteMap "WriteMap" concept, |
|
439 /// and its value type must be the \c Arc type of the digraph. |
432 template <class T> |
440 template <class T> |
433 struct DefPredMap |
441 struct SetPredMap |
434 : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > { |
442 : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > { |
435 }; |
443 }; |
436 |
444 |
437 /// @} |
445 /// @} |
438 |
446 |
439 /// \brief Constructor. |
447 /// \brief Constructor. |
462 local_arborescence = false; |
470 local_arborescence = false; |
463 _arborescence = &m; |
471 _arborescence = &m; |
464 return *this; |
472 return *this; |
465 } |
473 } |
466 |
474 |
467 /// \brief Sets the arborescence map. |
475 /// \brief Sets the predecessor map. |
468 /// |
476 /// |
469 /// Sets the arborescence map. |
477 /// Sets the predecessor map. |
470 /// \return <tt>(*this)</tt> |
478 /// \return <tt>(*this)</tt> |
471 MinCostArborescence& predMap(PredMap& m) { |
479 MinCostArborescence& predMap(PredMap& m) { |
472 if (local_pred) { |
480 if (local_pred) { |
473 delete _pred; |
481 delete _pred; |
474 } |
482 } |
475 local_pred = false; |
483 local_pred = false; |
476 _pred = &m; |
484 _pred = &m; |
477 return *this; |
485 return *this; |
478 } |
486 } |
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 |
487 |
633 /// \name Execution Control |
488 /// \name Execution Control |
634 /// The simplest way to execute the algorithm is to use |
489 /// The simplest way to execute the algorithm is to use |
635 /// one of the member functions called \c run(...). \n |
490 /// one of the member functions called \c run(...). \n |
636 /// If you need more control on the execution, |
491 /// If you need more control on the execution, |
752 /// \code |
608 /// \code |
753 /// mca.init(); |
609 /// mca.init(); |
754 /// mca.addSource(s); |
610 /// mca.addSource(s); |
755 /// mca.start(); |
611 /// mca.start(); |
756 /// \endcode |
612 /// \endcode |
757 void run(Node node) { |
613 void run(Node s) { |
758 init(); |
614 init(); |
759 addSource(node); |
615 addSource(s); |
760 start(); |
616 start(); |
761 } |
617 } |
762 |
618 |
763 ///@} |
619 ///@} |
|
620 |
|
621 /// \name Query Functions |
|
622 /// The result of the %MinCostArborescence algorithm can be obtained |
|
623 /// using these functions.\n |
|
624 /// Either run() or start() must be called before using them. |
|
625 |
|
626 /// @{ |
|
627 |
|
628 /// \brief Returns the cost of the arborescence. |
|
629 /// |
|
630 /// Returns the cost of the arborescence. |
|
631 Value arborescenceCost() const { |
|
632 Value sum = 0; |
|
633 for (ArcIt it(*_digraph); it != INVALID; ++it) { |
|
634 if (arborescence(it)) { |
|
635 sum += (*_cost)[it]; |
|
636 } |
|
637 } |
|
638 return sum; |
|
639 } |
|
640 |
|
641 /// \brief Returns \c true if the arc is in the arborescence. |
|
642 /// |
|
643 /// Returns \c true if the given arc is in the arborescence. |
|
644 /// \param arc An arc of the digraph. |
|
645 /// \pre \ref run() must be called before using this function. |
|
646 bool arborescence(Arc arc) const { |
|
647 return (*_pred)[_digraph->target(arc)] == arc; |
|
648 } |
|
649 |
|
650 /// \brief Returns a const reference to the arborescence map. |
|
651 /// |
|
652 /// Returns a const reference to the arborescence map. |
|
653 /// \pre \ref run() must be called before using this function. |
|
654 const ArborescenceMap& arborescenceMap() const { |
|
655 return *_arborescence; |
|
656 } |
|
657 |
|
658 /// \brief Returns the predecessor arc of the given node. |
|
659 /// |
|
660 /// Returns the predecessor arc of the given node. |
|
661 /// \pre \ref run() must be called before using this function. |
|
662 Arc pred(Node node) const { |
|
663 return (*_pred)[node]; |
|
664 } |
|
665 |
|
666 /// \brief Returns a const reference to the pred map. |
|
667 /// |
|
668 /// Returns a const reference to the pred map. |
|
669 /// \pre \ref run() must be called before using this function. |
|
670 const PredMap& predMap() const { |
|
671 return *_pred; |
|
672 } |
|
673 |
|
674 /// \brief Indicates that a node is reachable from the sources. |
|
675 /// |
|
676 /// Indicates that a node is reachable from the sources. |
|
677 bool reached(Node node) const { |
|
678 return (*_node_order)[node] != -3; |
|
679 } |
|
680 |
|
681 /// \brief Indicates that a node is processed. |
|
682 /// |
|
683 /// Indicates that a node is processed. The arborescence path exists |
|
684 /// from the source to the given node. |
|
685 bool processed(Node node) const { |
|
686 return (*_node_order)[node] == -1; |
|
687 } |
|
688 |
|
689 /// \brief Returns the number of the dual variables in basis. |
|
690 /// |
|
691 /// Returns the number of the dual variables in basis. |
|
692 int dualNum() const { |
|
693 return _dual_variables.size(); |
|
694 } |
|
695 |
|
696 /// \brief Returns the value of the dual solution. |
|
697 /// |
|
698 /// Returns the value of the dual solution. It should be |
|
699 /// equal to the arborescence value. |
|
700 Value dualValue() const { |
|
701 Value sum = 0; |
|
702 for (int i = 0; i < int(_dual_variables.size()); ++i) { |
|
703 sum += _dual_variables[i].value; |
|
704 } |
|
705 return sum; |
|
706 } |
|
707 |
|
708 /// \brief Returns the number of the nodes in the dual variable. |
|
709 /// |
|
710 /// Returns the number of the nodes in the dual variable. |
|
711 int dualSize(int k) const { |
|
712 return _dual_variables[k].end - _dual_variables[k].begin; |
|
713 } |
|
714 |
|
715 /// \brief Returns the value of the dual variable. |
|
716 /// |
|
717 /// Returns the the value of the dual variable. |
|
718 Value dualValue(int k) const { |
|
719 return _dual_variables[k].value; |
|
720 } |
|
721 |
|
722 /// \brief LEMON iterator for getting a dual variable. |
|
723 /// |
|
724 /// This class provides a common style LEMON iterator for getting a |
|
725 /// dual variable of \ref MinCostArborescence algorithm. |
|
726 /// It iterates over a subset of the nodes. |
|
727 class DualIt { |
|
728 public: |
|
729 |
|
730 /// \brief Constructor. |
|
731 /// |
|
732 /// Constructor for getting the nodeset of the dual variable |
|
733 /// of \ref MinCostArborescence algorithm. |
|
734 DualIt(const MinCostArborescence& algorithm, int variable) |
|
735 : _algorithm(&algorithm) |
|
736 { |
|
737 _index = _algorithm->_dual_variables[variable].begin; |
|
738 _last = _algorithm->_dual_variables[variable].end; |
|
739 } |
|
740 |
|
741 /// \brief Conversion to \c Node. |
|
742 /// |
|
743 /// Conversion to \c Node. |
|
744 operator Node() const { |
|
745 return _algorithm->_dual_node_list[_index]; |
|
746 } |
|
747 |
|
748 /// \brief Increment operator. |
|
749 /// |
|
750 /// Increment operator. |
|
751 DualIt& operator++() { |
|
752 ++_index; |
|
753 return *this; |
|
754 } |
|
755 |
|
756 /// \brief Validity checking |
|
757 /// |
|
758 /// Checks whether the iterator is invalid. |
|
759 bool operator==(Invalid) const { |
|
760 return _index == _last; |
|
761 } |
|
762 |
|
763 /// \brief Validity checking |
|
764 /// |
|
765 /// Checks whether the iterator is valid. |
|
766 bool operator!=(Invalid) const { |
|
767 return _index != _last; |
|
768 } |
|
769 |
|
770 private: |
|
771 const MinCostArborescence* _algorithm; |
|
772 int _index, _last; |
|
773 }; |
|
774 |
|
775 /// @} |
764 |
776 |
765 }; |
777 }; |
766 |
778 |
767 /// \ingroup spantree |
779 /// \ingroup spantree |
768 /// |
780 /// |
769 /// \brief Function type interface for MinCostArborescence algorithm. |
781 /// \brief Function type interface for MinCostArborescence algorithm. |
770 /// |
782 /// |
771 /// Function type interface for MinCostArborescence algorithm. |
783 /// Function type interface for MinCostArborescence algorithm. |
772 /// \param digraph The Digraph that the algorithm runs on. |
784 /// \param digraph The digraph the algorithm runs on. |
773 /// \param cost The CostMap of the arcs. |
785 /// \param cost An arc map storing the costs. |
774 /// \param source The source of the arborescence. |
786 /// \param source The source node of the arborescence. |
775 /// \retval arborescence The bool ArcMap which stores the arborescence. |
787 /// \retval arborescence An arc map with \c bool (or convertible) value |
776 /// \return The cost of the arborescence. |
788 /// type that stores the arborescence. |
|
789 /// \return The total cost of the arborescence. |
777 /// |
790 /// |
778 /// \sa MinCostArborescence |
791 /// \sa MinCostArborescence |
779 template <typename Digraph, typename CostMap, typename ArborescenceMap> |
792 template <typename Digraph, typename CostMap, typename ArborescenceMap> |
780 typename CostMap::Value minCostArborescence(const Digraph& digraph, |
793 typename CostMap::Value minCostArborescence(const Digraph& digraph, |
781 const CostMap& cost, |
794 const CostMap& cost, |
782 typename Digraph::Node source, |
795 typename Digraph::Node source, |
783 ArborescenceMap& arborescence) { |
796 ArborescenceMap& arborescence) { |
784 typename MinCostArborescence<Digraph, CostMap> |
797 typename MinCostArborescence<Digraph, CostMap> |
785 ::template DefArborescenceMap<ArborescenceMap> |
798 ::template SetArborescenceMap<ArborescenceMap> |
786 ::Create mca(digraph, cost); |
799 ::Create mca(digraph, cost); |
787 mca.arborescenceMap(arborescence); |
800 mca.arborescenceMap(arborescence); |
788 mca.run(source); |
801 mca.run(source); |
789 return mca.arborescenceValue(); |
802 return mca.arborescenceCost(); |
790 } |
803 } |
791 |
804 |
792 } |
805 } |
793 |
806 |
794 #endif |
807 #endif |