# HG changeset patch
# User beckerjc
# Date 1082229597 0
# Node ID 42c660f587025a7ae23b2deb024e23e5ad97504b
# Parent  b63ea19e502eb9795373c1b05aef2af73a79125a
Kruskal lenyegeben kesz.
Kell meg dokumentalni, meg meg egy par jol hasznalhato wrapper fv.
Es valamit meg kene csinalni azzal, hogy nem const ref. a kimeno boolmap,
  viszont sokszor "on-the-fly" akarjuk megkonstrualni (es ilyenkor persze a
  const-os mapet is lehet set-elni...)

diff -r b63ea19e502e -r 42c660f58702 src/work/johanna/kruskal.h
--- a/src/work/johanna/kruskal.h	Sat Apr 17 13:15:53 2004 +0000
+++ b/src/work/johanna/kruskal.h	Sat Apr 17 19:19:57 2004 +0000
@@ -2,165 +2,75 @@
 #ifndef HUGO_KRUSKAL_H
 #define HUGO_KRUSKAL_H
 
-#include "unionfind.h"
 #include <algorithm>
+#include <unionfind.h>
+#include <for_each_macros.h>
 
 namespace hugo {
 
-  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
-  typename EdgeCostMap::ValueType
-  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
-	   RetEdgeBoolMap &ret_bool_map);
+  /// Kruskal's algorithm to compute a minimum cost tree
 
-  template <typename Graph, typename EdgeCostMap, typename RetIterator>
-  typename EdgeCostMap::ValueType
-  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
-	   RetIterator ret_iterator);
+  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
+  typename InputEdgeOrder::ValueType
+  Kruskal(Graph const& G, InputEdgeOrder const& edges, 
+	  OutBoolMap& out_map)
+  {
+    typedef typename InputEdgeOrder::ValueType EdgeCost;
+    typedef typename Graph::NodeMap<int> NodeIntMap;
+    typedef typename Graph::Node Node;
 
-  // FIXME: ret_iterator nem lehet referencia!!!
+    NodeIntMap comp_map(G, -1);
+    UnionFind<Node,NodeIntMap> uf(comp_map); 
+      
+    EdgeCost tot_cost = 0;
+    for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
+	 p!=edges.end(); ++p ) {
+      if ( uf.joinComponents(G.head(edges.first(p)),
+			     G.tail(edges.first(p))) ) {
+	out_map.set(edges.first(p), true);
+	tot_cost += edges.second(p);
+      }
+      else {
+	out_map.set(edges.first(p), false);
+      }
+    }
+    return tot_cost;
+  }
 
-  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
-  typename EdgeCostPairVec::value_type::second_type
-  kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
-	   RetEdgeBoolMap &ret_bool_map);
 
-  template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
-  typename EdgeCostPairVec::value_type::second_type
-  kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
-	   RetIterator &ret_iterator);
+  
+  /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
+  
+  /// A writable bool-map that makes a sequence of "true" keys
 
-  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
-  int
-  kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
-	   RetEdgeBoolMap &ret_bool_map);
+  /// A writable bool-map that creates a sequence out of keys that receive
+  /// the value "true".
+  /// \warning Not a regular property map, as it doesn't know its KeyType
 
-  template <typename Graph, typename EdgePairVec, typename RetIterator>
-  int
-  kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
-	   RetIterator &ret_iterator);
-
-
-  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
-	    typename RetIterator>
-  typename EdgeCostMap::ValueType
-  kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
-	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
-
-  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
-	    typename RetIterator>
-  typename EdgeCostPairVec::value_type::second_type
-  kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
-	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
-
-  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
-	    typename RetIterator>
-  int
-  kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
-	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
-
-
-
-
-  template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
-  class MinCostTreeKruskal
-  {
-
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::Edge Edge;
+  template<typename Iterator>
+  class SequenceOutput {
+    Iterator it;
 
   public:
-    typedef typename InputEdgeOrder::ValueType EdgeCost;
-    
-  private:
-    Graph const &G;
-    InputEdgeOrder const &edges;
-    OutputObserver &out_obs;
+    typedef bool ValueType;
 
-  public:
+    SequenceOutput(Iterator const &_it) : it(_it) {}
 
-
-    MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, 
-		       OutputObserver& _out_obs) : 
-      G(_G), edges(_edges), out_obs(_out_obs) {}
-  
-
-    EdgeCost run()
-    {
-      typedef typename Graph::NodeMap<int> NodeIntMap;
-      typedef typename Graph::Node Node;
-      NodeIntMap comp_map(G, -1);
-      UnionFind<Node,NodeIntMap> uf(comp_map); 
-      
-      EdgeCost tot_cost = 0;
-      for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
-	   p!=edges.end(); ++p ) {
-	if ( uf.joinComponents(G.head(edges.first(p)),
-			       G.tail(edges.first(p))) ) {
-	  out_obs.setTrue(edges.first(p));
-	  tot_cost += edges.second(p);
-	}
-	else {
-	  out_obs.setFalse(edges.first(p));
-	}
-      }
-      return tot_cost;
-    }
-
+    template<typename KeyType>
+    void set(KeyType const& k, bool v) { if(v) {*it=k; ++it;} }
   };
 
-  
-  /* ** ** Output-objektumok (Observerek (?)) ** ** */
-  
-  template <typename BoolMap>
-  class BoolMapOutput {
-    BoolMap &bm;
-    typedef typename BoolMap::KeyType KeyType;
-
-  public:
-    BoolMapOutput(BoolMap &_bm) : bm(_bm) {}
-
-    void setTrue(KeyType const& k) { bm.set(k, true); }
-    void setFalse(KeyType const& k) { bm.set(k, false); }
-  };
-
-  template <typename Iterator>
-  class SequenceOutput {
-    Iterator &it;
-
-  public:
-    SequenceOutput(Iterator &_it) : it(_it) {}
-
-    template<typename KeyType>
-    void setTrue(KeyType const& k) { *it=k; ++it; }
-    template<typename KeyType>
-    void setFalse(KeyType const& k) {}
-  };
-
-  template <typename BoolMap, typename Iterator>
-  class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
-    typedef BoolMapOutput<BoolMap> BMO;
-    typedef SequenceOutput<Iterator> SO;
-  public:
-    CombinedOutput(BoolMap &_bm, Iterator &_it) :
-      BMO(_bm), SO(_it) {}
-
-    template<typename KeyType>
-    void setTrue(KeyType const& k) {
-      BMO::setTrue(k); 
-      SO::setTrue(k);
-    }
-    template<typename KeyType>
-    void setFalse(KeyType const& k) {
-      BMO::setFalse(k); 
-      SO::setFalse(k);      
-    }
-  };
-
+  template<typename Iterator>
+  inline
+  SequenceOutput<Iterator>
+  makeSequenceOutput(Iterator it) {
+    return SequenceOutput<Iterator>(it);
+  }
 
   /* ** ** InputSource -ok ** ** */
 
   template<typename Key, typename Val>
-  class PairVec : public std::vector< std::pair<Key,Val> > {
+  class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
 
   public:
     typedef std::vector< std::pair<Key,Val> > Parent;
@@ -171,9 +81,7 @@
     typedef typename Parent::iterator iterator;
     typedef typename Parent::const_iterator const_iterator;
 
-
   private:
-
     class comparePair {
     public:
       bool operator()(PairType const& a, PairType const& b) {
@@ -184,7 +92,7 @@
   public:
 
     // FIXME: kell ez?
-    // PairVec(Parent const& p) : Parent(p) {}
+    // KruskalPairVec(Parent const& p) : Parent(p) {}
     
     void sort() {
       std::sort(begin(), end(), comparePair());
@@ -192,19 +100,17 @@
 
     // FIXME: nem nagyon illik ez ide...
     template<typename Graph, typename Map>
-    void readGraphEdgeMap(Graph const& G, Map const& m) {
+    KruskalPairVec(Graph const& G, Map const& m) {
       typedef typename Graph::EdgeIt EdgeIt;
 
       clear();
-      for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
+      FOR_EACH_LOC(EdgeIt, e, G) {
+      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
 	push_back(make_pair(e, m[e]));
       }
-
       sort();
     }
 
-    int alma() { return 5; /* FIXME */ }
-
     Key const& first(const_iterator i) const { return i->first; }
     Key& first(iterator i) { return i->first; }
 
@@ -212,38 +118,93 @@
     Val& second(iterator i) { return i->second; }
   };
 
+
+  template <typename Map>
+  class KruskalMapVec : public std::vector<typename Map::KeyType> {
+  public:
+
+    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;
+
+  private:
+
+    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];
+      }
+    };
+
+  public:
+
+    KruskalMapVec(Map const& _m) : m(_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;
+
+      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; }
+
+    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.
   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
   typename EdgeCostMap::ValueType
-  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
-	   RetEdgeBoolMap &ret_bool_map) {
-    typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
-    OutObs out(ret_bool_map);
+  Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
+				   EdgeCostMap const& edge_costs,
+				   RetEdgeBoolMap &ret_bool_map) {
 
-    typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
+    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
       InputVec;
-    InputVec iv;
-    iv.readGraphEdgeMap(G, edge_costs);
+    InputVec iv(G, edge_costs);
 
-    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
-    return mctk.run();
+    return Kruskal(G, iv, ret_bool_map);
   }
 
+
+  /// \brief Wrapper to Kruskal().
+  /// Input is from an EdgeMap, output is to a sequence.
   template <typename Graph, typename EdgeCostMap, typename RetIterator>
   typename EdgeCostMap::ValueType
-  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
-	   RetIterator ret_iterator) {
-    typedef SequenceOutput<RetIterator> OutObs;
-    OutObs out(ret_iterator);
+  Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
+				    EdgeCostMap const& edge_costs,
+				    RetIterator ret_iterator) {
+    typedef SequenceOutput<RetIterator> OutMap;
+    OutMap out(ret_iterator);
 
-    typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
+    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
       InputVec;
-    InputVec iv;
-    iv.readGraphEdgeMap(G, edge_costs);
+    InputVec iv(G, edge_costs);
 
-    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
-    return mctk.run();    
+    return Kruskal(G, iv, out);
   }
 
 
diff -r b63ea19e502e -r 42c660f58702 src/work/johanna/kruskal_test.cc
--- a/src/work/johanna/kruskal_test.cc	Sat Apr 17 13:15:53 2004 +0000
+++ b/src/work/johanna/kruskal_test.cc	Sat Apr 17 19:19:57 2004 +0000
@@ -71,7 +71,7 @@
   
 
   cout << "Uniform 2-es koltseggel: " 
-       << kruskal1(G, edge_cost_map, tree_map)
+       << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map)
        << endl;
 
 
@@ -89,7 +89,8 @@
   vector<Edge> tree_edge_vec;
 
   cout << "Nemkonst koltseggel (-31): "
-       << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec))
+       << Kruskal_EdgeCostMapIn_IteratorOut(G, edge_cost_map,
+					    back_inserter(tree_edge_vec))
        << endl;
 
   int i = 1;
@@ -98,6 +99,21 @@
     cout << i << ". el: " << *e << endl;
   }
 
+  tree_edge_vec.clear();
+  SequenceOutput< back_insert_iterator< vector<Edge> > > 
+    vec_filler(back_inserter(tree_edge_vec));
+  cout << "Nemkonst koltseggel tarhatekonyabban: "
+       << Kruskal(G,
+		  KruskalMapVec<ECostMap>(G, edge_cost_map),
+		  vec_filler)
+       << 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;
 
diff -r b63ea19e502e -r 42c660f58702 src/work/johanna/unionfind.h
--- a/src/work/johanna/unionfind.h	Sat Apr 17 13:15:53 2004 +0000
+++ b/src/work/johanna/unionfind.h	Sat Apr 17 19:19:57 2004 +0000
@@ -24,7 +24,7 @@
 
     int whichComponent(T a)
     {
-      int comp0 = map.get(a);
+      int comp0 = map[a];
       if (comp0 < 0) {
 	return insertNewElement(a);
       }