1.1 --- a/src/work/johanna/kruskal_test.cc Sun Sep 19 12:45:35 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,154 +0,0 @@
1.4 -#include <string>
1.5 -#include <iostream>
1.6 -#include <map>
1.7 -#include <vector>
1.8 -
1.9 -#include <kruskal.h>
1.10 -#include <hugo/list_graph.h>
1.11 -
1.12 -
1.13 -using namespace std;
1.14 -using namespace hugo;
1.15 -
1.16 -class string_int_map : public map<string,int> {
1.17 -public:
1.18 - int get(const string &s) {
1.19 - // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
1.20 - // hogy is mukodik ez a map :)
1.21 - if( count(s) == 0 ) {
1.22 - operator[](s) = -1;
1.23 - }
1.24 - return operator[](s);
1.25 - }
1.26 - void set(const string &s, int i) {
1.27 - operator[](s) = i;
1.28 - }
1.29 -};
1.30 -
1.31 -
1.32 -// Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
1.33 -// Valami elegansabb megoldas kene a Kruskalban...
1.34 -
1.35 -template <typename K, typename V>
1.36 -class DummyMap {
1.37 -public:
1.38 - typedef K KeyType;
1.39 - typedef V ValueType;
1.40 -};
1.41 -
1.42 -int main() {
1.43 -
1.44 - typedef ListGraph::Node Node;
1.45 - typedef ListGraph::Edge Edge;
1.46 - typedef ListGraph::NodeIt NodeIt;
1.47 - typedef ListGraph::EdgeIt EdgeIt;
1.48 -
1.49 - ListGraph G;
1.50 -
1.51 - Node s=G.addNode();
1.52 - Node v1=G.addNode();
1.53 - Node v2=G.addNode();
1.54 - Node v3=G.addNode();
1.55 - Node v4=G.addNode();
1.56 - Node t=G.addNode();
1.57 -
1.58 - Edge e1 = G.addEdge(s, v1);
1.59 - Edge e2 = G.addEdge(s, v2);
1.60 - Edge e3 = G.addEdge(v1, v2);
1.61 - Edge e4 = G.addEdge(v2, v1);
1.62 - Edge e5 = G.addEdge(v1, v3);
1.63 - Edge e6 = G.addEdge(v3, v2);
1.64 - Edge e7 = G.addEdge(v2, v4);
1.65 - Edge e8 = G.addEdge(v4, v3);
1.66 - Edge e9 = G.addEdge(v3, t);
1.67 - Edge e10 = G.addEdge(v4, t);
1.68 -
1.69 - typedef ListGraph::EdgeMap<double> ECostMap;
1.70 - typedef ListGraph::EdgeMap<bool> EBoolMap;
1.71 -
1.72 - ECostMap edge_cost_map(G, 2);
1.73 - EBoolMap tree_map(G);
1.74 -
1.75 -
1.76 - cout << "Uniform 2-es koltseggel: "
1.77 - << kruskalEdgeMap(G, edge_cost_map, tree_map)
1.78 - << endl;
1.79 -
1.80 -
1.81 - edge_cost_map.set(e1, -10);
1.82 - edge_cost_map.set(e2, -9);
1.83 - edge_cost_map.set(e3, -8);
1.84 - edge_cost_map.set(e4, -7);
1.85 - edge_cost_map.set(e5, -6);
1.86 - edge_cost_map.set(e6, -5);
1.87 - edge_cost_map.set(e7, -4);
1.88 - edge_cost_map.set(e8, -3);
1.89 - edge_cost_map.set(e9, -2);
1.90 - edge_cost_map.set(e10, -1);
1.91 -
1.92 - vector<Edge> tree_edge_vec;
1.93 -
1.94 - cout << "Nemkonst koltseggel (-31): "
1.95 - << kruskalEdgeMap_IteratorOut(G, edge_cost_map,
1.96 - back_inserter(tree_edge_vec))
1.97 - << endl;
1.98 -
1.99 - int i = 1;
1.100 - for(vector<Edge>::iterator e = tree_edge_vec.begin();
1.101 - e != tree_edge_vec.end(); ++e, ++i) {
1.102 - cout << i << ". el: " << G.id(*e) << endl;
1.103 - }
1.104 -
1.105 - tree_edge_vec.clear();
1.106 -// SequenceOutput< back_insert_iterator< vector<Edge> > >
1.107 -// vec_filler(back_inserter(tree_edge_vec));
1.108 -// cout << "Nemkonst koltseggel tarhatekonyabban: "
1.109 -// << Kruskal(G,
1.110 -// KruskalMapVec<ECostMap>(G, edge_cost_map),
1.111 -// vec_filler)
1.112 -// << endl;
1.113 -
1.114 -// cout << "Nemkonst koltseggel tarhatekonyabban: "
1.115 -// << kruskal(G,
1.116 -// KruskalMapVec<ECostMap>(G, edge_cost_map),
1.117 -// makeSequenceOutput(back_inserter(tree_edge_vec))
1.118 -// )
1.119 -// << endl;
1.120 -
1.121 -// i = 1;
1.122 -// for(vector<Edge>::iterator e = tree_edge_vec.begin();
1.123 -// e != tree_edge_vec.end(); ++e, ++i) {
1.124 -// cout << i << ". el: " << *e << endl;
1.125 -// }
1.126 -
1.127 -// **********************************************************************
1.128 -
1.129 -// typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
1.130 -
1.131 -// MCTK mctk(G, edge_cost_map, tree_map);
1.132 -// double k0lts = mctk.run();
1.133 -
1.134 -// cout << "Uniform 2-es koltseggel: " << k0lts << endl;
1.135 -
1.136 -// // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
1.137 -// typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
1.138 -// MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
1.139 -// MCTK2::EdgeCostVector ecv;
1.140 -// ecv.push_back(make_pair(e1, 10));
1.141 -// ecv.push_back(make_pair(e2, 9));
1.142 -// ecv.push_back(make_pair(e3, 8));
1.143 -// ecv.push_back(make_pair(e4, 7));
1.144 -// ecv.push_back(make_pair(e5, 6));
1.145 -// ecv.push_back(make_pair(e6, 5));
1.146 -// ecv.push_back(make_pair(e7, 4));
1.147 -// ecv.push_back(make_pair(e8, 3));
1.148 -// ecv.push_back(make_pair(e9, 2));
1.149 -// ecv.push_back(make_pair(e10, 1));
1.150 -
1.151 -// k0lts = mctk2.run(ecv);
1.152 -// cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
1.153 -// << k0lts << endl;
1.154 -
1.155 -
1.156 - return 0;
1.157 -}