src/work/johanna/kruskal_test.cc
author alpar
Sun, 21 Mar 2004 14:58:48 +0000
changeset 223 02948c4c68e1
parent 150 4b5210aa0239
child 246 dc95ca4ebc7b
permissions -rw-r--r--
Dijkstra, bin_heap, fib_heap added to the doc.
beckerjc@150
     1
#include <string>
beckerjc@150
     2
#include <iostream>
beckerjc@150
     3
#include <map>
beckerjc@150
     4
beckerjc@150
     5
#include <kruskal.h>
beckerjc@218
     6
#include <list_graph.h>
beckerjc@150
     7
beckerjc@150
     8
beckerjc@150
     9
using namespace std;
beckerjc@150
    10
using namespace hugo;
beckerjc@150
    11
beckerjc@150
    12
class string_int_map : public map<string,int> {
beckerjc@150
    13
public:
beckerjc@150
    14
  int get(const string &s) {
beckerjc@150
    15
    // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
beckerjc@150
    16
    // hogy is mukodik ez a map :)
beckerjc@150
    17
    if( count(s) == 0 ) {
beckerjc@150
    18
      operator[](s) = -1;
beckerjc@150
    19
    }
beckerjc@150
    20
    return operator[](s);
beckerjc@150
    21
  }
beckerjc@150
    22
  void set(const string &s, int i) {
beckerjc@150
    23
      operator[](s) = i;
beckerjc@150
    24
  }
beckerjc@150
    25
};
beckerjc@150
    26
beckerjc@150
    27
beckerjc@218
    28
// Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
beckerjc@218
    29
// Valami elegansabb megoldas kene a Kruskalban...
beckerjc@218
    30
beckerjc@218
    31
template <typename K, typename V>
beckerjc@218
    32
class DummyMap {
beckerjc@218
    33
public:
beckerjc@218
    34
  typedef K KeyType;
beckerjc@218
    35
  typedef V ValueType;
beckerjc@218
    36
};
beckerjc@218
    37
beckerjc@150
    38
int main() {
beckerjc@150
    39
beckerjc@218
    40
  typedef ListGraph::Node Node;
beckerjc@218
    41
  typedef ListGraph::Edge Edge;
beckerjc@150
    42
  typedef ListGraph::NodeIt NodeIt;
beckerjc@150
    43
  typedef ListGraph::EdgeIt EdgeIt;
beckerjc@150
    44
beckerjc@150
    45
  ListGraph G;
beckerjc@150
    46
beckerjc@218
    47
  Node s=G.addNode();
beckerjc@218
    48
  Node v1=G.addNode();
beckerjc@218
    49
  Node v2=G.addNode();
beckerjc@218
    50
  Node v3=G.addNode();
beckerjc@218
    51
  Node v4=G.addNode();
beckerjc@218
    52
  Node t=G.addNode();
beckerjc@150
    53
  
beckerjc@218
    54
  Edge e1 = G.addEdge(s, v1);
beckerjc@218
    55
  Edge e2 = G.addEdge(s, v2);
beckerjc@218
    56
  Edge e3 = G.addEdge(v1, v2);
beckerjc@218
    57
  Edge e4 = G.addEdge(v2, v1);
beckerjc@218
    58
  Edge e5 = G.addEdge(v1, v3);
beckerjc@218
    59
  Edge e6 = G.addEdge(v3, v2);
beckerjc@218
    60
  Edge e7 = G.addEdge(v2, v4);
beckerjc@218
    61
  Edge e8 = G.addEdge(v4, v3);
beckerjc@218
    62
  Edge e9 = G.addEdge(v3, t);
beckerjc@218
    63
  Edge e10 = G.addEdge(v4, t);
beckerjc@150
    64
beckerjc@218
    65
  typedef ListGraph::EdgeMap<double> ECostMap;
beckerjc@218
    66
  typedef ListGraph::EdgeMap<bool> EBoolMap;
beckerjc@218
    67
beckerjc@218
    68
  ECostMap edge_cost_map(G, 2);
beckerjc@218
    69
  EBoolMap tree_map(G);
beckerjc@150
    70
  
beckerjc@218
    71
  typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
beckerjc@150
    72
beckerjc@218
    73
  MCTK mctk(G, edge_cost_map, tree_map);
beckerjc@218
    74
  double k0lts = mctk.run();
beckerjc@218
    75
beckerjc@218
    76
  cout << "Uniform 2-es koltseggel: " << k0lts << endl;
beckerjc@218
    77
beckerjc@218
    78
  // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
beckerjc@218
    79
  typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
beckerjc@218
    80
  MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
beckerjc@218
    81
  MCTK2::EdgeCostVector ecv;
beckerjc@218
    82
  ecv.push_back(make_pair(e1, 10));
beckerjc@218
    83
  ecv.push_back(make_pair(e2, 9));
beckerjc@218
    84
  ecv.push_back(make_pair(e3, 8));
beckerjc@218
    85
  ecv.push_back(make_pair(e4, 7));
beckerjc@218
    86
  ecv.push_back(make_pair(e5, 6));
beckerjc@218
    87
  ecv.push_back(make_pair(e6, 5));
beckerjc@218
    88
  ecv.push_back(make_pair(e7, 4));
beckerjc@218
    89
  ecv.push_back(make_pair(e8, 3));
beckerjc@218
    90
  ecv.push_back(make_pair(e9, 2));
beckerjc@218
    91
  ecv.push_back(make_pair(e10, 1));
beckerjc@218
    92
beckerjc@218
    93
  k0lts = mctk2.run(ecv);
beckerjc@218
    94
  cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
beckerjc@218
    95
       << k0lts << endl;
beckerjc@218
    96
beckerjc@150
    97
beckerjc@150
    98
  return 0;
beckerjc@150
    99
}