beckerjc@150: #include <string>
beckerjc@150: #include <iostream>
beckerjc@150: #include <map>
beckerjc@246: #include <vector>
beckerjc@150: 
beckerjc@150: #include <kruskal.h>
alpar@737: #include <hugo/list_graph.h>
beckerjc@150: 
beckerjc@150: 
beckerjc@150: using namespace std;
beckerjc@150: using namespace hugo;
beckerjc@150: 
beckerjc@150: class string_int_map : public map<string,int> {
beckerjc@150: public:
beckerjc@150:   int get(const string &s) {
beckerjc@150:     // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
beckerjc@150:     // hogy is mukodik ez a map :)
beckerjc@150:     if( count(s) == 0 ) {
beckerjc@150:       operator[](s) = -1;
beckerjc@150:     }
beckerjc@150:     return operator[](s);
beckerjc@150:   }
beckerjc@150:   void set(const string &s, int i) {
beckerjc@150:       operator[](s) = i;
beckerjc@150:   }
beckerjc@150: };
beckerjc@150: 
beckerjc@150: 
beckerjc@218: // Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
beckerjc@218: // Valami elegansabb megoldas kene a Kruskalban...
beckerjc@218: 
beckerjc@218: template <typename K, typename V>
beckerjc@218: class DummyMap {
beckerjc@218: public:
beckerjc@218:   typedef K KeyType;
beckerjc@218:   typedef V ValueType;
beckerjc@218: };
beckerjc@218: 
beckerjc@150: int main() {
beckerjc@150: 
beckerjc@218:   typedef ListGraph::Node Node;
beckerjc@218:   typedef ListGraph::Edge Edge;
beckerjc@150:   typedef ListGraph::NodeIt NodeIt;
beckerjc@150:   typedef ListGraph::EdgeIt EdgeIt;
beckerjc@150: 
beckerjc@150:   ListGraph G;
beckerjc@150: 
beckerjc@218:   Node s=G.addNode();
beckerjc@218:   Node v1=G.addNode();
beckerjc@218:   Node v2=G.addNode();
beckerjc@218:   Node v3=G.addNode();
beckerjc@218:   Node v4=G.addNode();
beckerjc@218:   Node t=G.addNode();
beckerjc@150:   
beckerjc@218:   Edge e1 = G.addEdge(s, v1);
beckerjc@218:   Edge e2 = G.addEdge(s, v2);
beckerjc@218:   Edge e3 = G.addEdge(v1, v2);
beckerjc@218:   Edge e4 = G.addEdge(v2, v1);
beckerjc@218:   Edge e5 = G.addEdge(v1, v3);
beckerjc@218:   Edge e6 = G.addEdge(v3, v2);
beckerjc@218:   Edge e7 = G.addEdge(v2, v4);
beckerjc@218:   Edge e8 = G.addEdge(v4, v3);
beckerjc@218:   Edge e9 = G.addEdge(v3, t);
beckerjc@218:   Edge e10 = G.addEdge(v4, t);
beckerjc@150: 
beckerjc@218:   typedef ListGraph::EdgeMap<double> ECostMap;
beckerjc@218:   typedef ListGraph::EdgeMap<bool> EBoolMap;
beckerjc@218: 
beckerjc@218:   ECostMap edge_cost_map(G, 2);
beckerjc@218:   EBoolMap tree_map(G);
beckerjc@150:   
beckerjc@150: 
beckerjc@246:   cout << "Uniform 2-es koltseggel: " 
alpar@737:        << kruskalEdgeMap(G, edge_cost_map, tree_map)
beckerjc@246:        << endl;
beckerjc@218: 
beckerjc@218: 
beckerjc@246:   edge_cost_map.set(e1, -10);
beckerjc@246:   edge_cost_map.set(e2, -9);
beckerjc@246:   edge_cost_map.set(e3, -8);
beckerjc@246:   edge_cost_map.set(e4, -7);
beckerjc@246:   edge_cost_map.set(e5, -6);
beckerjc@246:   edge_cost_map.set(e6, -5);
beckerjc@246:   edge_cost_map.set(e7, -4);
beckerjc@246:   edge_cost_map.set(e8, -3);
beckerjc@246:   edge_cost_map.set(e9, -2);
beckerjc@246:   edge_cost_map.set(e10, -1);
beckerjc@218: 
beckerjc@246:   vector<Edge> tree_edge_vec;
beckerjc@246: 
beckerjc@246:   cout << "Nemkonst koltseggel (-31): "
alpar@737:        << kruskalEdgeMap_IteratorOut(G, edge_cost_map,
alpar@737: 				     back_inserter(tree_edge_vec))
beckerjc@246:        << endl;
beckerjc@246: 
beckerjc@246:   int i = 1;
beckerjc@246:   for(vector<Edge>::iterator e = tree_edge_vec.begin();
beckerjc@246:       e != tree_edge_vec.end(); ++e, ++i) {
alpar@737:     cout << i << ". el: " << G.id(*e) << endl;
beckerjc@246:   }
beckerjc@246: 
beckerjc@349:   tree_edge_vec.clear();
beckerjc@352: //   SequenceOutput< back_insert_iterator< vector<Edge> > > 
beckerjc@352: //     vec_filler(back_inserter(tree_edge_vec));
beckerjc@352: //   cout << "Nemkonst koltseggel tarhatekonyabban: "
beckerjc@352: //        << Kruskal(G,
beckerjc@352: // 		  KruskalMapVec<ECostMap>(G, edge_cost_map),
beckerjc@352: // 		  vec_filler)
beckerjc@352: //        << endl;
beckerjc@349: 
alpar@737: //   cout << "Nemkonst koltseggel tarhatekonyabban: "
alpar@737: //        << kruskal(G,
alpar@737: // 		  KruskalMapVec<ECostMap>(G, edge_cost_map),
alpar@737: // 		  makeSequenceOutput(back_inserter(tree_edge_vec))
alpar@737: // 		  )
alpar@737: //        << endl;
beckerjc@349: 
alpar@737: //   i = 1;
alpar@737: //   for(vector<Edge>::iterator e = tree_edge_vec.begin();
alpar@737: //       e != tree_edge_vec.end(); ++e, ++i) {
alpar@737: //     cout << i << ". el: " << *e << endl;
alpar@737: //   }
alpar@737: 
alpar@737: // **********************************************************************
beckerjc@246: 
beckerjc@246: //   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
beckerjc@246: 
beckerjc@246: //   MCTK mctk(G, edge_cost_map, tree_map);
beckerjc@246: //   double k0lts = mctk.run();
beckerjc@246: 
beckerjc@246: //   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
beckerjc@246: 
beckerjc@246: //   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
beckerjc@246: //   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
beckerjc@246: //   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
beckerjc@246: //   MCTK2::EdgeCostVector ecv;
beckerjc@246: //   ecv.push_back(make_pair(e1, 10));
beckerjc@246: //   ecv.push_back(make_pair(e2, 9));
beckerjc@246: //   ecv.push_back(make_pair(e3, 8));
beckerjc@246: //   ecv.push_back(make_pair(e4, 7));
beckerjc@246: //   ecv.push_back(make_pair(e5, 6));
beckerjc@246: //   ecv.push_back(make_pair(e6, 5));
beckerjc@246: //   ecv.push_back(make_pair(e7, 4));
beckerjc@246: //   ecv.push_back(make_pair(e8, 3));
beckerjc@246: //   ecv.push_back(make_pair(e9, 2));
beckerjc@246: //   ecv.push_back(make_pair(e10, 1));
beckerjc@246: 
beckerjc@246: //   k0lts = mctk2.run(ecv);
beckerjc@246: //   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
beckerjc@246: //        << k0lts << endl;
beckerjc@218: 
beckerjc@150: 
beckerjc@150:   return 0;
beckerjc@150: }