COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/kruskal_test.cc @ 218:5964f1c64ca1

Last change on this file since 218:5964f1c64ca1 was 218:5964f1c64ca1, checked in by beckerjc, 16 years ago

unionfind: componentSize tagfv

kruskal: osztalyositva; lehet beadni sajat elorendezett el-koltseg vektort

nem tul elegans megoldas...

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