Changeset 824:157115b5814a in lemon-0.x

Timestamp:

09/09/04 09:09:11 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1120

Message:

Shorter template parameter names to be more readable in Doxygen.

File:

• src/hugo/kruskal.h (modified) (15 diffs)

src/hugo/kruskal.h

@@ -22 +22 @@
 ///Kruskal's algorithm to compute a minimum cost tree.
 
+///\weakgroup spantree
 namespace hugo {
 
@@ -35 +36 @@
   /// \param in This object is used to describe the edge costs. It must
   /// be an STL compatible 'Forward Container'
-  /// with <tt>std::pair<Graph::Edge,X></tt> as its <tt>value_type</tt>,
+  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
   /// where X is the type of the costs. It must contain every edge in
   /// cost-ascending order.
@@ -53 +54 @@
   /// \return The cost of the found tree.
 
-  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
-  typename InputEdgeOrder::value_type::second_type
-  kruskal(Graph const& G, InputEdgeOrder const& in, 
-                 OutBoolMap& out)
+  template <class GR, class IN, class OUT>
+  typename IN::value_type::second_type
+  kruskal(GR const& G, IN const& in, 
+                 OUT& out)
   {
-    typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
-    typedef typename Graph::template NodeMap<int> NodeIntMap;
-    typedef typename Graph::Node Node;
+    typedef typename IN::value_type::second_type EdgeCost;
+    typedef typename GR::template NodeMap<int> NodeIntMap;
+    typedef typename GR::Node Node;
 
     NodeIntMap comp(G, -1);
@@ -66 +67 @@
       
     EdgeCost tot_cost = 0;
-    for (typename InputEdgeOrder::const_iterator p = in.begin(); 
+    for (typename IN::const_iterator p = in.begin(); 
          p!=in.end(); ++p ) {
       if ( uf.join(G.head((*p).first),
@@ -84 +85 @@
   ///\bug What is this? Or why doesn't it work?
   ///
-  template<typename Map>
+  template<class Map>
   class NonConstMapWr {
     const Map &m;
@@ -92 +93 @@
     NonConstMapWr(const Map &_m) : m(_m) {}
 
-    template<typename KeyType>
+    template<class KeyType>
     void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
   };
 
-  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
-  inline
-  typename InputEdgeOrder::ValueType
-  kruskal(Graph const& G, InputEdgeOrder const& edges, 
-          OutBoolMap const& out_map)
+  template <class GR, class IN, class OUT>
+  inline
+  typename IN::ValueType
+  kruskal(GR const& G, IN const& edges, 
+          OUT const& out_map)
   {
-    NonConstMapWr<OutBoolMap> map_wr(out_map);
+    NonConstMapWr<OUT> map_wr(out_map);
     return kruskal(G, edges, map_wr);
   }  
@@ -116 +117 @@
   /// \sa makeKruskalMapInput()
   ///
-  ///\param Graph The type of the graph the algorithm runs on.
+  ///\param GR The type of the graph the algorithm runs on.
   ///\param Map An edge map containing the cost of the edges.
   ///\par
@@ -124 +125 @@
   ///computing the total cost of the tree).
   ///
-  template<typename Graph, typename Map>
+  template<class GR, class Map>
   class KruskalMapInput
-    : public std::vector< std::pair<typename Graph::Edge,
+    : public std::vector< std::pair<typename GR::Edge,
                                     typename Map::ValueType> > {
     
   public:
-    typedef std::vector< std::pair<typename Graph::Edge,
+    typedef std::vector< std::pair<typename GR::Edge,
                                    typename Map::ValueType> > Parent;
     typedef typename Parent::value_type value_type;
@@ -149 +150 @@
     }
 
-    KruskalMapInput(Graph const& G, Map const& m) {
-      typedef typename Graph::EdgeIt EdgeIt;
+    KruskalMapInput(GR const& G, Map const& m) {
+      typedef typename GR::EdgeIt EdgeIt;
       
       this->clear();
@@ -177 +178 @@
   ///\return An appropriate input source for \ref kruskal().
   ///
-  template<typename Graph, typename Map>
-  inline
-  KruskalMapInput<Graph,Map> makeKruskalMapInput(const Graph &G,const Map &m)
+  template<class GR, class Map>
+  inline
+  KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
   {
-    return KruskalMapInput<Graph,Map>(G,m);
+    return KruskalMapInput<GR,Map>(G,m);
   }
   
@@ -195 +196 @@
   /// \todo This class may be of wider usage, therefore it could move to
   /// <tt>maps.h</tt>
-  template<typename Iterator>
+  template<class Iterator>
   class SequenceOutput {
     mutable Iterator it;
@@ -208 +209 @@
   };
 
-  template<typename Iterator>
+  template<class Iterator>
   inline
   SequenceOutput<Iterator>
@@ -241 +242 @@
 
 
-  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
-  inline
-  typename EdgeCostMap::ValueType
-  kruskalEdgeMap(Graph const& G,
-                 EdgeCostMap const& in,
-                 RetEdgeBoolMap &out) {
+  template <class GR, class IN, class RET>
+  inline
+  typename IN::ValueType
+  kruskalEdgeMap(GR const& G,
+                 IN const& in,
+                 RET &out) {
     return kruskal(G,
-                   KruskalMapInput<Graph,EdgeCostMap>(G,in),
+                   KruskalMapInput<GR,IN>(G,in),
                    out);
   }
@@ -267 +268 @@
   ///
   /// \retval out This must be an iteraror of an STL Container with
-  /// <tt>Graph::Edge</tt> as its <tt>value_type</tt>.
+  /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
   /// The algorithm copies the elements of the found tree into this sequence.
   /// For example, if we know that the spanning tree of the graph \c G has
   /// say 53 edges then
-  /// we can put its edges into a vector \c tree with a code like this.
+  /// we can put its edges into a STL vector \c tree with a code like this.
   /// \code
   /// std::vector<Edge> tree(53);
@@ -285 +286 @@
   ///
   /// \bug its name does not follow the coding style.
-  template <typename Graph, typename EdgeCostMap, typename RetIterator>
-  inline
-  typename EdgeCostMap::ValueType
-  kruskalEdgeMap_IteratorOut(const Graph& G,
-                             const EdgeCostMap& in,
-                             RetIterator out)
+  template <class GR, class IN, class RET>
+  inline
+  typename IN::ValueType
+  kruskalEdgeMap_IteratorOut(const GR& G,
+                             const IN& in,
+                             RET out)
   {
-    SequenceOutput<RetIterator> _out(out);
+    SequenceOutput<RET> _out(out);
     return kruskal(G,
-                   KruskalMapInput<Graph, EdgeCostMap>(G, in),
+                   KruskalMapInput<GR,IN>(G, in),
                    _out);
   }