src/work/johanna/kruskal_test.cc
author marci
Thu, 11 Mar 2004 14:15:07 +0000
changeset 168 27fbd1559fb7
child 218 5964f1c64ca1
permissions -rw-r--r--
graph wrapper improvements, blocking flow on fly
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@150
     6
#include <list_graph.hh>
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@150
    28
int main() {
beckerjc@150
    29
beckerjc@150
    30
  typedef ListGraph::NodeIt NodeIt;
beckerjc@150
    31
  typedef ListGraph::EdgeIt EdgeIt;
beckerjc@150
    32
  typedef ListGraph::EachNodeIt EachNodeIt;
beckerjc@150
    33
  typedef ListGraph::EachEdgeIt EachEdgeIt;
beckerjc@150
    34
beckerjc@150
    35
  ListGraph G;
beckerjc@150
    36
beckerjc@150
    37
  NodeIt s=G.addNode();
beckerjc@150
    38
  NodeIt v1=G.addNode();
beckerjc@150
    39
  NodeIt v2=G.addNode();
beckerjc@150
    40
  NodeIt v3=G.addNode();
beckerjc@150
    41
  NodeIt v4=G.addNode();
beckerjc@150
    42
  NodeIt t=G.addNode();
beckerjc@150
    43
  
beckerjc@150
    44
  G.addEdge(s, v1);
beckerjc@150
    45
  G.addEdge(s, v2);
beckerjc@150
    46
  G.addEdge(v1, v2);
beckerjc@150
    47
  G.addEdge(v2, v1);
beckerjc@150
    48
  G.addEdge(v1, v3);
beckerjc@150
    49
  G.addEdge(v3, v2);
beckerjc@150
    50
  G.addEdge(v2, v4);
beckerjc@150
    51
  G.addEdge(v4, v3);
beckerjc@150
    52
  G.addEdge(v3, t);
beckerjc@150
    53
  G.addEdge(v4, t);
beckerjc@150
    54
beckerjc@150
    55
  ListGraph::EdgeMap<double> edge_cost_map(G, 2);
beckerjc@150
    56
  ListGraph::EdgeMap<bool> tree_map(G);
beckerjc@150
    57
  
beckerjc@150
    58
  double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);
beckerjc@150
    59
beckerjc@150
    60
  cout << k0lts << endl;
beckerjc@150
    61
beckerjc@150
    62
  return 0;
beckerjc@150
    63
}