# HG changeset patch
# User alpar
# Date 1090602803 0
# Node ID 2d867176d10e7a6e9e5166b2f7d6579ba3434dfc
# Parent  ba76a7f56b2357c80f4f809662db7a78dbfa1ae7
Several changes in Kruskal alg.
- Input object interface was changed to an STL compatible one.
- template parameters of class KruskalPairVec has been simplified.
- (the most of) the names meet the naming conventions.
- a lot of (but still not enough) documentation has been added.
- class KruskalMapVec has been commented out.

diff -r ba76a7f56b23 -r 2d867176d10e src/work/johanna/kruskal.h
--- a/src/work/johanna/kruskal.h	Fri Jul 23 16:58:02 2004 +0000
+++ b/src/work/johanna/kruskal.h	Fri Jul 23 17:13:23 2004 +0000
@@ -3,38 +3,55 @@
 #define HUGO_KRUSKAL_H
 
 #include <algorithm>
-#include <unionfind.h>
-#include <for_each_macros.h>
+#include <hugo/unionfind.h>
 
 ///\file
 ///\brief Kruskal's algorithm to compute a minimum cost tree
 
 namespace hugo {
 
-  /// Kruskal's algorithm to compute a minimum cost tree
+  /// Kruskal's algorithm to find a minimum cost tree of a graph.
+
+  /// This function runs Kruskal's algorithm to find a minimum cost tree.
+  /// \param G The graph the algorithm runs on.
+  /// \param in This object is used to describe the edge costs. It must
+  /// be an STL 'forward container'
+  /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
+  /// where X is the type of the costs. It must contain every edge in
+  /// cost-ascending order.
+  /// \retval out This must be a writeable EdgeMap. After running the algorithm
+  /// this will contain the found minimum cost spanning tree: the value of an
+  /// edge will be set to \c true if it belongs to the tree, otherwise it will
+  /// be set to \c false. The value of each edge will be set exactly once.\n
+  /// For the sake of simplicity, there is a helper class KruskalPairVec,
+  /// which converts a
+  /// simple EdgeMap to an input of this form. Alternatively, you can use
+  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
+  /// the edge costs are given by an EdgeMap.
+  /// \return The cost of the found tree.
 
   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
-  typename InputEdgeOrder::ValueType
-  Kruskal(Graph const& G, InputEdgeOrder const& edges, 
-	  OutBoolMap& out_map)
+  typename InputEdgeOrder::value_type::second_type
+  kruskal(Graph const& G, InputEdgeOrder const& in, 
+		 OutBoolMap& out)
   {
-    typedef typename InputEdgeOrder::ValueType EdgeCost;
-    typedef typename Graph::NodeMap<int> NodeIntMap;
+    typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
+    typedef typename Graph::template NodeMap<int> NodeIntMap;
     typedef typename Graph::Node Node;
 
-    NodeIntMap comp_map(G, -1);
-    UnionFind<Node,NodeIntMap> uf(comp_map); 
+    NodeIntMap comp(G, -1);
+    UnionFind<Node,NodeIntMap> uf(comp); 
       
     EdgeCost tot_cost = 0;
-    for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
-	 p!=edges.end(); ++p ) {
-      if ( uf.join(G.head(edges.first(p)),
-			     G.tail(edges.first(p))) ) {
-	out_map.set(edges.first(p), true);
-	tot_cost += edges.second(p);
+    for (typename InputEdgeOrder::const_iterator p = in.begin(); 
+	 p!=in.end(); ++p ) {
+      if ( uf.join(G.head((*p).first),
+		   G.tail((*p).first)) ) {
+	out.set((*p).first, true);
+	tot_cost += (*p).second;
       }
       else {
-	out_map.set(edges.first(p), false);
+	out.set((*p).first, false);
       }
     }
     return tot_cost;
@@ -57,11 +74,11 @@
   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
   inline
   typename InputEdgeOrder::ValueType
-  Kruskal(Graph const& G, InputEdgeOrder const& edges, 
+  kruskal(Graph const& G, InputEdgeOrder const& edges, 
 	  OutBoolMap const& out_map)
   {
     NonConstMapWr<OutBoolMap> map_wr(out_map);
-    return Kruskal(G, edges, map_wr);
+    return kruskal(G, edges, map_wr);
   }  
 
   
@@ -69,7 +86,7 @@
   
   /// A writable bool-map that makes a sequence of "true" keys
 
-  /// A writable bool-map that creates a sequence out of keys that receive
+  /// A writable bool-map that creates a sequence out of keys that receives
   /// the value "true".
   /// \warning Not a regular property map, as it doesn't know its KeyType
 
@@ -95,22 +112,30 @@
 
   /* ** ** InputSource -ok ** ** */
 
-  template<typename Key, typename Val>
-  class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
+  /// Kruskal input source.
 
+  /// Kruskal input source.
+  ///
+  template<typename Graph, typename Map>
+  class KruskalPairVec
+    : public std::vector< std::pair<typename Graph::Edge,
+				    typename Map::ValueType> > {
+    
   public:
-    typedef std::vector< std::pair<Key,Val> > Parent;
-    typedef Key KeyType;
-    typedef Val ValueType;
-    typedef std::pair<Key,Val> PairType;
-
-    typedef typename Parent::iterator iterator;
-    typedef typename Parent::const_iterator const_iterator;
+    typedef std::vector< std::pair<typename Graph::Edge,
+				   typename Map::ValueType> > Parent;
+    typedef typename Parent::value_type value_type;
+//     typedef Key KeyType;
+//     typedef Val ValueType;
+//     typedef std::pair<Key,Val> PairType;
+//     typedef typename Parent::iterator iterator;
+//     typedef typename Parent::const_iterator const_iterator;
 
   private:
     class comparePair {
     public:
-      bool operator()(PairType const& a, PairType const& b) {
+      bool operator()(const value_type& a,
+		      const value_type& b) {
 	return a.second < b.second;
       }
     };
@@ -121,118 +146,125 @@
     // KruskalPairVec(Parent const& p) : Parent(p) {}
     
     void sort() {
-      std::sort(begin(), end(), comparePair());
+      std::sort(this->begin(), this->end(), comparePair());
     }
 
     // FIXME: nem nagyon illik ez ide...
-    template<typename Graph, typename Map>
     KruskalPairVec(Graph const& G, Map const& m) {
       typedef typename Graph::EdgeIt EdgeIt;
-
-      clear();
-      FOR_EACH_LOC(EdgeIt, e, G) {
-      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
+      
+      this->clear();
+      for(EdgeIt e(G);G.valid(e);G.next(e)) {
+	// for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
 	push_back(make_pair(e, m[e]));
       }
       sort();
     }
 
-    Key const& first(const_iterator i) const { return i->first; }
-    Key& first(iterator i) { return i->first; }
+//     Key const& first(const_iterator i) const { return i->first; }
+//     Key& first(iterator i) { return i->first; }
 
-    Val const& second(const_iterator i) const { return i->second; }
-    Val& second(iterator i) { return i->second; }
+//     Val const& second(const_iterator i) const { return i->second; }
+//     Val& second(iterator i) { return i->second; }
   };
 
 
-  template <typename Map>
-  class KruskalMapVec : public std::vector<typename Map::KeyType> {
-  public:
+//   template <typename Map>
+//   class KruskalMapVec : public std::vector<typename Map::KeyType> {
+//   public:
+    
+//     typedef typename Map::KeyType KeyType;
+//     typedef typename Map::ValueType ValueType;
 
-    typedef typename Map::KeyType KeyType;
-    typedef typename Map::ValueType ValueType;
+//     typedef typename std::vector<KeyType> Parent;
+//     typedef typename Parent::iterator iterator;
+//     typedef typename Parent::const_iterator const_iterator;
 
-    typedef typename std::vector<KeyType> Parent;
-    typedef typename Parent::iterator iterator;
-    typedef typename Parent::const_iterator const_iterator;
+//   private:
 
-  private:
+//     const Map &m;
 
-    const Map &m;
+//     class compareKeys {
+//       const Map &m;
+//     public:
+//       compareKeys(Map const &_m) : m(_m) {}
+//       bool operator()(KeyType const& a, KeyType const& b) {
+// 	return m[a] < m[b];
+//       }
+//     };
 
-    class compareKeys {
-      const Map &m;
-    public:
-      compareKeys(Map const &_m) : m(_m) {}
-      bool operator()(KeyType const& a, KeyType const& b) {
-	return m[a] < m[b];
-      }
-    };
+//   public:
 
-  public:
+//     KruskalMapVec(Map const& _m) : m(_m) {}
 
-    KruskalMapVec(Map const& _m) : m(_m) {}
+//     void sort() {
+//       std::sort(begin(), end(), compareKeys(m));
+//     }
 
-    void sort() {
-      std::sort(begin(), end(), compareKeys(m));
-    }
+//     // FIXME: nem nagyon illik ez ide...
+//     template<typename Graph>
+//     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
+//       typedef typename Graph::EdgeIt EdgeIt;
 
-    // FIXME: nem nagyon illik ez ide...
-    template<typename Graph>
-    KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
-      typedef typename Graph::EdgeIt EdgeIt;
+//       clear();
+//       for(EdgeIt e(G);G.valid(e);G.next(e)) {
+//       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) 
+// 	push_back(e);
+//       }
+//       sort();
+//     }
 
-      clear();
-      FOR_EACH_LOC(EdgeIt, e, G) {
-      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
-	push_back(e);
-      }
-      sort();
-    }
+//     KeyType const& first(const_iterator i) const { return *i; }
+//     KeyType& first(iterator i) { return *i; }
 
-    KeyType const& first(const_iterator i) const { return *i; }
-    KeyType& first(iterator i) { return *i; }
-
-    ValueType const& second(const_iterator i) const { return m[*i]; }
-    ValueType& second(iterator i) { return m[*i]; }
-  };
+//     ValueType const& second(const_iterator i) const { return m[*i]; }
+//     ValueType& second(iterator i) { return m[*i]; }
+//   };
 
   /* ** ** Wrapper fuggvenyek ** ** */
 
 
   /// \brief Wrapper to Kruskal().
   /// Input is from an EdgeMap, output is a plain boolmap.
+
+  ///\todo some more words would be nice here.
+  ///
   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
   inline
   typename EdgeCostMap::ValueType
-  Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
-				   EdgeCostMap const& edge_costs,
-				   RetEdgeBoolMap &ret_bool_map) {
-
-    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
-      InputVec;
+  kruskalEdgeMap(Graph const& G,
+			EdgeCostMap const& edge_costs,
+			RetEdgeBoolMap &ret_bool_map) {
+    
+    typedef KruskalPairVec<Graph,EdgeCostMap> InputVec;
+    
     InputVec iv(G, edge_costs);
-
-    return Kruskal(G, iv, ret_bool_map);
+    return kruskal(G, iv, ret_bool_map);
   }
 
 
   /// \brief Wrapper to Kruskal().
   /// Input is from an EdgeMap, output is to a sequence.
+
+  ///\todo it does not follow the naming convention.
+  ///
   template <typename Graph, typename EdgeCostMap, typename RetIterator>
   inline
   typename EdgeCostMap::ValueType
-  Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
-				    EdgeCostMap const& edge_costs,
-				    RetIterator ret_iterator) {
+  kruskalEdgeMap_IteratorOut(const Graph& G,
+			     const EdgeCostMap& edge_costs,
+			     RetIterator ret_iterator)
+  {
+    typedef typename EdgeCostMap::ValueType ValueType;
+    
     typedef SequenceOutput<RetIterator> OutMap;
     OutMap out(ret_iterator);
 
-    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
-      InputVec;
+    typedef KruskalPairVec<Graph, EdgeCostMap> InputVec;
+
     InputVec iv(G, edge_costs);
 
-    return Kruskal(G, iv, out);
+    return kruskal(G, iv, out);
   }
 
 
diff -r ba76a7f56b23 -r 2d867176d10e src/work/johanna/kruskal_test.cc
--- a/src/work/johanna/kruskal_test.cc	Fri Jul 23 16:58:02 2004 +0000
+++ b/src/work/johanna/kruskal_test.cc	Fri Jul 23 17:13:23 2004 +0000
@@ -4,7 +4,7 @@
 #include <vector>
 
 #include <kruskal.h>
-#include <list_graph.h>
+#include <hugo/list_graph.h>
 
 
 using namespace std;
@@ -71,7 +71,7 @@
   
 
   cout << "Uniform 2-es koltseggel: " 
-       << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map)
+       << kruskalEdgeMap(G, edge_cost_map, tree_map)
        << endl;
 
 
@@ -89,14 +89,14 @@
   vector<Edge> tree_edge_vec;
 
   cout << "Nemkonst koltseggel (-31): "
-       << Kruskal_EdgeCostMapIn_IteratorOut(G, edge_cost_map,
-					    back_inserter(tree_edge_vec))
+       << kruskalEdgeMap_IteratorOut(G, edge_cost_map,
+				     back_inserter(tree_edge_vec))
        << endl;
 
   int i = 1;
   for(vector<Edge>::iterator e = tree_edge_vec.begin();
       e != tree_edge_vec.end(); ++e, ++i) {
-    cout << i << ". el: " << *e << endl;
+    cout << i << ". el: " << G.id(*e) << endl;
   }
 
   tree_edge_vec.clear();
@@ -107,19 +107,21 @@
 // 		  KruskalMapVec<ECostMap>(G, edge_cost_map),
 // 		  vec_filler)
 //        << endl;
-  cout << "Nemkonst koltseggel tarhatekonyabban: "
-       << Kruskal(G,
-		  KruskalMapVec<ECostMap>(G, edge_cost_map),
-		  makeSequenceOutput(back_inserter(tree_edge_vec))
-		  )
-       << endl;
 
-  i = 1;
-  for(vector<Edge>::iterator e = tree_edge_vec.begin();
-      e != tree_edge_vec.end(); ++e, ++i) {
-    cout << i << ". el: " << *e << endl;
-  }
+//   cout << "Nemkonst koltseggel tarhatekonyabban: "
+//        << kruskal(G,
+// 		  KruskalMapVec<ECostMap>(G, edge_cost_map),
+// 		  makeSequenceOutput(back_inserter(tree_edge_vec))
+// 		  )
+//        << endl;
 
+//   i = 1;
+//   for(vector<Edge>::iterator e = tree_edge_vec.begin();
+//       e != tree_edge_vec.end(); ++e, ++i) {
+//     cout << i << ". el: " << *e << endl;
+//   }
+
+// **********************************************************************
 
 //   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;