r440:88ed40ad0d4f
Thu, 01 Jan 2009 00:00:00
[Not Reviewed]
0 comments (0 inline)
!
!
!
1
1
2
2
1
1
21
21
1
1
1
1
1
1
1
1
1
1
1
1
1
1
12
12
| ... | ... |
@@ -3,5 +3,5 @@ |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| ... | ... |
@@ -86,5 +86,5 @@ |
| 86 | 86 |
coords(coords). |
| 87 | 87 |
title("Sample .eps figure").
|
| 88 |
copyright("(C) 2003-
|
|
| 88 |
copyright("(C) 2003-2009 LEMON Project").
|
|
| 89 | 89 |
run(); |
| 90 | 90 |
|
| ... | ... |
@@ -93,5 +93,5 @@ |
| 93 | 93 |
coords(coords). |
| 94 | 94 |
title("Sample .eps figure").
|
| 95 |
copyright("(C) 2003-
|
|
| 95 |
copyright("(C) 2003-2009 LEMON Project").
|
|
| 96 | 96 |
absoluteNodeSizes().absoluteArcWidths(). |
| 97 | 97 |
nodeScale(2).nodeSizes(sizes). |
| ... | ... |
@@ -106,5 +106,5 @@ |
| 106 | 106 |
graphToEps(g,"graph_to_eps_demo_out_3_arr.eps"). |
| 107 | 107 |
title("Sample .eps figure (with arrowheads)").
|
| 108 |
copyright("(C) 2003-
|
|
| 108 |
copyright("(C) 2003-2009 LEMON Project").
|
|
| 109 | 109 |
absoluteNodeSizes().absoluteArcWidths(). |
| 110 | 110 |
nodeColors(composeMap(palette,colors)). |
| ... | ... |
@@ -133,5 +133,5 @@ |
| 133 | 133 |
graphToEps(g,"graph_to_eps_demo_out_4_par.eps"). |
| 134 | 134 |
title("Sample .eps figure (parallel arcs)").
|
| 135 |
copyright("(C) 2003-
|
|
| 135 |
copyright("(C) 2003-2009 LEMON Project").
|
|
| 136 | 136 |
absoluteNodeSizes().absoluteArcWidths(). |
| 137 | 137 |
nodeShapes(shapes). |
| ... | ... |
@@ -148,5 +148,5 @@ |
| 148 | 148 |
graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps"). |
| 149 | 149 |
title("Sample .eps figure (parallel arcs and arrowheads)").
|
| 150 |
copyright("(C) 2003-
|
|
| 150 |
copyright("(C) 2003-2009 LEMON Project").
|
|
| 151 | 151 |
absoluteNodeSizes().absoluteArcWidths(). |
| 152 | 152 |
nodeScale(2).nodeSizes(sizes). |
| ... | ... |
@@ -164,5 +164,5 @@ |
| 164 | 164 |
graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps"). |
| 165 | 165 |
title("Sample .eps figure (fits to A4)").
|
| 166 |
copyright("(C) 2003-
|
|
| 166 |
copyright("(C) 2003-2009 LEMON Project").
|
|
| 167 | 167 |
scaleToA4(). |
| 168 | 168 |
absoluteNodeSizes().absoluteArcWidths(). |
| ... | ... |
@@ -194,5 +194,5 @@ |
| 194 | 194 |
scale(60). |
| 195 | 195 |
title("Sample .eps figure (Palette demo)").
|
| 196 |
copyright("(C) 2003-
|
|
| 196 |
copyright("(C) 2003-2009 LEMON Project").
|
|
| 197 | 197 |
coords(hcoords). |
| 198 | 198 |
absoluteNodeSizes().absoluteArcWidths(). |
| ... | ... |
@@ -3,5 +3,5 @@ |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| ... | ... |
@@ -72,5 +72,5 @@ |
| 72 | 72 |
\brief Auxiliary tools for implementation. |
| 73 | 73 |
|
| 74 |
This directory contains some auxiliary classes for implementing graphs, |
|
| 74 |
This directory contains some auxiliary classes for implementing graphs, |
|
| 75 | 75 |
maps and some other classes. |
| 76 | 76 |
As a user you typically don't have to deal with these files. |
| ... | ... |
@@ -8,8 +8,8 @@ |
| 8 | 8 |
|
| 9 | 9 |
lemon_libemon_la_SOURCES = \ |
| 10 |
lemon/arg_parser.cc \ |
|
| 11 |
lemon/base.cc \ |
|
| 12 |
lemon/color.cc \ |
|
| 13 |
lemon/random.cc |
|
| 10 |
lemon/arg_parser.cc \ |
|
| 11 |
lemon/base.cc \ |
|
| 12 |
lemon/color.cc \ |
|
| 13 |
lemon/random.cc |
|
| 14 | 14 |
|
| 15 | 15 |
#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS) |
| ... | ... |
@@ -18,22 +18,22 @@ |
| 18 | 18 |
lemon_HEADERS += \ |
| 19 | 19 |
lemon/adaptors.h \ |
| 20 |
|
|
| 20 |
lemon/arg_parser.h \ |
|
| 21 | 21 |
lemon/assert.h \ |
| 22 |
lemon/bfs.h \ |
|
| 23 |
lemon/bin_heap.h \ |
|
| 24 |
lemon/circulation.h \ |
|
| 25 |
lemon/color.h \ |
|
| 22 |
lemon/bfs.h \ |
|
| 23 |
lemon/bin_heap.h \ |
|
| 24 |
lemon/circulation.h \ |
|
| 25 |
lemon/color.h \ |
|
| 26 | 26 |
lemon/concept_check.h \ |
| 27 |
|
|
| 27 |
lemon/counter.h \ |
|
| 28 | 28 |
lemon/core.h \ |
| 29 |
lemon/dfs.h \ |
|
| 30 |
lemon/dijkstra.h \ |
|
| 31 |
lemon/dim2.h \ |
|
| 32 |
lemon/dimacs.h \ |
|
| 29 |
lemon/dfs.h \ |
|
| 30 |
lemon/dijkstra.h \ |
|
| 31 |
lemon/dim2.h \ |
|
| 32 |
lemon/dimacs.h \ |
|
| 33 | 33 |
lemon/elevator.h \ |
| 34 | 34 |
lemon/error.h \ |
| 35 | 35 |
lemon/full_graph.h \ |
| 36 |
lemon/graph_to_eps.h \ |
|
| 37 |
lemon/grid_graph.h \ |
|
| 36 |
lemon/graph_to_eps.h \ |
|
| 37 |
lemon/grid_graph.h \ |
|
| 38 | 38 |
lemon/hypercube_graph.h \ |
| 39 | 39 |
lemon/kruskal.h \ |
| ... | ... |
@@ -48,9 +48,9 @@ |
| 48 | 48 |
lemon/path.h \ |
| 49 | 49 |
lemon/preflow.h \ |
| 50 |
|
|
| 50 |
lemon/random.h \ |
|
| 51 | 51 |
lemon/smart_graph.h \ |
| 52 | 52 |
lemon/suurballe.h \ |
| 53 |
lemon/time_measure.h \ |
|
| 54 |
lemon/tolerance.h \ |
|
| 53 |
lemon/time_measure.h \ |
|
| 54 |
lemon/tolerance.h \ |
|
| 55 | 55 |
lemon/unionfind.h |
| 56 | 56 |
|
| ... | ... |
@@ -59,7 +59,7 @@ |
| 59 | 59 |
lemon/bits/array_map.h \ |
| 60 | 60 |
lemon/bits/base_extender.h \ |
| 61 |
|
|
| 61 |
lemon/bits/bezier.h \ |
|
| 62 | 62 |
lemon/bits/default_map.h \ |
| 63 |
|
|
| 63 |
lemon/bits/enable_if.h \ |
|
| 64 | 64 |
lemon/bits/graph_adaptor_extender.h \ |
| 65 | 65 |
lemon/bits/graph_extender.h \ |
| ... | ... |
@@ -3,5 +3,5 @@ |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| ... | ... |
@@ -335,5 +335,5 @@ |
| 335 | 335 |
typedef typename Digraph::ArcIt ArcIt; |
| 336 | 336 |
|
| 337 |
if(!comment.empty()) |
|
| 337 |
if(!comment.empty()) |
|
| 338 | 338 |
os << "c " << comment << std::endl; |
| 339 | 339 |
os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; |
| ... | ... |
@@ -3,5 +3,5 @@ |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| ... | ... |
@@ -239,5 +239,5 @@ |
| 239 | 239 |
if (reached[t]) continue; |
| 240 | 240 |
_sets.push_front(std::list<int>()); |
| 241 |
|
|
| 241 |
|
|
| 242 | 242 |
queue[qlast++] = t; |
| 243 | 243 |
reached.set(t, true); |
| ... | ... |
@@ -539,5 +539,5 @@ |
| 539 | 539 |
if (reached[t]) continue; |
| 540 | 540 |
_sets.push_front(std::list<int>()); |
| 541 |
|
|
| 541 |
|
|
| 542 | 542 |
queue[qlast++] = t; |
| 543 | 543 |
reached.set(t, true); |
| 1 |
/* -*- C++ -*- |
|
| 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
| 2 | 2 |
* |
| 3 |
* This file is a part of LEMON, a generic C++ optimization library |
|
| 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
|
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| ... | ... |
@@ -77,5 +77,5 @@ |
| 77 | 77 |
|
| 78 | 78 |
private: |
| 79 |
|
|
| 79 |
|
|
| 80 | 80 |
/// \brief Special implementation of the Dijkstra algorithm |
| 81 | 81 |
/// for finding shortest paths in the residual network. |
| ... | ... |
@@ -107,5 +107,5 @@ |
| 107 | 107 |
// The processed (i.e. permanently labeled) nodes |
| 108 | 108 |
std::vector<Node> _proc_nodes; |
| 109 |
|
|
| 109 |
|
|
| 110 | 110 |
Node _s; |
| 111 | 111 |
Node _t; |
| ... | ... |
@@ -201,5 +201,5 @@ |
| 201 | 201 |
// The length map |
| 202 | 202 |
const LengthMap &_length; |
| 203 |
|
|
| 203 |
|
|
| 204 | 204 |
// Arc map of the current flow |
| 205 | 205 |
FlowMap *_flow; |
| ... | ... |
@@ -269,5 +269,5 @@ |
| 269 | 269 |
/// This function sets the potential map. |
| 270 | 270 |
/// |
| 271 |
/// The potentials provide the dual solution of the underlying |
|
| 271 |
/// The potentials provide the dual solution of the underlying |
|
| 272 | 272 |
/// minimum cost flow problem. |
| 273 | 273 |
/// |
| ... | ... |
@@ -331,5 +331,5 @@ |
| 331 | 331 |
for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; |
| 332 | 332 |
|
| 333 |
_dijkstra = new ResidualDijkstra( _graph, *_flow, _length, |
|
| 333 |
_dijkstra = new ResidualDijkstra( _graph, *_flow, _length, |
|
| 334 | 334 |
*_potential, _pred, |
| 335 | 335 |
_source, _target ); |
| ... | ... |
@@ -371,5 +371,5 @@ |
| 371 | 371 |
return _path_num; |
| 372 | 372 |
} |
| 373 |
|
|
| 373 |
|
|
| 374 | 374 |
/// \brief Compute the paths from the flow. |
| 375 | 375 |
/// |
| ... | ... |
@@ -3,5 +3,5 @@ |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| ... | ... |
@@ -1190,5 +1190,5 @@ |
| 1190 | 1190 |
popLeft(nodes[jd].next); |
| 1191 | 1191 |
pushRight(jd, ld); |
| 1192 |
if (less(ld, nodes[jd].left) || |
|
| 1192 |
if (less(ld, nodes[jd].left) || |
|
| 1193 | 1193 |
nodes[ld].item == nodes[pd].item) {
|
| 1194 | 1194 |
nodes[jd].item = nodes[ld].item; |
| ... | ... |
@@ -4,14 +4,14 @@ |
| 4 | 4 |
noinst_HEADERS += \ |
| 5 | 5 |
test/graph_test.h \ |
| 6 |
|
|
| 6 |
test/test_tools.h |
|
| 7 | 7 |
|
| 8 | 8 |
check_PROGRAMS += \ |
| 9 | 9 |
test/bfs_test \ |
| 10 |
test/circulation_test \ |
|
| 11 |
test/counter_test \ |
|
| 10 |
test/circulation_test \ |
|
| 11 |
test/counter_test \ |
|
| 12 | 12 |
test/dfs_test \ |
| 13 | 13 |
test/digraph_test \ |
| 14 | 14 |
test/dijkstra_test \ |
| 15 |
|
|
| 15 |
test/dim_test \ |
|
| 16 | 16 |
test/error_test \ |
| 17 | 17 |
test/graph_adaptor_test \ |
| ... | ... |
@@ -22,13 +22,13 @@ |
| 22 | 22 |
test/heap_test \ |
| 23 | 23 |
test/kruskal_test \ |
| 24 |
|
|
| 24 |
test/maps_test \ |
|
| 25 | 25 |
test/max_matching_test \ |
| 26 |
test/path_test \ |
|
| 27 |
test/preflow_test \ |
|
| 28 |
test/random_test \ |
|
| 29 |
test/suurballe_test \ |
|
| 30 |
test/test_tools_fail \ |
|
| 31 |
test/test_tools_pass \ |
|
| 32 |
|
|
| 26 |
test/path_test \ |
|
| 27 |
test/preflow_test \ |
|
| 28 |
test/random_test \ |
|
| 29 |
test/suurballe_test \ |
|
| 30 |
test/test_tools_fail \ |
|
| 31 |
test/test_tools_pass \ |
|
| 32 |
test/time_measure_test \ |
|
| 33 | 33 |
test/unionfind_test |
| 34 | 34 |
| ... | ... |
@@ -3,5 +3,5 @@ |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| ... | ... |
@@ -104,5 +104,5 @@ |
| 104 | 104 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = true; |
| 105 | 105 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; |
| 106 |
|
|
| 106 |
|
|
| 107 | 107 |
checkGraphNodeList(adaptor, 3); |
| 108 | 108 |
checkGraphArcList(adaptor, 3); |
| ... | ... |
@@ -197,5 +197,5 @@ |
| 197 | 197 |
|
| 198 | 198 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = true; |
| 199 |
|
|
| 199 |
|
|
| 200 | 200 |
checkGraphNodeList(adaptor, 3); |
| 201 | 201 |
checkGraphArcList(adaptor, 3); |
| ... | ... |
@@ -269,5 +269,5 @@ |
| 269 | 269 |
|
| 270 | 270 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; |
| 271 |
|
|
| 271 |
|
|
| 272 | 272 |
checkGraphNodeList(adaptor, 3); |
| 273 | 273 |
checkGraphArcList(adaptor, 3); |
| ... | ... |
@@ -578,5 +578,5 @@ |
| 578 | 578 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; |
| 579 | 579 |
edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; |
| 580 |
|
|
| 580 |
|
|
| 581 | 581 |
checkGraphNodeList(adaptor, 4); |
| 582 | 582 |
checkGraphArcList(adaptor, 8); |
| ... | ... |
@@ -709,5 +709,5 @@ |
| 709 | 709 |
|
| 710 | 710 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; |
| 711 |
|
|
| 711 |
|
|
| 712 | 712 |
checkGraphNodeList(adaptor, 4); |
| 713 | 713 |
checkGraphArcList(adaptor, 8); |
| ... | ... |
@@ -808,5 +808,5 @@ |
| 808 | 808 |
|
| 809 | 809 |
edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; |
| 810 |
|
|
| 810 |
|
|
| 811 | 811 |
checkGraphNodeList(adaptor, 4); |
| 812 | 812 |
checkGraphArcList(adaptor, 8); |
| 1 |
/* -*- C++ -*- |
|
| 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
| 2 | 2 |
* |
| 3 |
* This file is a part of LEMON, a generic C++ optimization library |
|
| 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
|
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| ... | ... |
@@ -73,5 +73,5 @@ |
| 73 | 73 |
// Check the feasibility of the flow |
| 74 | 74 |
template <typename Digraph, typename FlowMap> |
| 75 |
bool checkFlow( const Digraph& gr, const FlowMap& flow, |
|
| 75 |
bool checkFlow( const Digraph& gr, const FlowMap& flow, |
|
| 76 | 76 |
typename Digraph::Node s, typename Digraph::Node t, |
| 77 | 77 |
int value ) |
| ... | ... |
@@ -96,5 +96,5 @@ |
| 96 | 96 |
|
| 97 | 97 |
// Check the optimalitiy of the flow |
| 98 |
template < typename Digraph, typename CostMap, |
|
| 98 |
template < typename Digraph, typename CostMap, |
|
| 99 | 99 |
typename FlowMap, typename PotentialMap > |
| 100 | 100 |
bool checkOptimality( const Digraph& gr, const CostMap& cost, |
| ... | ... |
@@ -145,5 +145,5 @@ |
| 145 | 145 |
node("target", target).
|
| 146 | 146 |
run(); |
| 147 |
|
|
| 147 |
|
|
| 148 | 148 |
// Find 2 paths |
| 149 | 149 |
{
|
| ... | ... |
@@ -153,5 +153,5 @@ |
| 153 | 153 |
"The flow is not feasible"); |
| 154 | 154 |
check(suurballe.totalLength() == 510, "The flow is not optimal"); |
| 155 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
| 155 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
| 156 | 156 |
suurballe.potentialMap()), |
| 157 | 157 |
"Wrong potentials"); |
| ... | ... |
@@ -168,5 +168,5 @@ |
| 168 | 168 |
"The flow is not feasible"); |
| 169 | 169 |
check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
| 170 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
| 170 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
| 171 | 171 |
suurballe.potentialMap()), |
| 172 | 172 |
"Wrong potentials"); |
| ... | ... |
@@ -183,5 +183,5 @@ |
| 183 | 183 |
"The flow is not feasible"); |
| 184 | 184 |
check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
| 185 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
| 185 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
| 186 | 186 |
suurballe.potentialMap()), |
| 187 | 187 |
"Wrong potentials"); |
0 comments (0 inline)