Changeset 885:5e59c44b6ba2 in lemon-0.x

Timestamp:

09/19/04 17:24:56 (21 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

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

Message:

Kruskal cleanup:

• resolved the NonConstMapWr? bug
• docs added for NonConstMapWr? and KruskalSequenceOut?

Location:

src

Files:

• hugo/kruskal.h (modified) (9 diffs)
• test/kruskal_test.cc (modified) (1 diff)

src/hugo/kruskal.h

@@ -82 +82 @@
   /* A work-around for running Kruskal with const-reference bool maps... */
 
-  ///\bug What is this? Or why doesn't it work?
-  ///
+  /// Helper class for calling kruskal with "constant" output map.
+
+  /// Helper class for calling kruskal with output maps constructed
+  /// on-the-fly.
+  ///
+  /// A typical examle is the following call:
+  /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
+  /// Here, the third argument is a temporary object (which wraps around an
+  /// iterator with a writable bool map interface), and thus by rules of C++
+  /// is a \c const object. To enable call like this exist this class and
+  /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
+  /// third argument.
   template<class Map>
   class NonConstMapWr {
@@ -98 +108 @@
   template <class GR, class IN, class OUT>
   inline
-  typename IN::ValueType
-  kruskal(GR const& G, IN const& edges, 
-          OUT const& out_map)
+  typename IN::value_type::second_type
+  kruskal(GR const& G, IN const& edges, OUT const& out_map)
   {
     NonConstMapWr<OUT> map_wr(out_map);
@@ -152 +161 @@
       typedef typename GR::EdgeIt EdgeIt;
       
-      this->clear();
-      for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
+      for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
       sort();
     }
@@ -185 +193 @@
   
   
-  /* ** ** Output-objects: simple writable bool maps** ** */
+
+  /* ** ** Output-objects: simple writable bool maps ** ** */
   
+
+
   /// A writable bool-map that makes a sequence of "true" keys
 
   /// A writable bool-map that creates a sequence out of keys that receives
   /// the value "true".
+  ///
+  /// \sa makeKruskalSequenceOutput()
+  ///
+  /// Very often, when looking for a min cost spanning tree, we want as
+  /// output a container containing the edges of the found tree. For this
+  /// purpose exist this class that wraps around an STL iterator with a
+  /// writable bool map interface. When a key gets value "true" this key
+  /// is added to sequence pointed by the iterator.
+  ///
+  /// A typical usage:
+  /// \code
+  /// std::vector<Graph::Edge> v;
+  /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
+  /// \endcode
+  /// 
+  /// For the most common case, when the input is given by a simple edge
+  /// map and the output is a sequence of the tree edges, a special
+  /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
+  ///
   /// \warning Not a regular property map, as it doesn't know its KeyType
-  /// \bug Missing documentation.
-  /// \todo This class may be of wider usage, therefore it could move to
-  /// <tt>maps.h</tt>
+
   template<class Iterator>
-  class SequenceOutput {
+  class KruskalSequenceOutput {
     mutable Iterator it;
 
@@ -202 +230 @@
     typedef bool ValueType;
 
-    SequenceOutput(Iterator const &_it) : it(_it) {}
+    KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
 
     template<typename KeyType>
@@ -210 +238 @@
   template<class Iterator>
   inline
-  SequenceOutput<Iterator>
-  makeSequenceOutput(Iterator it) {
-    return SequenceOutput<Iterator>(it);
-  }
+  KruskalSequenceOutput<Iterator>
+  makeKruskalSequenceOutput(Iterator it) {
+    return KruskalSequenceOutput<Iterator>(it);
+  }
+
+
 
   /* ** ** Wrapper funtions ** ** */
+
 
 
@@ -239 +270 @@
   ///
   /// \return The cost of the found tree.
-
 
   template <class GR, class IN, class RET>
@@ -285 +315 @@
   ///
   /// \bug its name does not follow the coding style.
+
   template <class GR, class IN, class RET>
   inline
@@ -292 +323 @@
                              RET out)
   {
-    SequenceOutput<RET> _out(out);
-    return kruskal(G,
-                   KruskalMapInput<GR,IN>(G, in),
-                   _out);
+    KruskalSequenceOutput<RET> _out(out);
+    return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
   }
 

src/test/kruskal_test.cc

@@ -82 +82 @@
         "Total cost should be -31.");
 
+  tree_edge_vec.clear();
+
+  //The above test could also be coded like this:
+  check(kruskal(G,
+                makeKruskalMapInput(G, edge_cost_map),
+                makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
+        ==-31,
+        "Total cost should be -31.");
+
   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");