#include <string>

 #include <iostream>

 #include <map>

 #include <vector>

 #include <kruskal.h>

 #include <list_graph.h>

 using namespace std;

 using namespace hugo;

 class string_int_map : public map<string,int> {

 public:

   int get(const string &s) {

     // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy

     // hogy is mukodik ez a map :)

     if( count(s) == 0 ) {

       operator[](s) = -1;

     }

     return operator[](s);

   }

   void set(const string &s, int i) {

       operator[](s) = i;

   }

 };

 // 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;

   ListGraph G;

   Node s=G.addNode();

   Node v1=G.addNode();

   Node v2=G.addNode();

   Node v3=G.addNode();

   Node v4=G.addNode();

   Node t=G.addNode();

   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);

   typedef ListGraph::EdgeMap<double> ECostMap;

   typedef ListGraph::EdgeMap<bool> EBoolMap;

   ECostMap edge_cost_map(G, 2);

   EBoolMap tree_map(G);

   cout << "Uniform 2-es koltseggel: " 

        << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map)

        << endl;

   edge_cost_map.set(e1, -10);

   edge_cost_map.set(e2, -9);

   edge_cost_map.set(e3, -8);

   edge_cost_map.set(e4, -7);

   edge_cost_map.set(e5, -6);

   edge_cost_map.set(e6, -5);

   edge_cost_map.set(e7, -4);

   edge_cost_map.set(e8, -3);

   edge_cost_map.set(e9, -2);

   edge_cost_map.set(e10, -1);

   vector<Edge> tree_edge_vec;

   cout << "Nemkonst koltseggel (-31): "

        << Kruskal_EdgeCostMapIn_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;

   }

   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;

   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;

 //   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;

 }