beckerjc@150: #include beckerjc@150: #include beckerjc@150: #include beckerjc@246: #include beckerjc@150: beckerjc@150: #include alpar@737: #include beckerjc@150: beckerjc@150: beckerjc@150: using namespace std; beckerjc@150: using namespace hugo; beckerjc@150: beckerjc@150: class string_int_map : public map { 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 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 ECostMap; beckerjc@218: typedef ListGraph::EdgeMap 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 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::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 > > beckerjc@352: // vec_filler(back_inserter(tree_edge_vec)); beckerjc@352: // cout << "Nemkonst koltseggel tarhatekonyabban: " beckerjc@352: // << Kruskal(G, beckerjc@352: // KruskalMapVec(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(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::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 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, EBoolMap> MCTK2; beckerjc@246: // MCTK2 mctk2(G, DummyMap(), 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: }