src/work/johanna/kruskal_test.cc
author alpar
Sat, 17 Apr 2004 13:15:53 +0000
changeset 348 b63ea19e502e
parent 218 5964f1c64ca1
child 349 42c660f58702
permissions -rw-r--r--
A bool Edge Map with iterators that goes through the true or the false edges.
     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        << kruskal1(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        << 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;
   127 
   128 
   129   return 0;
   130 }