src/work/johanna/kruskal_test.cc
author alpar
Thu, 22 Jul 2004 14:29:20 +0000
changeset 730 af375858f17c
parent 349 42c660f58702
child 737 2d867176d10e
permissions -rw-r--r--
Custom made INSTALL file (will be sometime).
     1 #include <string>
     2 #include <iostream>
     3 #include <map>
     4 #include <vector>
     5 
     6 #include <kruskal.h>
     7 #include <list_graph.h>
     8 
     9 
    10 using namespace std;
    11 using namespace hugo;
    12 
    13 class string_int_map : public map<string,int> {
    14 public:
    15   int get(const string &s) {
    16     // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
    17     // hogy is mukodik ez a map :)
    18     if( count(s) == 0 ) {
    19       operator[](s) = -1;
    20     }
    21     return operator[](s);
    22   }
    23   void set(const string &s, int i) {
    24       operator[](s) = i;
    25   }
    26 };
    27 
    28 
    29 // Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
    30 // Valami elegansabb megoldas kene a Kruskalban...
    31 
    32 template <typename K, typename V>
    33 class DummyMap {
    34 public:
    35   typedef K KeyType;
    36   typedef V ValueType;
    37 };
    38 
    39 int main() {
    40 
    41   typedef ListGraph::Node Node;
    42   typedef ListGraph::Edge Edge;
    43   typedef ListGraph::NodeIt NodeIt;
    44   typedef ListGraph::EdgeIt EdgeIt;
    45 
    46   ListGraph G;
    47 
    48   Node s=G.addNode();
    49   Node v1=G.addNode();
    50   Node v2=G.addNode();
    51   Node v3=G.addNode();
    52   Node v4=G.addNode();
    53   Node t=G.addNode();
    54   
    55   Edge e1 = G.addEdge(s, v1);
    56   Edge e2 = G.addEdge(s, v2);
    57   Edge e3 = G.addEdge(v1, v2);
    58   Edge e4 = G.addEdge(v2, v1);
    59   Edge e5 = G.addEdge(v1, v3);
    60   Edge e6 = G.addEdge(v3, v2);
    61   Edge e7 = G.addEdge(v2, v4);
    62   Edge e8 = G.addEdge(v4, v3);
    63   Edge e9 = G.addEdge(v3, t);
    64   Edge e10 = G.addEdge(v4, t);
    65 
    66   typedef ListGraph::EdgeMap<double> ECostMap;
    67   typedef ListGraph::EdgeMap<bool> EBoolMap;
    68 
    69   ECostMap edge_cost_map(G, 2);
    70   EBoolMap tree_map(G);
    71   
    72 
    73   cout << "Uniform 2-es koltseggel: " 
    74        << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map)
    75        << endl;
    76 
    77 
    78   edge_cost_map.set(e1, -10);
    79   edge_cost_map.set(e2, -9);
    80   edge_cost_map.set(e3, -8);
    81   edge_cost_map.set(e4, -7);
    82   edge_cost_map.set(e5, -6);
    83   edge_cost_map.set(e6, -5);
    84   edge_cost_map.set(e7, -4);
    85   edge_cost_map.set(e8, -3);
    86   edge_cost_map.set(e9, -2);
    87   edge_cost_map.set(e10, -1);
    88 
    89   vector<Edge> tree_edge_vec;
    90 
    91   cout << "Nemkonst koltseggel (-31): "
    92        << Kruskal_EdgeCostMapIn_IteratorOut(G, edge_cost_map,
    93 					    back_inserter(tree_edge_vec))
    94        << endl;
    95 
    96   int i = 1;
    97   for(vector<Edge>::iterator e = tree_edge_vec.begin();
    98       e != tree_edge_vec.end(); ++e, ++i) {
    99     cout << i << ". el: " << *e << endl;
   100   }
   101 
   102   tree_edge_vec.clear();
   103 //   SequenceOutput< back_insert_iterator< vector<Edge> > > 
   104 //     vec_filler(back_inserter(tree_edge_vec));
   105 //   cout << "Nemkonst koltseggel tarhatekonyabban: "
   106 //        << Kruskal(G,
   107 // 		  KruskalMapVec<ECostMap>(G, edge_cost_map),
   108 // 		  vec_filler)
   109 //        << endl;
   110   cout << "Nemkonst koltseggel tarhatekonyabban: "
   111        << Kruskal(G,
   112 		  KruskalMapVec<ECostMap>(G, edge_cost_map),
   113 		  makeSequenceOutput(back_inserter(tree_edge_vec))
   114 		  )
   115        << endl;
   116 
   117   i = 1;
   118   for(vector<Edge>::iterator e = tree_edge_vec.begin();
   119       e != tree_edge_vec.end(); ++e, ++i) {
   120     cout << i << ". el: " << *e << endl;
   121   }
   122 
   123 
   124 //   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
   125 
   126 //   MCTK mctk(G, edge_cost_map, tree_map);
   127 //   double k0lts = mctk.run();
   128 
   129 //   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
   130 
   131 //   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
   132 //   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
   133 //   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
   134 //   MCTK2::EdgeCostVector ecv;
   135 //   ecv.push_back(make_pair(e1, 10));
   136 //   ecv.push_back(make_pair(e2, 9));
   137 //   ecv.push_back(make_pair(e3, 8));
   138 //   ecv.push_back(make_pair(e4, 7));
   139 //   ecv.push_back(make_pair(e5, 6));
   140 //   ecv.push_back(make_pair(e6, 5));
   141 //   ecv.push_back(make_pair(e7, 4));
   142 //   ecv.push_back(make_pair(e8, 3));
   143 //   ecv.push_back(make_pair(e9, 2));
   144 //   ecv.push_back(make_pair(e10, 1));
   145 
   146 //   k0lts = mctk2.run(ecv);
   147 //   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
   148 //        << k0lts << endl;
   149 
   150 
   151   return 0;
   152 }