Changeset 606:c5fd2d996909 in lemon for lemon/min_cost_arborescence.h
- Timestamp:
- 03/29/09 23:08:20 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
-
lemon/min_cost_arborescence.h (modified) (8 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/min_cost_arborescence.h
r522 r606 36 36 /// 37 37 /// Default traits class for MinCostArborescence class. 38 /// \param _DigraphDigraph type.39 /// \param _CostMapType of cost map.40 template <class _Digraph, class _CostMap>38 /// \param GR Digraph type. 39 /// \param CM Type of cost map. 40 template <class GR, class CM> 41 41 struct MinCostArborescenceDefaultTraits{ 42 42 43 43 /// \brief The digraph type the algorithm runs on. 44 typedef _DigraphDigraph;44 typedef GR Digraph; 45 45 46 46 /// \brief The type of the map that stores the arc costs. … … 48 48 /// The type of the map that stores the arc costs. 49 49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 50 typedef _CostMapCostMap;50 typedef CM CostMap; 51 51 52 52 /// \brief The value type of the costs. … … 64 64 typedef typename Digraph::template ArcMap<bool> ArborescenceMap; 65 65 66 /// \brief Instantiates a ArborescenceMap.67 /// 68 /// This function instantiates a \ refArborescenceMap.66 /// \brief Instantiates a \c ArborescenceMap. 67 /// 68 /// This function instantiates a \c ArborescenceMap. 69 69 /// \param digraph is the graph, to which we would like to 70 /// calculate the ArborescenceMap.70 /// calculate the \c ArborescenceMap. 71 71 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ 72 72 return new ArborescenceMap(digraph); 73 73 } 74 74 75 /// \brief The type of the PredMap76 /// 77 /// The type of the PredMap. It is a node map with an arc value type.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 78 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 79 79 80 /// \brief Instantiates a PredMap.81 /// 82 /// This function instantiates a \ refPredMap.83 /// \param _digraph is the digraph,to which we would like to define the84 /// PredMap.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 85 static PredMap *createPredMap(const Digraph &digraph){ 86 86 return new PredMap(digraph); … … 99 99 /// the minimum cost subgraph which are union of arborescences with the 100 100 /// given sources and spans all the nodes which are reachable from the 101 /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.101 /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e). 102 102 /// 103 103 /// The algorithm provides also an optimal dual solution, therefore 104 104 /// the optimality of the solution can be checked. 105 105 /// 106 /// \param _DigraphThe digraph type the algorithm runs on. The default value106 /// \param GR The digraph type the algorithm runs on. The default value 107 107 /// is \ref ListDigraph. 108 /// \param _CostMapThis read-only ArcMap determines the costs of the108 /// \param CM This read-only ArcMap determines the costs of the 109 109 /// arcs. It is read once for each arc, so the map may involve in 110 110 /// relatively time consuming process to compute the arc cost if 111 111 /// it is necessary. The default map type is \ref 112 112 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 113 /// \param _TraitsTraits class to set various data types used113 /// \param TR Traits class to set various data types used 114 114 /// by the algorithm. The default traits class is 115 115 /// \ref MinCostArborescenceDefaultTraits 116 /// "MinCostArborescenceDefaultTraits< _Digraph, _CostMap>". See \ref116 /// "MinCostArborescenceDefaultTraits<GR, CM>". See \ref 117 117 /// MinCostArborescenceDefaultTraits for the documentation of a 118 118 /// MinCostArborescence traits class. 119 ///120 /// \author Balazs Dezso121 119 #ifndef DOXYGEN 122 template <typename _Digraph= ListDigraph,123 typename _CostMap = typename _Digraph::template ArcMap<int>,124 typename _Traits=125 MinCostArborescenceDefaultTraits<_Digraph, _CostMap> >120 template <typename GR = ListDigraph, 121 typename CM = typename GR::template ArcMap<int>, 122 typename TR = 123 MinCostArborescenceDefaultTraits<GR, CM> > 126 124 #else 127 template <typename _Digraph, typename _CostMap, typedef _Traits>125 template <typename GR, typename CM, typedef TR> 128 126 #endif 129 127 class MinCostArborescence { … … 131 129 132 130 /// The traits. 133 typedef _TraitsTraits;131 typedef TR Traits; 134 132 /// The type of the underlying digraph. 135 133 typedef typename Traits::Digraph Digraph; … … 441 439 /// \brief Constructor. 442 440 /// 443 /// \param _digraph The digraph the algorithm will run on.444 /// \param _cost The cost map used by the algorithm.441 /// \param digraph The digraph the algorithm will run on. 442 /// \param cost The cost map used by the algorithm. 445 443 MinCostArborescence(const Digraph& digraph, const CostMap& cost) 446 444 : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false), … … 457 455 /// 458 456 /// Sets the arborescence map. 459 /// \return \c (*this)457 /// \return <tt>(*this)</tt> 460 458 MinCostArborescence& arborescenceMap(ArborescenceMap& m) { 461 459 if (local_arborescence) { … … 470 468 /// 471 469 /// Sets the arborescence map. 472 /// \return \c (*this)470 /// \return <tt>(*this)</tt> 473 471 MinCostArborescence& predMap(PredMap& m) { 474 472 if (local_pred) {
Note: See TracChangeset
for help on using the changeset viewer.
