1.1 --- a/lemon/min_cost_arborescence.h Thu Mar 05 10:13:20 2009 +0000
1.2 +++ b/lemon/min_cost_arborescence.h Sun Mar 29 23:08:20 2009 +0200
1.3 @@ -35,19 +35,19 @@
1.4 /// \brief Default traits class for MinCostArborescence class.
1.5 ///
1.6 /// Default traits class for MinCostArborescence class.
1.7 - /// \param _Digraph Digraph type.
1.8 - /// \param _CostMap Type of cost map.
1.9 - template <class _Digraph, class _CostMap>
1.10 + /// \param GR Digraph type.
1.11 + /// \param CM Type of cost map.
1.12 + template <class GR, class CM>
1.13 struct MinCostArborescenceDefaultTraits{
1.14
1.15 /// \brief The digraph type the algorithm runs on.
1.16 - typedef _Digraph Digraph;
1.17 + typedef GR Digraph;
1.18
1.19 /// \brief The type of the map that stores the arc costs.
1.20 ///
1.21 /// The type of the map that stores the arc costs.
1.22 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.23 - typedef _CostMap CostMap;
1.24 + typedef CM CostMap;
1.25
1.26 /// \brief The value type of the costs.
1.27 ///
1.28 @@ -63,25 +63,25 @@
1.29 /// arc. After it will set all arborescence arcs once.
1.30 typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
1.31
1.32 - /// \brief Instantiates a ArborescenceMap.
1.33 + /// \brief Instantiates a \c ArborescenceMap.
1.34 ///
1.35 - /// This function instantiates a \ref ArborescenceMap.
1.36 + /// This function instantiates a \c ArborescenceMap.
1.37 /// \param digraph is the graph, to which we would like to
1.38 - /// calculate the ArborescenceMap.
1.39 + /// calculate the \c ArborescenceMap.
1.40 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
1.41 return new ArborescenceMap(digraph);
1.42 }
1.43
1.44 - /// \brief The type of the PredMap
1.45 + /// \brief The type of the \c PredMap
1.46 ///
1.47 - /// The type of the PredMap. It is a node map with an arc value type.
1.48 + /// The type of the \c PredMap. It is a node map with an arc value type.
1.49 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.50
1.51 - /// \brief Instantiates a PredMap.
1.52 + /// \brief Instantiates a \c PredMap.
1.53 ///
1.54 - /// This function instantiates a \ref PredMap.
1.55 - /// \param _digraph is the digraph, to which we would like to define the
1.56 - /// PredMap.
1.57 + /// This function instantiates a \c PredMap.
1.58 + /// \param digraph The digraph to which we would like to define the
1.59 + /// \c PredMap.
1.60 static PredMap *createPredMap(const Digraph &digraph){
1.61 return new PredMap(digraph);
1.62 }
1.63 @@ -98,39 +98,37 @@
1.64 /// more sources should be given for the algorithm and it will calculate
1.65 /// the minimum cost subgraph which are union of arborescences with the
1.66 /// given sources and spans all the nodes which are reachable from the
1.67 - /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.
1.68 + /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
1.69 ///
1.70 /// The algorithm provides also an optimal dual solution, therefore
1.71 /// the optimality of the solution can be checked.
1.72 ///
1.73 - /// \param _Digraph The digraph type the algorithm runs on. The default value
1.74 + /// \param GR The digraph type the algorithm runs on. The default value
1.75 /// is \ref ListDigraph.
1.76 - /// \param _CostMap This read-only ArcMap determines the costs of the
1.77 + /// \param CM This read-only ArcMap determines the costs of the
1.78 /// arcs. It is read once for each arc, so the map may involve in
1.79 /// relatively time consuming process to compute the arc cost if
1.80 /// it is necessary. The default map type is \ref
1.81 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
1.82 - /// \param _Traits Traits class to set various data types used
1.83 + /// \param TR Traits class to set various data types used
1.84 /// by the algorithm. The default traits class is
1.85 /// \ref MinCostArborescenceDefaultTraits
1.86 - /// "MinCostArborescenceDefaultTraits<_Digraph, _CostMap>". See \ref
1.87 + /// "MinCostArborescenceDefaultTraits<GR, CM>". See \ref
1.88 /// MinCostArborescenceDefaultTraits for the documentation of a
1.89 /// MinCostArborescence traits class.
1.90 - ///
1.91 - /// \author Balazs Dezso
1.92 #ifndef DOXYGEN
1.93 - template <typename _Digraph = ListDigraph,
1.94 - typename _CostMap = typename _Digraph::template ArcMap<int>,
1.95 - typename _Traits =
1.96 - MinCostArborescenceDefaultTraits<_Digraph, _CostMap> >
1.97 + template <typename GR = ListDigraph,
1.98 + typename CM = typename GR::template ArcMap<int>,
1.99 + typename TR =
1.100 + MinCostArborescenceDefaultTraits<GR, CM> >
1.101 #else
1.102 - template <typename _Digraph, typename _CostMap, typedef _Traits>
1.103 + template <typename GR, typename CM, typedef TR>
1.104 #endif
1.105 class MinCostArborescence {
1.106 public:
1.107
1.108 /// The traits.
1.109 - typedef _Traits Traits;
1.110 + typedef TR Traits;
1.111 /// The type of the underlying digraph.
1.112 typedef typename Traits::Digraph Digraph;
1.113 /// The type of the map that stores the arc costs.
1.114 @@ -440,8 +438,8 @@
1.115
1.116 /// \brief Constructor.
1.117 ///
1.118 - /// \param _digraph The digraph the algorithm will run on.
1.119 - /// \param _cost The cost map used by the algorithm.
1.120 + /// \param digraph The digraph the algorithm will run on.
1.121 + /// \param cost The cost map used by the algorithm.
1.122 MinCostArborescence(const Digraph& digraph, const CostMap& cost)
1.123 : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
1.124 _arborescence(0), local_arborescence(false),
1.125 @@ -456,7 +454,7 @@
1.126 /// \brief Sets the arborescence map.
1.127 ///
1.128 /// Sets the arborescence map.
1.129 - /// \return \c (*this)
1.130 + /// \return <tt>(*this)</tt>
1.131 MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
1.132 if (local_arborescence) {
1.133 delete _arborescence;
1.134 @@ -469,7 +467,7 @@
1.135 /// \brief Sets the arborescence map.
1.136 ///
1.137 /// Sets the arborescence map.
1.138 - /// \return \c (*this)
1.139 + /// \return <tt>(*this)</tt>
1.140 MinCostArborescence& predMap(PredMap& m) {
1.141 if (local_pred) {
1.142 delete _pred;