# HG changeset patch
# User beckerjc
# Date 1079802105 0
# Node ID 5964f1c64ca19c44d3a28ad581b4353eb7671a97
# Parent  fc549fac0dd0386ae251dc60a836a25135019456
unionfind: componentSize tagfv

kruskal: osztalyositva; lehet beadni sajat elorendezett el-koltseg vektort
	 nem tul elegans megoldas...

diff -r fc549fac0dd0 -r 5964f1c64ca1 src/work/johanna/Makefile
--- a/src/work/johanna/Makefile	Sat Mar 20 16:13:19 2004 +0000
+++ b/src/work/johanna/Makefile	Sat Mar 20 17:01:45 2004 +0000
@@ -1,4 +1,4 @@
 BINARIES = kruskal_test
-INCLUDEDIRS= -I. -I.. -I../../include
+INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
 include ../makefile
 
diff -r fc549fac0dd0 -r 5964f1c64ca1 src/work/johanna/kruskal.h
--- a/src/work/johanna/kruskal.h	Sat Mar 20 16:13:19 2004 +0000
+++ b/src/work/johanna/kruskal.h	Sat Mar 20 17:01:45 2004 +0000
@@ -7,52 +7,76 @@
 
 namespace hugo {
 
-  template <typename EdgeCostPair> static
-  bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
-    return a.second < b.second;
-  }
 
+  template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
+  class MinCostTreeKruskal
+  {
 
-  template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::Edge Edge;
 
-  typename EdgeDoubleMap::ValueType 
-  MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap, 
-		     EdgeBoolMap& treemap) 
-  {
+  public:
+    typedef typename EdgeCostMap::ValueType EdgeCost;
+    typedef std::pair<Edge, EdgeCost> EdgeCostPair;
+    typedef std::vector<EdgeCostPair> EdgeCostVector;
     
-    typedef typename EdgeDoubleMap::ValueType EDouble;
-    typedef typename Graph::EachEdgeIt EachEdgeIt;
-    typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
+  private:
+    Graph const &G;
+    EdgeCostMap const &costmap;
+    EdgeBoolMap& treemap;
+    
+    //template <typename EdgeCostPair>
+    class comparePair {
+    public:
+      bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) {
+	return a.second < b.second;
+      }
+    };
 
+  public:
 
-    typedef std::vector<EdgeCostPair> EdgeCostVector;
-    EdgeCostVector rank;
 
-    for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
-      rank.push_back(make_pair(e, costmap.get(e)));
+    MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap, 
+		       EdgeBoolMap& _treemap) : G(_G), costmap(_costmap), 
+						treemap(_treemap) {}
+  
+
+    EdgeCost run() 
+    {
+     EdgeCostVector rank;
+     for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
+	rank.push_back(make_pair(e, costmap.get(e)));
+      }
+      
+      std::sort(rank.begin(), rank.end(), comparePair());
+
+      return run(rank);
+    
     }
 
-    
-    std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
+    EdgeCost run(EdgeCostVector const &rank)
+    {
+      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 EdgeCostVector::const_iterator p = rank.begin(); 
+	   p!=rank.end(); ++p ) {
+	if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
+	  treemap.set(p->first, true);
+	  tot_cost += p->second;
+	}
+	else {
+	  treemap.set(p->first, false);
+	}
+      }
+      return tot_cost;
 
-    typedef typename Graph::NodeMap<int> NodeIntMap;
-    typedef typename Graph::NodeIt NodeIt;
-    NodeIntMap comp_map(G, -1);
-    UnionFind<NodeIt,NodeIntMap> uf(comp_map); 
+    }
 
-    EDouble tot_cost = 0;
-    for (typename EdgeCostVector::iterator p = rank.begin(); 
-	 p!=rank.end(); ++p ) {
-      if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
-	treemap.set(p->first, true);
-	tot_cost += p->second;
-      }
-      else {
-	treemap.set(p->first, false);
-      }
-    }
-    return tot_cost;
-  }
+  };
 
 
 } //namespace hugo
diff -r fc549fac0dd0 -r 5964f1c64ca1 src/work/johanna/kruskal_test.cc
--- a/src/work/johanna/kruskal_test.cc	Sat Mar 20 16:13:19 2004 +0000
+++ b/src/work/johanna/kruskal_test.cc	Sat Mar 20 17:01:45 2004 +0000
@@ -3,7 +3,7 @@
 #include <map>
 
 #include <kruskal.h>
-#include <list_graph.hh>
+#include <list_graph.h>
 
 
 using namespace std;
@@ -25,39 +25,75 @@
 };
 
 
+// Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
+// Valami elegansabb megoldas kene a Kruskalban...
+
+template <typename K, typename V>
+class DummyMap {
+public:
+  typedef K KeyType;
+  typedef V ValueType;
+};
+
 int main() {
 
+  typedef ListGraph::Node Node;
+  typedef ListGraph::Edge Edge;
   typedef ListGraph::NodeIt NodeIt;
   typedef ListGraph::EdgeIt EdgeIt;
-  typedef ListGraph::EachNodeIt EachNodeIt;
-  typedef ListGraph::EachEdgeIt EachEdgeIt;
 
   ListGraph G;
 
-  NodeIt s=G.addNode();
-  NodeIt v1=G.addNode();
-  NodeIt v2=G.addNode();
-  NodeIt v3=G.addNode();
-  NodeIt v4=G.addNode();
-  NodeIt t=G.addNode();
+  Node s=G.addNode();
+  Node v1=G.addNode();
+  Node v2=G.addNode();
+  Node v3=G.addNode();
+  Node v4=G.addNode();
+  Node t=G.addNode();
   
-  G.addEdge(s, v1);
-  G.addEdge(s, v2);
-  G.addEdge(v1, v2);
-  G.addEdge(v2, v1);
-  G.addEdge(v1, v3);
-  G.addEdge(v3, v2);
-  G.addEdge(v2, v4);
-  G.addEdge(v4, v3);
-  G.addEdge(v3, t);
-  G.addEdge(v4, t);
+  Edge e1 = G.addEdge(s, v1);
+  Edge e2 = G.addEdge(s, v2);
+  Edge e3 = G.addEdge(v1, v2);
+  Edge e4 = G.addEdge(v2, v1);
+  Edge e5 = G.addEdge(v1, v3);
+  Edge e6 = G.addEdge(v3, v2);
+  Edge e7 = G.addEdge(v2, v4);
+  Edge e8 = G.addEdge(v4, v3);
+  Edge e9 = G.addEdge(v3, t);
+  Edge e10 = G.addEdge(v4, t);
 
-  ListGraph::EdgeMap<double> edge_cost_map(G, 2);
-  ListGraph::EdgeMap<bool> tree_map(G);
+  typedef ListGraph::EdgeMap<double> ECostMap;
+  typedef ListGraph::EdgeMap<bool> EBoolMap;
+
+  ECostMap edge_cost_map(G, 2);
+  EBoolMap tree_map(G);
   
-  double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);
+  typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
 
-  cout << k0lts << endl;
+  MCTK mctk(G, edge_cost_map, tree_map);
+  double k0lts = mctk.run();
+
+  cout << "Uniform 2-es koltseggel: " << k0lts << endl;
+
+  // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
+  typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
+  MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
+  MCTK2::EdgeCostVector ecv;
+  ecv.push_back(make_pair(e1, 10));
+  ecv.push_back(make_pair(e2, 9));
+  ecv.push_back(make_pair(e3, 8));
+  ecv.push_back(make_pair(e4, 7));
+  ecv.push_back(make_pair(e5, 6));
+  ecv.push_back(make_pair(e6, 5));
+  ecv.push_back(make_pair(e7, 4));
+  ecv.push_back(make_pair(e8, 3));
+  ecv.push_back(make_pair(e9, 2));
+  ecv.push_back(make_pair(e10, 1));
+
+  k0lts = mctk2.run(ecv);
+  cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
+       << k0lts << endl;
+
 
   return 0;
 }
diff -r fc549fac0dd0 -r 5964f1c64ca1 src/work/johanna/unionfind.h
--- a/src/work/johanna/unionfind.h	Sat Mar 20 16:13:19 2004 +0000
+++ b/src/work/johanna/unionfind.h	Sat Mar 20 17:01:45 2004 +0000
@@ -1,6 +1,6 @@
 // -*- c++ -*- //
-#ifndef UNION_FIND_H
-#define UNION_FIND_H
+#ifndef HUGO_UNION_FIND_H
+#define HUGO_UNION_FIND_H
 
 #include <vector>
 #include <utility>
@@ -68,8 +68,14 @@
       return true;
     }
 
+    int componentSize(T a)
+    {
+      int ca = whichComponent(a);
+      return data[ca].second;
+    }
+
   };
 
 } //namespace hugo
 
-#endif //UNION_FIND_H
+#endif //HUGO_UNION_FIND_H