COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/kruskal_test.cc @ 768:a5e9303a5511

Last change on this file since 768:a5e9303a5511 was 737:2d867176d10e, checked in by Alpar Juttner, 20 years ago

Several changes in Kruskal alg.

  • Input object interface was changed to an STL compatible one.
  • template parameters of class KruskalPairVec? has been simplified.
  • (the most of) the names meet the naming conventions.
  • a lot of (but still not enough) documentation has been added.
  • class KruskalMapVec? has been commented out.
File size: 3.9 KB
RevLine 
[150]1#include <string>
2#include <iostream>
3#include <map>
[246]4#include <vector>
[150]5
6#include <kruskal.h>
[737]7#include <hugo/list_graph.h>
[150]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
[218]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
[150]39int main() {
40
[218]41  typedef ListGraph::Node Node;
42  typedef ListGraph::Edge Edge;
[150]43  typedef ListGraph::NodeIt NodeIt;
44  typedef ListGraph::EdgeIt EdgeIt;
45
46  ListGraph G;
47
[218]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();
[150]54 
[218]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);
[150]65
[218]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);
[150]71 
72
[246]73  cout << "Uniform 2-es koltseggel: "
[737]74       << kruskalEdgeMap(G, edge_cost_map, tree_map)
[246]75       << endl;
[218]76
77
[246]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);
[218]88
[246]89  vector<Edge> tree_edge_vec;
90
91  cout << "Nemkonst koltseggel (-31): "
[737]92       << kruskalEdgeMap_IteratorOut(G, edge_cost_map,
93                                     back_inserter(tree_edge_vec))
[246]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) {
[737]99    cout << i << ". el: " << G.id(*e) << endl;
[246]100  }
101
[349]102  tree_edge_vec.clear();
[352]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;
[349]110
[737]111//   cout << "Nemkonst koltseggel tarhatekonyabban: "
112//        << kruskal(G,
113//                KruskalMapVec<ECostMap>(G, edge_cost_map),
114//                makeSequenceOutput(back_inserter(tree_edge_vec))
115//                )
116//        << endl;
[349]117
[737]118//   i = 1;
119//   for(vector<Edge>::iterator e = tree_edge_vec.begin();
120//       e != tree_edge_vec.end(); ++e, ++i) {
121//     cout << i << ". el: " << *e << endl;
122//   }
123
124// **********************************************************************
[246]125
126//   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
127
128//   MCTK mctk(G, edge_cost_map, tree_map);
129//   double k0lts = mctk.run();
130
131//   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
132
133//   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
134//   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
135//   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
136//   MCTK2::EdgeCostVector ecv;
137//   ecv.push_back(make_pair(e1, 10));
138//   ecv.push_back(make_pair(e2, 9));
139//   ecv.push_back(make_pair(e3, 8));
140//   ecv.push_back(make_pair(e4, 7));
141//   ecv.push_back(make_pair(e5, 6));
142//   ecv.push_back(make_pair(e6, 5));
143//   ecv.push_back(make_pair(e7, 4));
144//   ecv.push_back(make_pair(e8, 3));
145//   ecv.push_back(make_pair(e9, 2));
146//   ecv.push_back(make_pair(e10, 1));
147
148//   k0lts = mctk2.run(ecv);
149//   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
150//        << k0lts << endl;
[218]151
[150]152
153  return 0;
154}
Note: See TracBrowser for help on using the repository browser.