alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@810: #include alpar@810: #include alpar@810: alpar@810: #include "test_tools.h" alpar@921: #include alpar@921: #include alpar@921: #include deba@2424: alpar@2260: #include alpar@2260: #include deba@2424: #include alpar@810: alpar@810: alpar@810: using namespace std; alpar@921: using namespace lemon; alpar@810: alpar@810: void checkCompileKruskal() alpar@810: { alpar@2260: concepts::WriteMap w; deba@2424: concepts::WriteMap uw; deba@2424: deba@2424: concepts::ReadMap r; deba@2424: concepts::ReadMap ur; alpar@810: alpar@2260: concepts::Graph g; deba@2424: concepts::UGraph ug; deba@2424: deba@2424: kruskal(g, r, w); deba@2424: kruskal(ug, ur, uw); deba@2424: deba@2424: std::vector > rs; deba@2424: std::vector > urs; deba@2424: deba@2424: kruskal(g, rs, w); deba@2424: kruskal(ug, urs, uw); deba@2424: deba@2424: std::vector ws; deba@2424: std::vector uws; deba@2424: deba@2424: kruskal(g, r, ws.begin()); deba@2424: kruskal(ug, ur, uws.begin()); deba@2424: deba@2424: Kruskal > deba@2424: alg(ug, ur); deba@2424: deba@2424: alg.init(); deba@2424: alg.initPresorted(uws.begin(), uws.end()); deba@2424: alg.reinit(); deba@2424: deba@2424: alg.emptyQueue(); deba@2424: deba@2424: alg.nextEdge(); deba@2424: alg.processNextEdge(); deba@2424: alg.processEdge(concepts::UGraph::UEdge()); deba@2424: deba@2424: alg.run(); deba@2424: deba@2424: alg.treeMap(); deba@2424: alg.tree(concepts::UGraph::UEdge()); alpar@810: } alpar@810: alpar@810: int main() { alpar@810: deba@2424: typedef ListUGraph::Node Node; deba@2424: typedef ListUGraph::UEdge UEdge; deba@2424: typedef ListUGraph::NodeIt NodeIt; deba@2424: typedef ListUGraph::EdgeIt EdgeIt; alpar@810: deba@2424: ListUGraph G; alpar@810: alpar@810: Node s=G.addNode(); alpar@810: Node v1=G.addNode(); alpar@810: Node v2=G.addNode(); alpar@810: Node v3=G.addNode(); alpar@810: Node v4=G.addNode(); alpar@810: Node t=G.addNode(); alpar@810: deba@2424: UEdge e1 = G.addEdge(s, v1); deba@2424: UEdge e2 = G.addEdge(s, v2); deba@2424: UEdge e3 = G.addEdge(v1, v2); deba@2424: UEdge e4 = G.addEdge(v2, v1); deba@2424: UEdge e5 = G.addEdge(v1, v3); deba@2424: UEdge e6 = G.addEdge(v3, v2); deba@2424: UEdge e7 = G.addEdge(v2, v4); deba@2424: UEdge e8 = G.addEdge(v4, v3); deba@2424: UEdge e9 = G.addEdge(v3, t); deba@2424: UEdge e10 = G.addEdge(v4, t); alpar@810: deba@2424: typedef ListUGraph::UEdgeMap ECostMap; deba@2424: typedef ListUGraph::UEdgeMap EBoolMap; alpar@810: alpar@810: ECostMap edge_cost_map(G, 2); alpar@810: EBoolMap tree_map(G); alpar@810: alpar@810: alpar@810: //Test with const map. deba@2424: check(kruskal(G, ConstMap(2), tree_map)==10, alpar@810: "Total cost should be 10"); alpar@810: //Test with a edge map (filled with uniform costs). alpar@1557: check(kruskal(G, edge_cost_map, tree_map)==10, alpar@810: "Total cost should be 10"); alpar@810: alpar@810: edge_cost_map.set(e1, -10); alpar@810: edge_cost_map.set(e2, -9); alpar@810: edge_cost_map.set(e3, -8); alpar@810: edge_cost_map.set(e4, -7); alpar@810: edge_cost_map.set(e5, -6); alpar@810: edge_cost_map.set(e6, -5); alpar@810: edge_cost_map.set(e7, -4); alpar@810: edge_cost_map.set(e8, -3); alpar@810: edge_cost_map.set(e9, -2); alpar@810: edge_cost_map.set(e10, -1); alpar@810: deba@2424: vector tree_edge_vec(5); alpar@810: alpar@810: //Test with a edge map and inserter. alpar@1557: check(kruskal(G, edge_cost_map, alpar@1557: tree_edge_vec.begin()) alpar@810: ==-31, alpar@810: "Total cost should be -31."); alpar@1557: klao@885: tree_edge_vec.clear(); klao@885: alpar@1557: check(kruskal(G, edge_cost_map, alpar@1557: back_inserter(tree_edge_vec)) alpar@1557: ==-31, alpar@1557: "Total cost should be -31."); alpar@1557: deba@2424: // tree_edge_vec.clear(); alpar@1557: deba@2424: // //The above test could also be coded like this: deba@2424: // check(kruskal(G, deba@2424: // makeKruskalMapInput(G, edge_cost_map), deba@2424: // makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) deba@2424: // ==-31, deba@2424: // "Total cost should be -31."); klao@885: alpar@810: check(tree_edge_vec.size()==5,"The tree should have 5 edges."); alpar@810: alpar@810: check(tree_edge_vec[0]==e1 && alpar@810: tree_edge_vec[1]==e2 && alpar@810: tree_edge_vec[2]==e5 && alpar@810: tree_edge_vec[3]==e7 && alpar@810: tree_edge_vec[4]==e9, alpar@810: "Wrong tree."); alpar@810: deba@2424: Kruskal ka(G, edge_cost_map); deba@2424: deba@2424: ka.run(); deba@2424: deba@2424: check(ka.tree(e1) && deba@2424: ka.tree(e2) && deba@2424: ka.tree(e5) && deba@2424: ka.tree(e7) && deba@2424: ka.tree(e9), deba@2424: "Wrong tree."); deba@2424: deba@2424: check(ka.treeValue() == -31, deba@2424: "Total cost should be -31."); deba@2424: alpar@810: return 0; alpar@810: }