athos@659: #include athos@661: //#include "test_tools.h" alpar@921: #include athos@659: #include athos@659: //#include athos@659: //#include athos@659: athos@659: using namespace std; alpar@921: using namespace lemon; athos@659: athos@659: athos@659: athos@659: bool passed = true; athos@672: athos@659: void check(bool rc, char *msg="") { athos@659: passed = passed && rc; athos@659: if(!rc) { athos@659: std::cerr << "Test failed! ("<< msg << ")" << std::endl; \ athos@659: athos@659: athos@659: } athos@659: } athos@672: athos@659: athos@659: athos@659: int main() athos@659: { athos@659: athos@659: typedef ListGraph::Node Node; athos@659: typedef ListGraph::Edge Edge; athos@659: athos@659: ListGraph graph; athos@659: athos@659: //Ahuja könyv példája athos@659: athos@659: Node s=graph.addNode(); athos@659: Node v1=graph.addNode(); athos@659: Node v2=graph.addNode(); athos@659: Node v3=graph.addNode(); athos@659: Node v4=graph.addNode(); athos@659: Node v5=graph.addNode(); athos@659: Node t=graph.addNode(); athos@659: athos@662: ListGraph::NodeMap supply_demand(graph); athos@662: athos@662: supply_demand.set(s, 2); athos@662: supply_demand.set(v1, 3); athos@662: supply_demand.set(v3, -1); athos@662: supply_demand.set(t, -4); athos@662: athos@659: Edge s_v1=graph.addEdge(s, v1); athos@659: Edge v1_v2=graph.addEdge(v1, v2); athos@659: Edge s_v3=graph.addEdge(s, v3); athos@659: Edge v2_v4=graph.addEdge(v2, v4); athos@659: Edge v2_v5=graph.addEdge(v2, v5); athos@659: Edge v3_v5=graph.addEdge(v3, v5); athos@659: Edge v4_t=graph.addEdge(v4, t); athos@659: Edge v5_t=graph.addEdge(v5, t); athos@659: athos@659: athos@661: ListGraph::EdgeMap cost(graph); athos@659: athos@661: cost.set(s_v1, 6); athos@661: cost.set(v1_v2, 4); athos@661: cost.set(s_v3, 10); athos@661: cost.set(v2_v4, 5); athos@661: cost.set(v2_v5, 1); athos@661: cost.set(v3_v5, 4); athos@661: cost.set(v4_t, 8); athos@661: cost.set(v5_t, 8); athos@659: athos@659: /* athos@659: ListGraph::EdgeMap capacity(graph); athos@659: athos@659: capacity.set(s_v1, 2); athos@659: capacity.set(v1_v2, 2); athos@659: capacity.set(s_v3, 1); athos@659: capacity.set(v2_v4, 1); athos@659: capacity.set(v2_v5, 1); athos@659: capacity.set(v3_v5, 1); athos@659: capacity.set(v4_t, 1); athos@659: capacity.set(v5_t, 2); athos@659: */ athos@659: athos@659: // ConstMap const1map(1); athos@659: std::cout << "Enhanced capacity scaling algorithm test (for the mincostflow problem)..." << std::endl; athos@659: athos@659: MinCostFlow< ListGraph, ListGraph::EdgeMap, ListGraph::NodeMap > athos@661: min_cost_flow_test(graph, cost, supply_demand); athos@659: athos@662: min_cost_flow_test.run(); athos@662: //int k=1; athos@672: check(min_cost_flow_test.checkOptimality(), "Is the primal-dual solution pair really optimal?"); athos@659: athos@659: /* athos@661: check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19"); athos@659: athos@659: check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); athos@659: athos@659: k=2; athos@659: athos@661: check( min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total cost should be 41"); athos@659: athos@659: check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); athos@659: athos@659: athos@659: k=4; athos@659: athos@661: check( min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total cost should be 64"); athos@659: athos@659: check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); athos@659: athos@672: */ athos@659: cout << (passed ? "All tests passed." : "Some of the tests failed!!!") athos@659: << endl; athos@659: athos@659: return passed ? 0 : 1; athos@672: athos@659: }