COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/kruskal_test.cc @ 351:01fb9da7a363

Last change on this file since 351:01fb9da7a363 was 349:42c660f58702, checked in by beckerjc, 17 years ago

Kruskal lenyegeben kesz.
Kell meg dokumentalni, meg meg egy par jol hasznalhato wrapper fv.
Es valamit meg kene csinalni azzal, hogy nem const ref. a kimeno boolmap,

viszont sokszor "on-the-fly" akarjuk megkonstrualni (es ilyenkor persze a
const-os mapet is lehet set-elni...)

File size: 3.6 KB
Line 
1#include <string>
2#include <iostream>
3#include <map>
4#include <vector>
5
6#include <kruskal.h>
7#include <list_graph.h>
8
9
10using namespace std;
11using namespace hugo;
12
13class string_int_map : public map<string,int> {
14public:
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
32template <typename K, typename V>
33class DummyMap {
34public:
35  typedef K KeyType;
36  typedef V ValueType;
37};
38
39int 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
111  i = 1;
112  for(vector<Edge>::iterator e = tree_edge_vec.begin();
113      e != tree_edge_vec.end(); ++e, ++i) {
114    cout << i << ". el: " << *e << endl;
115  }
116
117
118//   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
119
120//   MCTK mctk(G, edge_cost_map, tree_map);
121//   double k0lts = mctk.run();
122
123//   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
124
125//   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
126//   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
127//   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
128//   MCTK2::EdgeCostVector ecv;
129//   ecv.push_back(make_pair(e1, 10));
130//   ecv.push_back(make_pair(e2, 9));
131//   ecv.push_back(make_pair(e3, 8));
132//   ecv.push_back(make_pair(e4, 7));
133//   ecv.push_back(make_pair(e5, 6));
134//   ecv.push_back(make_pair(e6, 5));
135//   ecv.push_back(make_pair(e7, 4));
136//   ecv.push_back(make_pair(e8, 3));
137//   ecv.push_back(make_pair(e9, 2));
138//   ecv.push_back(make_pair(e10, 1));
139
140//   k0lts = mctk2.run(ecv);
141//   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
142//        << k0lts << endl;
143
144
145  return 0;
146}
Note: See TracBrowser for help on using the repository browser.