r423:ff48c2738fb2
Mon, 08 Dec 2008 16:18:04
[Not Reviewed]
0 comments (0 inline)
2
3
0
| 1 | 1 |
EXTRA_DIST += \ |
| 2 |
test/CMakeLists.txt \ |
|
| 3 |
test/min_cost_flow_test.lgf \ |
|
| 4 |
|
|
| 2 |
test/CMakeLists.txt |
|
| 5 | 3 |
|
| 6 | 4 |
noinst_HEADERS += \ |
| 7 | 5 |
test/graph_test.h \ |
| 8 | 6 |
test/test_tools.h |
| 9 | 7 |
|
| 10 | 8 |
check_PROGRAMS += \ |
| 11 | 9 |
test/bfs_test \ |
| 12 | 10 |
test/circulation_test \ |
| 13 | 11 |
test/counter_test \ |
| 14 | 12 |
test/dfs_test \ |
| 15 | 13 |
test/digraph_test \ |
| 16 | 14 |
test/dijkstra_test \ |
| ... | ... |
@@ -7,37 +7,72 @@ |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 |
#include <fstream> |
|
| 20 |
#include <string> |
|
| 19 |
#include <iostream> |
|
| 21 | 20 |
|
| 22 | 21 |
#include "test_tools.h" |
| 23 | 22 |
#include <lemon/smart_graph.h> |
| 24 | 23 |
#include <lemon/preflow.h> |
| 25 | 24 |
#include <lemon/concepts/digraph.h> |
| 26 | 25 |
#include <lemon/concepts/maps.h> |
| 27 | 26 |
#include <lemon/lgf_reader.h> |
| 28 | 27 |
#include <lemon/elevator.h> |
| 29 | 28 |
|
| 30 | 29 |
using namespace lemon; |
| 31 | 30 |
|
| 31 |
char test_lgf[] = |
|
| 32 |
"@nodes\n" |
|
| 33 |
"label\n" |
|
| 34 |
"0\n" |
|
| 35 |
"1\n" |
|
| 36 |
"2\n" |
|
| 37 |
"3\n" |
|
| 38 |
"4\n" |
|
| 39 |
"5\n" |
|
| 40 |
"6\n" |
|
| 41 |
"7\n" |
|
| 42 |
"8\n" |
|
| 43 |
"9\n" |
|
| 44 |
"@arcs\n" |
|
| 45 |
" label capacity\n" |
|
| 46 |
"0 1 0 20\n" |
|
| 47 |
"0 2 1 0\n" |
|
| 48 |
"1 1 2 3\n" |
|
| 49 |
"1 2 3 8\n" |
|
| 50 |
"1 3 4 8\n" |
|
| 51 |
"2 5 5 5\n" |
|
| 52 |
"3 2 6 5\n" |
|
| 53 |
"3 5 7 5\n" |
|
| 54 |
"3 6 8 5\n" |
|
| 55 |
"4 3 9 3\n" |
|
| 56 |
"5 7 10 3\n" |
|
| 57 |
"5 6 11 10\n" |
|
| 58 |
"5 8 12 10\n" |
|
| 59 |
"6 8 13 8\n" |
|
| 60 |
"8 9 14 20\n" |
|
| 61 |
"8 1 15 5\n" |
|
| 62 |
"9 5 16 5\n" |
|
| 63 |
"@attributes\n" |
|
| 64 |
"source 1\n" |
|
| 65 |
"target 8\n"; |
|
| 66 |
|
|
| 32 | 67 |
void checkPreflowCompile() |
| 33 | 68 |
{
|
| 34 | 69 |
typedef int VType; |
| 35 | 70 |
typedef concepts::Digraph Digraph; |
| 36 | 71 |
|
| 37 | 72 |
typedef Digraph::Node Node; |
| 38 | 73 |
typedef Digraph::Arc Arc; |
| 39 | 74 |
typedef concepts::ReadMap<Arc,VType> CapMap; |
| 40 | 75 |
typedef concepts::ReadWriteMap<Arc,VType> FlowMap; |
| 41 | 76 |
typedef concepts::WriteMap<Node,bool> CutMap; |
| 42 | 77 |
|
| 43 | 78 |
typedef Elevator<Digraph, Digraph::Node> Elev; |
| ... | ... |
@@ -114,38 +149,29 @@ |
| 114 | 149 |
|
| 115 | 150 |
typedef SmartDigraph Digraph; |
| 116 | 151 |
|
| 117 | 152 |
typedef Digraph::Node Node; |
| 118 | 153 |
typedef Digraph::NodeIt NodeIt; |
| 119 | 154 |
typedef Digraph::ArcIt ArcIt; |
| 120 | 155 |
typedef Digraph::ArcMap<int> CapMap; |
| 121 | 156 |
typedef Digraph::ArcMap<int> FlowMap; |
| 122 | 157 |
typedef Digraph::NodeMap<bool> CutMap; |
| 123 | 158 |
|
| 124 | 159 |
typedef Preflow<Digraph, CapMap> PType; |
| 125 | 160 |
|
| 126 |
std::string f_name; |
|
| 127 |
if( getenv("srcdir") )
|
|
| 128 |
f_name = std::string(getenv("srcdir"));
|
|
| 129 |
else f_name = "."; |
|
| 130 |
f_name += "/test/preflow_graph.lgf"; |
|
| 131 |
|
|
| 132 |
std::ifstream file(f_name.c_str()); |
|
| 133 |
|
|
| 134 |
check(file, "Input file '" << f_name << "' not found."); |
|
| 135 |
|
|
| 136 | 161 |
Digraph g; |
| 137 | 162 |
Node s, t; |
| 138 | 163 |
CapMap cap(g); |
| 139 |
|
|
| 164 |
std::istringstream input(test_lgf); |
|
| 165 |
DigraphReader<Digraph>(g,input). |
|
| 140 | 166 |
arcMap("capacity", cap).
|
| 141 | 167 |
node("source",s).
|
| 142 | 168 |
node("target",t).
|
| 143 | 169 |
run(); |
| 144 | 170 |
|
| 145 | 171 |
PType preflow_test(g, cap, s, t); |
| 146 | 172 |
preflow_test.run(); |
| 147 | 173 |
|
| 148 | 174 |
check(checkFlow(g, preflow_test.flowMap(), cap, s, t), |
| 149 | 175 |
"The flow is not feasible."); |
| 150 | 176 |
|
| 151 | 177 |
CutMap min_cut(g); |
| ... | ... |
@@ -8,35 +8,77 @@ |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <iostream> |
| 20 |
#include <fstream> |
|
| 21 | 20 |
|
| 22 | 21 |
#include <lemon/list_graph.h> |
| 23 | 22 |
#include <lemon/lgf_reader.h> |
| 24 | 23 |
#include <lemon/path.h> |
| 25 | 24 |
#include <lemon/suurballe.h> |
| 26 | 25 |
|
| 27 | 26 |
#include "test_tools.h" |
| 28 | 27 |
|
| 29 | 28 |
using namespace lemon; |
| 30 | 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"; |
|
| 72 |
|
|
| 31 | 73 |
// Check the feasibility of the flow |
| 32 | 74 |
template <typename Digraph, typename FlowMap> |
| 33 | 75 |
bool checkFlow( const Digraph& gr, const FlowMap& flow, |
| 34 | 76 |
typename Digraph::Node s, typename Digraph::Node t, |
| 35 | 77 |
int value ) |
| 36 | 78 |
{
|
| 37 | 79 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
| 38 | 80 |
for (ArcIt e(gr); e != INVALID; ++e) |
| 39 | 81 |
if (!(flow[e] == 0 || flow[e] == 1)) return false; |
| 40 | 82 |
|
| 41 | 83 |
for (NodeIt n(gr); n != INVALID; ++n) {
|
| 42 | 84 |
int sum = 0; |
| ... | ... |
@@ -87,38 +129,30 @@ |
| 87 | 129 |
} |
| 88 | 130 |
|
| 89 | 131 |
|
| 90 | 132 |
int main() |
| 91 | 133 |
{
|
| 92 | 134 |
DIGRAPH_TYPEDEFS(ListDigraph); |
| 93 | 135 |
|
| 94 | 136 |
// Read the test digraph |
| 95 | 137 |
ListDigraph digraph; |
| 96 | 138 |
ListDigraph::ArcMap<int> length(digraph); |
| 97 | 139 |
Node source, target; |
| 98 | 140 |
|
| 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"; |
|
| 104 |
|
|
| 105 |
std::ifstream input(fname.c_str()); |
|
| 106 |
check(input, "Input file '" << fname << "' not found"); |
|
| 141 |
std::istringstream input(test_lgf); |
|
| 107 | 142 |
DigraphReader<ListDigraph>(digraph, input). |
| 108 | 143 |
arcMap("cost", length).
|
| 109 | 144 |
node("source", source).
|
| 110 | 145 |
node("target", target).
|
| 111 | 146 |
run(); |
| 112 |
input.close(); |
|
| 113 | 147 |
|
| 114 | 148 |
// Find 2 paths |
| 115 | 149 |
{
|
| 116 | 150 |
Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
| 117 | 151 |
check(suurballe.run(2) == 2, "Wrong number of paths"); |
| 118 | 152 |
check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), |
| 119 | 153 |
"The flow is not feasible"); |
| 120 | 154 |
check(suurballe.totalLength() == 510, "The flow is not optimal"); |
| 121 | 155 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
| 122 | 156 |
suurballe.potentialMap()), |
| 123 | 157 |
"Wrong potentials"); |
| 124 | 158 |
for (int i = 0; i < suurballe.pathNum(); ++i) |
| 1 |
@nodes |
|
| 2 |
label supply1 supply2 supply3 |
|
| 3 |
1 0 20 27 |
|
| 4 |
2 0 -4 0 |
|
| 5 |
3 0 0 0 |
|
| 6 |
4 0 0 0 |
|
| 7 |
5 0 9 0 |
|
| 8 |
6 0 -6 0 |
|
| 9 |
7 0 0 0 |
|
| 10 |
8 0 0 0 |
|
| 11 |
9 0 3 0 |
|
| 12 |
10 0 -2 0 |
|
| 13 |
11 0 0 0 |
|
| 14 |
12 0 -20 -27 |
|
| 15 |
|
|
| 16 |
@arcs |
|
| 17 |
cost capacity lower1 lower2 |
|
| 18 |
1 2 70 11 0 8 |
|
| 19 |
1 3 150 3 0 1 |
|
| 20 |
1 4 80 15 0 2 |
|
| 21 |
2 8 80 12 0 0 |
|
| 22 |
3 5 140 5 0 3 |
|
| 23 |
4 6 60 10 0 1 |
|
| 24 |
4 7 80 2 0 0 |
|
| 25 |
4 8 110 3 0 0 |
|
| 26 |
5 7 60 14 0 0 |
|
| 27 |
5 11 120 12 0 0 |
|
| 28 |
6 3 0 3 0 0 |
|
| 29 |
6 9 140 4 0 0 |
|
| 30 |
6 10 90 8 0 0 |
|
| 31 |
7 1 30 5 0 0 |
|
| 32 |
8 12 60 16 0 4 |
|
| 33 |
9 12 50 6 0 0 |
|
| 34 |
10 12 70 13 0 5 |
|
| 35 |
10 2 100 7 0 0 |
|
| 36 |
10 7 60 10 0 0 |
|
| 37 |
11 10 20 14 0 6 |
|
| 38 |
12 11 30 10 0 0 |
|
| 39 |
|
|
| 40 |
@attributes |
|
| 41 |
source 1 |
|
| 42 |
target 12 |
|
| 43 |
|
|
| 44 |
@end |
| 1 |
@nodes |
|
| 2 |
label |
|
| 3 |
0 |
|
| 4 |
1 |
|
| 5 |
2 |
|
| 6 |
3 |
|
| 7 |
4 |
|
| 8 |
5 |
|
| 9 |
6 |
|
| 10 |
7 |
|
| 11 |
8 |
|
| 12 |
9 |
|
| 13 |
@arcs |
|
| 14 |
label capacity |
|
| 15 |
0 1 0 20 |
|
| 16 |
0 2 1 0 |
|
| 17 |
1 1 2 3 |
|
| 18 |
1 2 3 8 |
|
| 19 |
1 3 4 8 |
|
| 20 |
2 5 5 5 |
|
| 21 |
3 2 6 5 |
|
| 22 |
3 5 7 5 |
|
| 23 |
3 6 8 5 |
|
| 24 |
4 3 9 3 |
|
| 25 |
5 7 10 3 |
|
| 26 |
5 6 11 10 |
|
| 27 |
5 8 12 10 |
|
| 28 |
6 8 13 8 |
|
| 29 |
8 9 14 20 |
|
| 30 |
8 1 15 5 |
|
| 31 |
9 5 16 5 |
|
| 32 |
@attributes |
|
| 33 |
source 1 |
|
| 34 |
target 8 |
0 comments (0 inline)