15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #include <iostream> |
19 #include <iostream> |
20 #include <fstream> |
|
21 |
20 |
22 #include <lemon/list_graph.h> |
21 #include <lemon/list_graph.h> |
23 #include <lemon/lgf_reader.h> |
22 #include <lemon/lgf_reader.h> |
24 #include <lemon/path.h> |
23 #include <lemon/path.h> |
25 #include <lemon/suurballe.h> |
24 #include <lemon/suurballe.h> |
26 |
25 |
27 #include "test_tools.h" |
26 #include "test_tools.h" |
28 |
27 |
29 using namespace lemon; |
28 using namespace lemon; |
|
29 |
|
30 char test_lgf[] = |
|
31 "@nodes\n" |
|
32 "label supply1 supply2 supply3\n" |
|
33 "1 0 20 27\n" |
|
34 "2 0 -4 0\n" |
|
35 "3 0 0 0\n" |
|
36 "4 0 0 0\n" |
|
37 "5 0 9 0\n" |
|
38 "6 0 -6 0\n" |
|
39 "7 0 0 0\n" |
|
40 "8 0 0 0\n" |
|
41 "9 0 3 0\n" |
|
42 "10 0 -2 0\n" |
|
43 "11 0 0 0\n" |
|
44 "12 0 -20 -27\n" |
|
45 "@arcs\n" |
|
46 " cost capacity lower1 lower2\n" |
|
47 " 1 2 70 11 0 8\n" |
|
48 " 1 3 150 3 0 1\n" |
|
49 " 1 4 80 15 0 2\n" |
|
50 " 2 8 80 12 0 0\n" |
|
51 " 3 5 140 5 0 3\n" |
|
52 " 4 6 60 10 0 1\n" |
|
53 " 4 7 80 2 0 0\n" |
|
54 " 4 8 110 3 0 0\n" |
|
55 " 5 7 60 14 0 0\n" |
|
56 " 5 11 120 12 0 0\n" |
|
57 " 6 3 0 3 0 0\n" |
|
58 " 6 9 140 4 0 0\n" |
|
59 " 6 10 90 8 0 0\n" |
|
60 " 7 1 30 5 0 0\n" |
|
61 " 8 12 60 16 0 4\n" |
|
62 " 9 12 50 6 0 0\n" |
|
63 "10 12 70 13 0 5\n" |
|
64 "10 2 100 7 0 0\n" |
|
65 "10 7 60 10 0 0\n" |
|
66 "11 10 20 14 0 6\n" |
|
67 "12 11 30 10 0 0\n" |
|
68 "@attributes\n" |
|
69 "source 1\n" |
|
70 "target 12\n" |
|
71 "@end\n"; |
30 |
72 |
31 // Check the feasibility of the flow |
73 // Check the feasibility of the flow |
32 template <typename Digraph, typename FlowMap> |
74 template <typename Digraph, typename FlowMap> |
33 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
75 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
34 typename Digraph::Node s, typename Digraph::Node t, |
76 typename Digraph::Node s, typename Digraph::Node t, |
94 // Read the test digraph |
136 // Read the test digraph |
95 ListDigraph digraph; |
137 ListDigraph digraph; |
96 ListDigraph::ArcMap<int> length(digraph); |
138 ListDigraph::ArcMap<int> length(digraph); |
97 Node source, target; |
139 Node source, target; |
98 |
140 |
99 std::string fname; |
141 std::istringstream input(test_lgf); |
100 if(getenv("srcdir")) |
|
101 fname = std::string(getenv("srcdir")); |
|
102 else fname = "."; |
|
103 fname += "/test/min_cost_flow_test.lgf"; |
|
104 |
|
105 std::ifstream input(fname.c_str()); |
|
106 check(input, "Input file '" << fname << "' not found"); |
|
107 DigraphReader<ListDigraph>(digraph, input). |
142 DigraphReader<ListDigraph>(digraph, input). |
108 arcMap("cost", length). |
143 arcMap("cost", length). |
109 node("source", source). |
144 node("source", source). |
110 node("target", target). |
145 node("target", target). |
111 run(); |
146 run(); |
112 input.close(); |
|
113 |
147 |
114 // Find 2 paths |
148 // Find 2 paths |
115 { |
149 { |
116 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
150 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
117 check(suurballe.run(2) == 2, "Wrong number of paths"); |
151 check(suurballe.run(2) == 2, "Wrong number of paths"); |