1.1 --- a/src/hugo/mincostflows.h Tue May 11 16:15:18 2004 +0000
1.2 +++ b/src/hugo/mincostflows.h Tue May 11 16:38:17 2004 +0000
1.3 @@ -6,7 +6,7 @@
1.4 ///\file
1.5 ///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost
1.6
1.7 -#include <iostream>
1.8 +
1.9 #include <hugo/dijkstra.h>
1.10 #include <hugo/graph_wrapper.h>
1.11 #include <hugo/maps.h>
2.1 --- a/src/hugo/minlengthpaths.h Tue May 11 16:15:18 2004 +0000
2.2 +++ b/src/hugo/minlengthpaths.h Tue May 11 16:38:17 2004 +0000
2.3 @@ -6,7 +6,7 @@
2.4 ///\file
2.5 ///\brief An algorithm for finding k paths of minimal total length.
2.6
2.7 -#include <iostream>
2.8 +
2.9 //#include <hugo/dijkstra.h>
2.10 //#include <hugo/graph_wrapper.h>
2.11 #include <hugo/maps.h>
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/test/mincostflows_test.cc Tue May 11 16:38:17 2004 +0000
3.3 @@ -0,0 +1,88 @@
3.4 +#include <iostream>
3.5 +#include "test_tools.h"
3.6 +#include <hugo/list_graph.h>
3.7 +#include <hugo/mincostflows.h>
3.8 +//#include <path.h>
3.9 +//#include <maps.h>
3.10 +
3.11 +using namespace std;
3.12 +using namespace hugo;
3.13 +
3.14 +
3.15 +
3.16 +bool passed = true;
3.17 +/*
3.18 +void check(bool rc, char *msg="") {
3.19 + passed = passed && rc;
3.20 + if(!rc) {
3.21 + std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
3.22 +
3.23 +
3.24 + }
3.25 +}
3.26 +*/
3.27 +
3.28 +
3.29 +int main()
3.30 +{
3.31 +
3.32 + typedef ListGraph::Node Node;
3.33 + typedef ListGraph::Edge Edge;
3.34 +
3.35 + ListGraph graph;
3.36 +
3.37 + //Ahuja könyv példája
3.38 +
3.39 + Node s=graph.addNode();
3.40 + Node v1=graph.addNode();
3.41 + Node v2=graph.addNode();
3.42 + Node v3=graph.addNode();
3.43 + Node v4=graph.addNode();
3.44 + Node v5=graph.addNode();
3.45 + Node t=graph.addNode();
3.46 +
3.47 + Edge s_v1=graph.addEdge(s, v1);
3.48 + Edge v1_v2=graph.addEdge(v1, v2);
3.49 + Edge s_v3=graph.addEdge(s, v3);
3.50 + Edge v2_v4=graph.addEdge(v2, v4);
3.51 + Edge v2_v5=graph.addEdge(v2, v5);
3.52 + Edge v3_v5=graph.addEdge(v3, v5);
3.53 + Edge v4_t=graph.addEdge(v4, t);
3.54 + Edge v5_t=graph.addEdge(v5, t);
3.55 +
3.56 +
3.57 + ListGraph::EdgeMap<int> length(graph);
3.58 +
3.59 + length.set(s_v1, 6);
3.60 + length.set(v1_v2, 4);
3.61 + length.set(s_v3, 10);
3.62 + length.set(v2_v4, 5);
3.63 + length.set(v2_v5, 1);
3.64 + length.set(v3_v5, 5);
3.65 + length.set(v4_t, 8);
3.66 + length.set(v5_t, 8);
3.67 +
3.68 + ConstMap<Edge, int> const1map(1);
3.69 + std::cout << "Mincostflows algorithm test..." << std::endl;
3.70 +
3.71 +
3.72 + int k=3;
3.73 + MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> >
3.74 + surb_test(graph, length, const1map);
3.75 +
3.76 + check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
3.77 +
3.78 + check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
3.79 +
3.80 + k=1;
3.81 + check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
3.82 +
3.83 + check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
3.84 +
3.85 +
3.86 + cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
3.87 + << endl;
3.88 +
3.89 + return passed ? 0 : 1;
3.90 +
3.91 +}
4.1 --- a/src/test/minlengthpaths_test.cc Tue May 11 16:15:18 2004 +0000
4.2 +++ b/src/test/minlengthpaths_test.cc Tue May 11 16:38:17 2004 +0000
4.3 @@ -2,6 +2,7 @@
4.4 #include <hugo/list_graph.h>
4.5 #include <hugo/minlengthpaths.h>
4.6 #include <path.h>
4.7 +#include "test_tools.h"
4.8
4.9 using namespace std;
4.10 using namespace hugo;
4.11 @@ -10,16 +11,6 @@
4.12
4.13 bool passed = true;
4.14
4.15 -void check(bool rc, char *msg="") {
4.16 - passed = passed && rc;
4.17 - if(!rc) {
4.18 - std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
4.19 -
4.20 -
4.21 - }
4.22 -}
4.23 -
4.24 -
4.25
4.26 int main()
4.27 {
5.1 --- a/src/work/athos/mincostflows_test.cc Tue May 11 16:15:18 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,103 +0,0 @@
5.4 -#include <iostream>
5.5 -#include <list_graph.h>
5.6 -#include <mincostflows.h>
5.7 -//#include <path.h>
5.8 -//#include <maps.h>
5.9 -
5.10 -using namespace std;
5.11 -using namespace hugo;
5.12 -
5.13 -
5.14 -
5.15 -bool passed = true;
5.16 -
5.17 -void check(bool rc, char *msg="") {
5.18 - passed = passed && rc;
5.19 - if(!rc) {
5.20 - std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
5.21 -
5.22 -
5.23 - }
5.24 -}
5.25 -
5.26 -
5.27 -
5.28 -int main()
5.29 -{
5.30 -
5.31 - typedef ListGraph::Node Node;
5.32 - typedef ListGraph::Edge Edge;
5.33 -
5.34 - ListGraph graph;
5.35 -
5.36 - //Ahuja könyv példája
5.37 -
5.38 - Node s=graph.addNode();
5.39 - Node v1=graph.addNode();
5.40 - Node v2=graph.addNode();
5.41 - Node v3=graph.addNode();
5.42 - Node v4=graph.addNode();
5.43 - Node v5=graph.addNode();
5.44 - Node t=graph.addNode();
5.45 -
5.46 - Edge s_v1=graph.addEdge(s, v1);
5.47 - Edge v1_v2=graph.addEdge(v1, v2);
5.48 - Edge s_v3=graph.addEdge(s, v3);
5.49 - Edge v2_v4=graph.addEdge(v2, v4);
5.50 - Edge v2_v5=graph.addEdge(v2, v5);
5.51 - Edge v3_v5=graph.addEdge(v3, v5);
5.52 - Edge v4_t=graph.addEdge(v4, t);
5.53 - Edge v5_t=graph.addEdge(v5, t);
5.54 -
5.55 -
5.56 - ListGraph::EdgeMap<int> length(graph);
5.57 -
5.58 - length.set(s_v1, 6);
5.59 - length.set(v1_v2, 4);
5.60 - length.set(s_v3, 10);
5.61 - length.set(v2_v4, 5);
5.62 - length.set(v2_v5, 1);
5.63 - length.set(v3_v5, 5);
5.64 - length.set(v4_t, 8);
5.65 - length.set(v5_t, 8);
5.66 -
5.67 - ConstMap<Edge, int> const1map(1);
5.68 - std::cout << "Mincostflows algorithm test..." << std::endl;
5.69 -
5.70 -
5.71 - int k=3;
5.72 - MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> >
5.73 - surb_test(graph, length, const1map);
5.74 -
5.75 - check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
5.76 -
5.77 - check(surb_test.checkSolution(), "Is the primal-dual solution pair really optimal?");
5.78 -
5.79 - k=1;
5.80 - check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
5.81 -
5.82 - check(surb_test.checkSolution(), "Is the primal-dual solution pair really optimal?");
5.83 -
5.84 - //cout << surb_test.run(s,t,k) << surb_test.totalLength()<<endl;
5.85 - /*
5.86 - typedef DirPath<ListGraph> DPath;
5.87 - DPath P(graph);
5.88 -
5.89 - surb_test.getPath(P,0);
5.90 - check(P.length() == 4, "First path should contain 4 edges.");
5.91 -
5.92 - surb_test.getPath(P,1);
5.93 - check(P.length() == 3, "Second path: 3 edges.");
5.94 -
5.95 - k=1;
5.96 - check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
5.97 -
5.98 - surb_test.getPath(P,0);
5.99 - check(P.length() == 4, "First path should contain 4 edges.");
5.100 - */
5.101 - cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
5.102 - << endl;
5.103 -
5.104 - return passed ? 0 : 1;
5.105 -
5.106 -}