Test file for the min cost flow algorithms.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
20 #include <lemon/list_graph.h>
21 #include <lemon/suurballe.h>
23 #include "test_tools.h"
25 using namespace lemon;
33 typedef ListGraph Graph;
34 typedef Graph::Node Node;
35 typedef Graph::Edge Edge;
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();
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);
59 Graph::EdgeMap<int> length(graph);
70 std::cout << "Minlengthpaths algorithm test..." << std::endl;
74 Suurballe< Graph, Graph::EdgeMap<int> >
75 surb_test(graph, length, s, t);
77 check( surb_test.run(k) == 2 && surb_test.totalLength() == 46,
78 "Two paths, total length should be 46");
80 check( surb_test.checkComplementarySlackness(),
81 "Complementary slackness conditions are not met.");
83 // typedef DirPath<Graph> DPath;
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;
96 check( surb_test.run(k) == 1 && surb_test.totalLength() == 19,
97 "One path, total length should be 19");
99 check( surb_test.checkComplementarySlackness(),
100 "Complementary slackness conditions are not met.");
102 // surb_test.getPath(P,0);
103 // check(P.length() == 4, "First path should contain 4 edges.");
105 std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
108 return passed ? 0 : 1;