equal
deleted
inserted
replaced
88 |
88 |
89 }; |
89 }; |
90 |
90 |
91 /// \ingroup spantree |
91 /// \ingroup spantree |
92 /// |
92 /// |
93 /// \brief %MinCostArborescence algorithm class. |
93 /// \brief Minimum Cost Arborescence algorithm class. |
94 /// |
94 /// |
95 /// This class provides an efficient implementation of |
95 /// This class provides an efficient implementation of |
96 /// %MinCostArborescence algorithm. The arborescence is a tree |
96 /// Minimum Cost Arborescence algorithm. The arborescence is a tree |
97 /// which is directed from a given source node of the digraph. One or |
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 |
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 |
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 |
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). |
101 /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e). |
388 } |
388 } |
389 |
389 |
390 |
390 |
391 public: |
391 public: |
392 |
392 |
393 /// \name Named template parameters |
393 /// \name Named Template Parameters |
394 |
394 |
395 /// @{ |
395 /// @{ |
396 |
396 |
397 template <class T> |
397 template <class T> |
398 struct DefArborescenceMapTraits : public Traits { |
398 struct DefArborescenceMapTraits : public Traits { |
628 int _index, _last; |
628 int _index, _last; |
629 }; |
629 }; |
630 |
630 |
631 /// @} |
631 /// @} |
632 |
632 |
633 /// \name Execution control |
633 /// \name Execution Control |
634 /// The simplest way to execute the algorithm is to use |
634 /// The simplest way to execute the algorithm is to use |
635 /// one of the member functions called \c run(...). \n |
635 /// one of the member functions called \c run(...). \n |
636 /// If you need more control on the execution, |
636 /// If you need more control on the execution, |
637 /// first you must call \ref init(), then you can add several |
637 /// first you must call \ref init(), then you can add several |
638 /// source nodes with \ref addSource(). |
638 /// source nodes with \ref addSource(). |