1.1 --- a/src/work/athos/min_cost_flow.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,119 +0,0 @@
1.4 -#include <iostream>
1.5 -//#include "test_tools.h"
1.6 -#include <lemon/list_graph.h>
1.7 -#include <mincostflow.h>
1.8 -//#include <path.h>
1.9 -//#include <maps.h>
1.10 -
1.11 -using namespace std;
1.12 -using namespace lemon;
1.13 -
1.14 -
1.15 -
1.16 -bool passed = true;
1.17 -
1.18 -void check(bool rc, char *msg="") {
1.19 - passed = passed && rc;
1.20 - if(!rc) {
1.21 - std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
1.22 -
1.23 -
1.24 - }
1.25 -}
1.26 -
1.27 -
1.28 -
1.29 -int main()
1.30 -{
1.31 -
1.32 - typedef ListGraph::Node Node;
1.33 - typedef ListGraph::Edge Edge;
1.34 -
1.35 - ListGraph graph;
1.36 -
1.37 - //Ahuja könyv példája
1.38 -
1.39 - Node s=graph.addNode();
1.40 - Node v1=graph.addNode();
1.41 - Node v2=graph.addNode();
1.42 - Node v3=graph.addNode();
1.43 - Node v4=graph.addNode();
1.44 - Node v5=graph.addNode();
1.45 - Node t=graph.addNode();
1.46 -
1.47 - ListGraph::NodeMap<int> supply_demand(graph);
1.48 -
1.49 - supply_demand.set(s, 2);
1.50 - supply_demand.set(v1, 3);
1.51 - supply_demand.set(v3, -1);
1.52 - supply_demand.set(t, -4);
1.53 -
1.54 - Edge s_v1=graph.addEdge(s, v1);
1.55 - Edge v1_v2=graph.addEdge(v1, v2);
1.56 - Edge s_v3=graph.addEdge(s, v3);
1.57 - Edge v2_v4=graph.addEdge(v2, v4);
1.58 - Edge v2_v5=graph.addEdge(v2, v5);
1.59 - Edge v3_v5=graph.addEdge(v3, v5);
1.60 - Edge v4_t=graph.addEdge(v4, t);
1.61 - Edge v5_t=graph.addEdge(v5, t);
1.62 -
1.63 -
1.64 - ListGraph::EdgeMap<int> cost(graph);
1.65 -
1.66 - cost.set(s_v1, 6);
1.67 - cost.set(v1_v2, 4);
1.68 - cost.set(s_v3, 10);
1.69 - cost.set(v2_v4, 5);
1.70 - cost.set(v2_v5, 1);
1.71 - cost.set(v3_v5, 4);
1.72 - cost.set(v4_t, 8);
1.73 - cost.set(v5_t, 8);
1.74 -
1.75 - /*
1.76 - ListGraph::EdgeMap<int> capacity(graph);
1.77 -
1.78 - capacity.set(s_v1, 2);
1.79 - capacity.set(v1_v2, 2);
1.80 - capacity.set(s_v3, 1);
1.81 - capacity.set(v2_v4, 1);
1.82 - capacity.set(v2_v5, 1);
1.83 - capacity.set(v3_v5, 1);
1.84 - capacity.set(v4_t, 1);
1.85 - capacity.set(v5_t, 2);
1.86 - */
1.87 -
1.88 - // ConstMap<Edge, int> const1map(1);
1.89 - std::cout << "Enhanced capacity scaling algorithm test (for the mincostflow problem)..." << std::endl;
1.90 -
1.91 - MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::NodeMap<int> >
1.92 - min_cost_flow_test(graph, cost, supply_demand);
1.93 -
1.94 - min_cost_flow_test.run();
1.95 - //int k=1;
1.96 - check(min_cost_flow_test.checkOptimality(), "Is the primal-dual solution pair really optimal?");
1.97 -
1.98 - /*
1.99 - check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19");
1.100 -
1.101 - check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.102 -
1.103 - k=2;
1.104 -
1.105 - check( min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total cost should be 41");
1.106 -
1.107 - check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.108 -
1.109 -
1.110 - k=4;
1.111 -
1.112 - check( min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total cost should be 64");
1.113 -
1.114 - check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
1.115 -
1.116 - */
1.117 - cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
1.118 - << endl;
1.119 -
1.120 - return passed ? 0 : 1;
1.121 -
1.122 -}