src/work/johanna/kruskal_test.cc
changeset 348 b63ea19e502e
parent 218 5964f1c64ca1
child 349 42c660f58702
equal deleted inserted replaced
1:5d9c1c3bacce 2:3c8630d0c5cd
     1 #include <string>
     1 #include <string>
     2 #include <iostream>
     2 #include <iostream>
     3 #include <map>
     3 #include <map>
       
     4 #include <vector>
     4 
     5 
     5 #include <kruskal.h>
     6 #include <kruskal.h>
     6 #include <list_graph.h>
     7 #include <list_graph.h>
     7 
     8 
     8 
     9 
    66   typedef ListGraph::EdgeMap<bool> EBoolMap;
    67   typedef ListGraph::EdgeMap<bool> EBoolMap;
    67 
    68 
    68   ECostMap edge_cost_map(G, 2);
    69   ECostMap edge_cost_map(G, 2);
    69   EBoolMap tree_map(G);
    70   EBoolMap tree_map(G);
    70   
    71   
    71   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
       
    72 
    72 
    73   MCTK mctk(G, edge_cost_map, tree_map);
    73   cout << "Uniform 2-es koltseggel: " 
    74   double k0lts = mctk.run();
    74        << kruskal1(G, edge_cost_map, tree_map)
       
    75        << endl;
    75 
    76 
    76   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
       
    77 
    77 
    78   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
    78   edge_cost_map.set(e1, -10);
    79   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
    79   edge_cost_map.set(e2, -9);
    80   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
    80   edge_cost_map.set(e3, -8);
    81   MCTK2::EdgeCostVector ecv;
    81   edge_cost_map.set(e4, -7);
    82   ecv.push_back(make_pair(e1, 10));
    82   edge_cost_map.set(e5, -6);
    83   ecv.push_back(make_pair(e2, 9));
    83   edge_cost_map.set(e6, -5);
    84   ecv.push_back(make_pair(e3, 8));
    84   edge_cost_map.set(e7, -4);
    85   ecv.push_back(make_pair(e4, 7));
    85   edge_cost_map.set(e8, -3);
    86   ecv.push_back(make_pair(e5, 6));
    86   edge_cost_map.set(e9, -2);
    87   ecv.push_back(make_pair(e6, 5));
    87   edge_cost_map.set(e10, -1);
    88   ecv.push_back(make_pair(e7, 4));
       
    89   ecv.push_back(make_pair(e8, 3));
       
    90   ecv.push_back(make_pair(e9, 2));
       
    91   ecv.push_back(make_pair(e10, 1));
       
    92 
    88 
    93   k0lts = mctk2.run(ecv);
    89   vector<Edge> tree_edge_vec;
    94   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
    90 
    95        << k0lts << endl;
    91   cout << "Nemkonst koltseggel (-31): "
       
    92        << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec))
       
    93        << endl;
       
    94 
       
    95   int i = 1;
       
    96   for(vector<Edge>::iterator e = tree_edge_vec.begin();
       
    97       e != tree_edge_vec.end(); ++e, ++i) {
       
    98     cout << i << ". el: " << *e << endl;
       
    99   }
       
   100 
       
   101 
       
   102 //   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
       
   103 
       
   104 //   MCTK mctk(G, edge_cost_map, tree_map);
       
   105 //   double k0lts = mctk.run();
       
   106 
       
   107 //   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
       
   108 
       
   109 //   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
       
   110 //   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
       
   111 //   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
       
   112 //   MCTK2::EdgeCostVector ecv;
       
   113 //   ecv.push_back(make_pair(e1, 10));
       
   114 //   ecv.push_back(make_pair(e2, 9));
       
   115 //   ecv.push_back(make_pair(e3, 8));
       
   116 //   ecv.push_back(make_pair(e4, 7));
       
   117 //   ecv.push_back(make_pair(e5, 6));
       
   118 //   ecv.push_back(make_pair(e6, 5));
       
   119 //   ecv.push_back(make_pair(e7, 4));
       
   120 //   ecv.push_back(make_pair(e8, 3));
       
   121 //   ecv.push_back(make_pair(e9, 2));
       
   122 //   ecv.push_back(make_pair(e10, 1));
       
   123 
       
   124 //   k0lts = mctk2.run(ecv);
       
   125 //   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
       
   126 //        << k0lts << endl;
    96 
   127 
    97 
   128 
    98   return 0;
   129   return 0;
    99 }
   130 }