source: lemon-0.x/src/work/johanna/kruskal_test.cc @ 538:d8863141824d

#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;
}