1.1 --- a/lemon/max_matching.h Thu Mar 05 10:13:20 2009 +0000
1.2 +++ b/lemon/max_matching.h Sun Mar 29 23:08:20 2009 +0200
1.3 @@ -55,12 +55,12 @@
1.4 /// tight. This decomposition can be attained by calling \c
1.5 /// decomposition() after running the algorithm.
1.6 ///
1.7 - /// \param _Graph The graph type the algorithm runs on.
1.8 - template <typename _Graph>
1.9 + /// \param GR The graph type the algorithm runs on.
1.10 + template <typename GR>
1.11 class MaxMatching {
1.12 public:
1.13
1.14 - typedef _Graph Graph;
1.15 + typedef GR Graph;
1.16 typedef typename Graph::template NodeMap<typename Graph::Arc>
1.17 MatchingMap;
1.18
1.19 @@ -463,7 +463,7 @@
1.20 /// Initialize the matching from a \c bool valued \c Edge map. This
1.21 /// map must have the property that there are no two incident edges
1.22 /// with true value, ie. it contains a matching.
1.23 - /// \return %True if the map contains a matching.
1.24 + /// \return \c true if the map contains a matching.
1.25 template <typename MatchingMap>
1.26 bool matchingInit(const MatchingMap& matching) {
1.27 createStructures();
1.28 @@ -613,7 +613,7 @@
1.29 /// This class provides an efficient implementation of Edmond's
1.30 /// maximum weighted matching algorithm. The implementation is based
1.31 /// on extensive use of priority queues and provides
1.32 - /// \f$O(nm\log(n))\f$ time complexity.
1.33 + /// \f$O(nm\log n)\f$ time complexity.
1.34 ///
1.35 /// The maximum weighted matching problem is to find undirected
1.36 /// edges in the graph with maximum overall weight and no two of
1.37 @@ -647,13 +647,16 @@
1.38 /// "BlossomIt" nested class, which is able to iterate on the nodes
1.39 /// of a blossom. If the value type is integral then the dual
1.40 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
1.41 - template <typename _Graph,
1.42 - typename _WeightMap = typename _Graph::template EdgeMap<int> >
1.43 + template <typename GR,
1.44 + typename WM = typename GR::template EdgeMap<int> >
1.45 class MaxWeightedMatching {
1.46 public:
1.47
1.48 - typedef _Graph Graph;
1.49 - typedef _WeightMap WeightMap;
1.50 + ///\e
1.51 + typedef GR Graph;
1.52 + ///\e
1.53 + typedef WM WeightMap;
1.54 + ///\e
1.55 typedef typename WeightMap::Value Value;
1.56
1.57 /// \brief Scaling factor for dual solution
1.58 @@ -1957,7 +1960,7 @@
1.59 /// This class provides an efficient implementation of Edmond's
1.60 /// maximum weighted perfect matching algorithm. The implementation
1.61 /// is based on extensive use of priority queues and provides
1.62 - /// \f$O(nm\log(n))\f$ time complexity.
1.63 + /// \f$O(nm\log n)\f$ time complexity.
1.64 ///
1.65 /// The maximum weighted matching problem is to find undirected
1.66 /// edges in the graph with maximum overall weight and no two of
1.67 @@ -1990,13 +1993,13 @@
1.68 /// "BlossomIt" nested class which is able to iterate on the nodes
1.69 /// of a blossom. If the value type is integral then the dual
1.70 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
1.71 - template <typename _Graph,
1.72 - typename _WeightMap = typename _Graph::template EdgeMap<int> >
1.73 + template <typename GR,
1.74 + typename WM = typename GR::template EdgeMap<int> >
1.75 class MaxWeightedPerfectMatching {
1.76 public:
1.77
1.78 - typedef _Graph Graph;
1.79 - typedef _WeightMap WeightMap;
1.80 + typedef GR Graph;
1.81 + typedef WM WeightMap;
1.82 typedef typename WeightMap::Value Value;
1.83
1.84 /// \brief Scaling factor for dual solution