alpar@906: /* -*- C++ -*- alpar@921: * src/test/kruskal_test.cc - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@906: * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, 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 klao@959: #include klao@959: #include alpar@810: alpar@810: alpar@810: using namespace std; alpar@921: using namespace lemon; alpar@810: alpar@810: void checkCompileKruskal() alpar@810: { klao@959: concept::WriteMap w; alpar@810: klao@959: kruskalEdgeMap(concept::StaticGraph(), klao@959: concept::ReadMap(), alpar@810: w); alpar@810: } alpar@810: alpar@810: int main() { alpar@810: alpar@810: typedef ListGraph::Node Node; alpar@810: typedef ListGraph::Edge Edge; alpar@810: typedef ListGraph::NodeIt NodeIt; alpar@810: typedef ListGraph::EdgeIt EdgeIt; alpar@810: alpar@810: ListGraph 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: alpar@810: Edge e1 = G.addEdge(s, v1); alpar@810: Edge e2 = G.addEdge(s, v2); alpar@810: Edge e3 = G.addEdge(v1, v2); alpar@810: Edge e4 = G.addEdge(v2, v1); alpar@810: Edge e5 = G.addEdge(v1, v3); alpar@810: Edge e6 = G.addEdge(v3, v2); alpar@810: Edge e7 = G.addEdge(v2, v4); alpar@810: Edge e8 = G.addEdge(v4, v3); alpar@810: Edge e9 = G.addEdge(v3, t); alpar@810: Edge e10 = G.addEdge(v4, t); alpar@810: alpar@810: typedef ListGraph::EdgeMap ECostMap; alpar@810: typedef ListGraph::EdgeMap 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. alpar@810: check(kruskalEdgeMap(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@810: check(kruskalEdgeMap(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: alpar@810: vector tree_edge_vec; alpar@810: alpar@810: //Test with a edge map and inserter. alpar@810: check(kruskalEdgeMap_IteratorOut(G, edge_cost_map, alpar@810: back_inserter(tree_edge_vec)) alpar@810: ==-31, alpar@810: "Total cost should be -31."); alpar@810: klao@885: tree_edge_vec.clear(); klao@885: klao@885: //The above test could also be coded like this: klao@885: check(kruskal(G, klao@885: makeKruskalMapInput(G, edge_cost_map), klao@885: makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) klao@885: ==-31, klao@885: "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: alpar@810: return 0; alpar@810: }