Changeset 2586:37fb2c384c78 in lemon-0.x for test/suurballe_test.cc
- Timestamp:
- 02/29/08 16:55:13 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3468
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/suurballe_test.cc
r2553 r2586 18 18 19 19 #include <iostream> 20 #include <fstream> 21 20 22 #include <lemon/list_graph.h> 23 #include <lemon/graph_reader.h> 24 #include <lemon/path.h> 21 25 #include <lemon/suurballe.h> 22 //#include <path.h> 26 23 27 #include "test_tools.h" 24 28 25 29 using namespace lemon; 26 30 31 // Checks the feasibility of the flow 32 template <typename Graph, typename FlowMap> 33 bool checkFlow( const Graph& gr, const FlowMap& flow, 34 typename Graph::Node s, typename Graph::Node t, 35 int value ) 36 { 37 GRAPH_TYPEDEFS(typename Graph); 38 for (EdgeIt e(gr); e != INVALID; ++e) 39 if (!(flow[e] == 0 || flow[e] == 1)) return false; 27 40 28 bool passed = true; 41 for (NodeIt n(gr); n != INVALID; ++n) { 42 int sum = 0; 43 for (OutEdgeIt e(gr, n); e != INVALID; ++e) 44 sum += flow[e]; 45 for (InEdgeIt e(gr, n); e != INVALID; ++e) 46 sum -= flow[e]; 47 if (n == s && sum != value) return false; 48 if (n == t && sum != -value) return false; 49 if (n != s && n != t && sum != 0) return false; 50 } 51 52 return true; 53 } 54 55 // Checks the optimalitiy of the flow 56 template < typename Graph, typename CostMap, 57 typename FlowMap, typename PotentialMap > 58 bool checkOptimality( const Graph& gr, const CostMap& cost, 59 const FlowMap& flow, const PotentialMap& pi ) 60 { 61 // Checking the Complementary Slackness optimality condition 62 GRAPH_TYPEDEFS(typename Graph); 63 bool opt = true; 64 for (EdgeIt e(gr); e != INVALID; ++e) { 65 typename CostMap::Value red_cost = 66 cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; 67 opt = (flow[e] == 0 && red_cost >= 0) || 68 (flow[e] == 1 && red_cost <= 0); 69 if (!opt) break; 70 } 71 return opt; 72 } 73 74 // Checks a path 75 template < typename Graph, typename Path > 76 bool checkPath( const Graph& gr, const Path& path, 77 typename Graph::Node s, typename Graph::Node t) 78 { 79 // Checking the Complementary Slackness optimality condition 80 GRAPH_TYPEDEFS(typename Graph); 81 Node n = s; 82 for (int i = 0; i < path.length(); ++i) { 83 if (gr.source(path.nth(i)) != n) return false; 84 n = gr.target(path.nth(i)); 85 } 86 return n == t; 87 } 29 88 30 89 31 90 int main() 32 91 { 33 typedef ListGraph Graph; 34 typedef Graph::Node Node; 35 typedef Graph::Edge Edge; 92 GRAPH_TYPEDEFS(ListGraph); 36 93 37 Graph graph; 94 // Reading the test graph 95 ListGraph graph; 96 ListGraph::EdgeMap<int> length(graph); 97 Node source, target; 38 98 39 //Ahuja könyv példája 99 std::string fname; 100 if(getenv("srcdir")) 101 fname = std::string(getenv("srcdir")); 102 else fname = "."; 103 fname += "/test/min_cost_flow_test.lgf"; 40 104 41 Node s=graph.addNode(); 42 Node v1=graph.addNode(); 43 Node v2=graph.addNode(); 44 Node v3=graph.addNode(); 45 Node v4=graph.addNode(); 46 Node v5=graph.addNode(); 47 Node t=graph.addNode(); 105 std::ifstream input(fname.c_str()); 106 check(input, "Input file '" << fname << "' not found"); 107 GraphReader<ListGraph>(input, graph). 108 readEdgeMap("cost", length). 109 readNode("source", source). 110 readNode("target", target). 111 run(); 112 input.close(); 113 114 // Finding 2 paths 115 { 116 Suurballe<ListGraph> suurballe(graph, length, source, target); 117 check(suurballe.run(2) == 2, "Wrong number of paths"); 118 check(checkFlow(graph, suurballe.flowMap(), source, target, 2), 119 "The flow is not feasible"); 120 check(suurballe.totalLength() == 510, "The flow is not optimal"); 121 check(checkOptimality(graph, length, suurballe.flowMap(), 122 suurballe.potentialMap()), 123 "Wrong potentials"); 124 for (int i = 0; i < suurballe.pathNum(); ++i) 125 check(checkPath(graph, suurballe.path(i), source, target), 126 "Wrong path"); 127 } 48 128 49 Edge s_v1=graph.addEdge(s, v1); 50 Edge v1_v2=graph.addEdge(v1, v2); 51 Edge s_v3=graph.addEdge(s, v3); 52 Edge v2_v4=graph.addEdge(v2, v4); 53 Edge v2_v5=graph.addEdge(v2, v5); 54 Edge v3_v5=graph.addEdge(v3, v5); 55 Edge v4_t=graph.addEdge(v4, t); 56 Edge v5_t=graph.addEdge(v5, t); 57 129 // Finding 3 paths 130 { 131 Suurballe<ListGraph> suurballe(graph, length, source, target); 132 check(suurballe.run(3) == 3, "Wrong number of paths"); 133 check(checkFlow(graph, suurballe.flowMap(), source, target, 3), 134 "The flow is not feasible"); 135 check(suurballe.totalLength() == 1040, "The flow is not optimal"); 136 check(checkOptimality(graph, length, suurballe.flowMap(), 137 suurballe.potentialMap()), 138 "Wrong potentials"); 139 for (int i = 0; i < suurballe.pathNum(); ++i) 140 check(checkPath(graph, suurballe.path(i), source, target), 141 "Wrong path"); 142 } 58 143 59 Graph::EdgeMap<int> length(graph); 144 // Finding 5 paths (only 3 can be found) 145 { 146 Suurballe<ListGraph> suurballe(graph, length, source, target); 147 check(suurballe.run(5) == 3, "Wrong number of paths"); 148 check(checkFlow(graph, suurballe.flowMap(), source, target, 3), 149 "The flow is not feasible"); 150 check(suurballe.totalLength() == 1040, "The flow is not optimal"); 151 check(checkOptimality(graph, length, suurballe.flowMap(), 152 suurballe.potentialMap()), 153 "Wrong potentials"); 154 for (int i = 0; i < suurballe.pathNum(); ++i) 155 check(checkPath(graph, suurballe.path(i), source, target), 156 "Wrong path"); 157 } 60 158 61 length.set(s_v1, 6); 62 length.set(v1_v2, 4); 63 length.set(s_v3, 10); 64 length.set(v2_v4, 5); 65 length.set(v2_v5, 1); 66 length.set(v3_v5, 5); 67 length.set(v4_t, 8); 68 length.set(v5_t, 8); 69 70 std::cout << "Minlengthpaths algorithm test..." << std::endl; 71 72 73 int k=3; 74 Suurballe< Graph, Graph::EdgeMap<int> > 75 surb_test(graph, length, s, t); 76 77 check( surb_test.run(k) == 2 && surb_test.totalLength() == 46, 78 "Two paths, total length should be 46"); 79 80 check( surb_test.checkComplementarySlackness(), 81 "Complementary slackness conditions are not met."); 82 83 // typedef DirPath<Graph> DPath; 84 // DPath P(graph); 85 86 /* 87 surb_test.getPath(P,0); 88 check(P.length() == 4, "First path should contain 4 edges."); 89 std::cout<<P.length()<<std::endl; 90 surb_test.getPath(P,1); 91 check(P.length() == 3, "Second path: 3 edges."); 92 std::cout<<P.length()<<std::endl; 93 */ 94 95 k=1; 96 check( surb_test.run(k) == 1 && surb_test.totalLength() == 19, 97 "One path, total length should be 19"); 98 99 check( surb_test.checkComplementarySlackness(), 100 "Complementary slackness conditions are not met."); 101 102 // surb_test.getPath(P,0); 103 // check(P.length() == 4, "First path should contain 4 edges."); 104 105 std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!") 106 << std::endl; 107 108 return passed ? 0 : 1; 109 159 return 0; 110 160 }
Note: See TracChangeset
for help on using the changeset viewer.