Index: .hgignore
===================================================================
--- .hgignore (revision 944)
+++ .hgignore (revision 610)
@@ -23,5 +23,4 @@
lemon/stamp-h2
doc/Doxyfile
-doc/references.dox
cmake/version.cmake
.dirstamp
Index: README
===================================================================
--- README (revision 921)
+++ README (revision 705)
@@ -18,8 +18,4 @@
Copying, distribution and modification conditions and terms.
-NEWS
-
- News and version history.
-
INSTALL
@@ -38,8 +34,4 @@
Some example programs to make you easier to get familiar with LEMON.
-scripts/
-
- Scripts that make it easier to develop LEMON.
-
test/
Index: demo/arg_parser_demo.cc
===================================================================
--- demo/arg_parser_demo.cc (revision 956)
+++ demo/arg_parser_demo.cc (revision 463)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -66,16 +66,7 @@
.other("...");
- // Throw an exception when problems occurs. The default behavior is to
- // exit(1) on these cases, but this makes Valgrind falsely warn
- // about memory leaks.
- ap.throwOnProblems();
-
// Perform the parsing process
// (in case of any error it terminates the program)
- // The try {} construct is necessary only if the ap.trowOnProblems()
- // setting is in use.
- try {
- ap.parse();
- } catch (ArgParserException &) { return 1; }
+ ap.parse();
// Check each option if it has been given and print its value
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 943)
+++ doc/CMakeLists.txt (revision 895)
@@ -21,5 +21,4 @@
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 943)
+++ doc/Makefile.am (revision 895)
@@ -28,5 +28,4 @@
connected_components.eps \
edge_biconnected_components.eps \
- matching.eps \
node_biconnected_components.eps \
planar.eps \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 956)
+++ doc/groups.dox (revision 879)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -387,5 +387,5 @@
problem of maximum flow.
-\ref Circulation is a preflow push-relabel algorithm implemented directly
+\ref Circulation is a preflow push-relabel algorithm implemented directly
for finding feasible circulations, which is a somewhat different problem,
but it is strongly related to maximum flow.
@@ -523,14 +523,7 @@
Edmond's blossom shrinking algorithm for calculating maximum weighted
perfect matching in general graphs.
-- \ref MaxFractionalMatching Push-relabel algorithm for calculating
- maximum cardinality fractional matching in general graphs.
-- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
- maximum weighted fractional matching in general graphs.
-- \ref MaxWeightedPerfectFractionalMatching
- Augmenting path algorithm for calculating maximum weighted
- perfect fractional matching in general graphs.
-
-\image html matching.png
-\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
+
+\image html bipartite_matching.png
+\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
*/
Index: c/images/matching.eps
===================================================================
--- doc/images/matching.eps (revision 943)
+++ (revision )
@@ -1,130 +1,0 @@
-%!PS-Adobe-2.0 EPSF-2.0
-%%Creator: LEMON, graphToEps()
-%%CreationDate: Sun Mar 14 09:08:34 2010
-%%BoundingBox: -353 -264 559 292
-%%EndComments
-/lb { setlinewidth setrgbcolor newpath moveto
- 4 2 roll 1 index 1 index curveto stroke } bind def
-/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
-/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
-/sq { newpath 2 index 1 index add 2 index 2 index add moveto
- 2 index 1 index sub 2 index 2 index add lineto
- 2 index 1 index sub 2 index 2 index sub lineto
- 2 index 1 index add 2 index 2 index sub lineto
- closepath pop pop pop} bind def
-/di { newpath 2 index 1 index add 2 index moveto
- 2 index 2 index 2 index add lineto
- 2 index 1 index sub 2 index lineto
- 2 index 2 index 2 index sub lineto
- closepath pop pop pop} bind def
-/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
- setrgbcolor 1.1 div sq fill
- } bind def
-/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
- setrgbcolor 1.1 div di fill
- } bind def
-/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
- newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
- lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
- 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
- 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/nmale {
- 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
- newpath 5 index 5 index moveto
- 5 index 4 index 1 mul 1.5 mul add
- 5 index 5 index 3 sqrt 1.5 mul mul add
- 1 index 1 index lineto
- 1 index 1 index 7 index sub moveto
- 1 index 1 index lineto
- exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
- stroke
- 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/arrl 1 def
-/arrw 0.3 def
-/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
-/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
- /w exch def /len exch def
- newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
- len w sub arrl sub dx dy lrl
- arrw dy dx neg lrl
- dx arrl w add mul dy w 2 div arrw add mul sub
- dy arrl w add mul dx w 2 div arrw add mul add rlineto
- dx arrl w add mul neg dy w 2 div arrw add mul sub
- dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
- arrw dy dx neg lrl
- len w sub arrl sub neg dx dy lrl
- closepath fill } bind def
-/cshow { 2 index 2 index moveto dup stringwidth pop
- neg 2 div fosi .35 mul neg rmoveto show pop pop} def
-
-gsave
-%Arcs:
-gsave
-140.321 266.249 -327.729 150.06 0 0 0 4.99223 l
-82.1207 -238.726 -245.288 -110.743 0 0 0 4.99223 l
-336.635 -229.036 533.603 13.109 0 0 0 4.99223 l
-53.8598 -45.8071 -245.288 -110.743 0 0 0 4.99223 l
--75.5617 118.579 -327.729 150.06 0 0 0 4.99223 l
--327.729 150.06 -245.288 -110.743 1 0 0 11.9813 l
-533.603 13.109 218.184 -84.2955 0 0 0 4.99223 l
-39.87 175.035 141.163 67.2575 0 0 0 4.99223 l
-53.8598 -45.8071 -75.5617 118.579 0 0 0 4.99223 l
--102.406 -141.267 82.1207 -238.726 0 0 0 4.99223 l
-399.144 166.894 533.603 13.109 1 0 0 11.9813 l
-39.87 175.035 140.321 266.249 1 0 0 11.9813 l
-399.144 166.894 140.321 266.249 0 0 0 4.99223 l
-399.144 166.894 141.163 67.2575 0 0 0 4.99223 l
-53.8598 -45.8071 204.765 -173.77 0 0 0 4.99223 l
-82.1207 -238.726 204.765 -173.77 0 0 0 4.99223 l
-258.227 61.658 399.144 166.894 0 0 0 4.99223 l
-53.8598 -45.8071 -102.406 -141.267 1 0 0 11.9813 l
-175.073 -37.4477 141.163 67.2575 0 0 0 4.99223 l
-258.227 61.658 380 0 0 0 0 4.99223 l
-34.6739 40.8267 -75.5617 118.579 1 0 0 11.9813 l
-380 0 533.603 13.109 0 0 0 4.99223 l
-175.073 -37.4477 380 0 0 0 0 4.99223 l
-218.184 -84.2955 204.765 -173.77 0 0 0 4.99223 l
-53.8598 -45.8071 34.6739 40.8267 0 0 0 4.99223 l
-167.905 -213.988 82.1207 -238.726 1 0 0 11.9813 l
-336.635 -229.036 204.765 -173.77 1 0 0 11.9813 l
-336.635 -229.036 167.905 -213.988 0 0 0 4.99223 l
-329.08 -26.3098 218.184 -84.2955 0 0 0 4.99223 l
-39.87 175.035 -75.5617 118.579 0 0 0 4.99223 l
-53.8598 -45.8071 175.073 -37.4477 0 0 0 4.99223 l
-34.6739 40.8267 141.163 67.2575 0 0 0 4.99223 l
-258.227 61.658 141.163 67.2575 1 0 0 11.9813 l
-175.073 -37.4477 218.184 -84.2955 1 0 0 11.9813 l
-380 0 329.08 -26.3098 1 0 0 11.9813 l
-grestore
-%Nodes:
-gsave
--245.288 -110.743 14.9767 1 1 1 nc
-204.765 -173.77 14.9767 1 1 1 nc
--327.729 150.06 14.9767 1 1 1 nc
--75.5617 118.579 14.9767 1 1 1 nc
-218.184 -84.2955 14.9767 1 1 1 nc
-140.321 266.249 14.9767 1 1 1 nc
-141.163 67.2575 14.9767 1 1 1 nc
-82.1207 -238.726 14.9767 1 1 1 nc
-329.08 -26.3098 14.9767 1 1 1 nc
--102.406 -141.267 14.9767 1 1 1 nc
-533.603 13.109 14.9767 1 1 1 nc
-167.905 -213.988 14.9767 1 1 1 nc
-336.635 -229.036 14.9767 1 1 1 nc
-380 0 14.9767 1 1 1 nc
-399.144 166.894 14.9767 1 1 1 nc
-34.6739 40.8267 14.9767 1 1 1 nc
-39.87 175.035 14.9767 1 1 1 nc
-175.073 -37.4477 14.9767 1 1 1 nc
-53.8598 -45.8071 14.9767 1 1 1 nc
-258.227 61.658 14.9767 1 1 1 nc
-grestore
-grestore
-showpage
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox (revision 956)
+++ doc/mainpage.dox (revision 802)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -24,7 +24,7 @@
LEMON stands for Library for Efficient Modeling
and Optimization in Networks.
-It is a C++ template library providing efficient implementations of common
+It is a C++ template library providing efficient implementation of common
data structures and algorithms with focus on combinatorial optimization
-tasks connected mainly with graphs and networks.
+problems in graphs and networks.
@@ -36,10 +36,10 @@
-The project is maintained by the
+The project is maintained by the
Egerváry Research Group on
Combinatorial Optimization \ref egres
at the Operations Research Department of the
-Eötvös Loránd University,
-Budapest, Hungary.
+Eötvös Loránd University,
+Budapest, Hungary.
LEMON is also a member of the COIN-OR
initiative \ref coinor.
@@ -50,8 +50,4 @@
LEMON Tutorial.
-If you are interested in starting to use the library, see the Installation
-Guide.
-
If you know what you are looking for, then try to find it under the
Modules section.
Index: doc/min_cost_flow.dox
===================================================================
--- doc/min_cost_flow.dox (revision 956)
+++ doc/min_cost_flow.dox (revision 835)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -82,5 +82,5 @@
- if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
then \f$\pi(u)=0\f$.
-
+
Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
@@ -120,5 +120,5 @@
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
-It means that the total demand must be less or equal to the
+It means that the total demand must be less or equal to the
total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
positive) and all the demands have to be satisfied, but there
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am (revision 953)
+++ lemon/Makefile.am (revision 888)
@@ -61,5 +61,5 @@
lemon/bfs.h \
lemon/bin_heap.h \
- lemon/binomial_heap.h \
+ lemon/binom_heap.h \
lemon/bucket_heap.h \
lemon/capacity_scaling.h \
@@ -76,5 +76,4 @@
lemon/cycle_canceling.h \
lemon/dfs.h \
- lemon/dheap.h \
lemon/dijkstra.h \
lemon/dim2.h \
@@ -85,5 +84,5 @@
lemon/euler.h \
lemon/fib_heap.h \
- lemon/fractional_matching.h \
+ lemon/fourary_heap.h \
lemon/full_graph.h \
lemon/glpk.h \
@@ -91,8 +90,9 @@
lemon/graph_to_eps.h \
lemon/grid_graph.h \
- lemon/hartmann_orlin_mmc.h \
- lemon/howard_mmc.h \
+ lemon/hartmann_orlin.h \
+ lemon/howard.h \
lemon/hypercube_graph.h \
- lemon/karp_mmc.h \
+ lemon/karp.h \
+ lemon/kary_heap.h \
lemon/kruskal.h \
lemon/hao_orlin.h \
@@ -113,5 +113,4 @@
lemon/planarity.h \
lemon/preflow.h \
- lemon/quad_heap.h \
lemon/radix_heap.h \
lemon/radix_sort.h \
Index: lemon/adaptors.h
===================================================================
--- lemon/adaptors.h (revision 956)
+++ lemon/adaptors.h (revision 834)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -422,5 +422,5 @@
Parent::initialize(digraph);
_node_filter = &node_filter;
- _arc_filter = &arc_filter;
+ _arc_filter = &arc_filter;
}
@@ -509,9 +509,9 @@
template
- class NodeMap
- : public SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
+ class NodeMap
+ : public SubMapExtender,
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
typedef SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
public:
@@ -536,7 +536,7 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
typedef SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> Parent;
@@ -583,5 +583,5 @@
Parent::initialize(digraph);
_node_filter = &node_filter;
- _arc_filter = &arc_filter;
+ _arc_filter = &arc_filter;
}
@@ -652,8 +652,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
@@ -679,5 +679,5 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
@@ -1022,8 +1022,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent;
@@ -1049,8 +1049,8 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent;
@@ -1076,8 +1076,8 @@
template
- class EdgeMap
+ class EdgeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
@@ -1118,6 +1118,6 @@
NF* _node_filter;
EF* _edge_filter;
- SubGraphBase()
- : Parent(), _node_filter(0), _edge_filter(0) { }
+ SubGraphBase()
+ : Parent(), _node_filter(0), _edge_filter(0) { }
void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
@@ -1220,8 +1220,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent;
@@ -1247,8 +1247,8 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent;
@@ -1274,9 +1274,9 @@
template
- class EdgeMap
+ class EdgeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> {
- typedef SubMapExtender,
- LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
+ typedef SubMapExtender,
+ LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
public:
@@ -1505,5 +1505,5 @@
#endif
typedef DigraphAdaptorExtender<
- SubDigraphBase >,
+ SubDigraphBase >,
true> > Parent;
@@ -1526,5 +1526,5 @@
/// Creates a subgraph for the given digraph or graph with the
/// given node filter map.
- FilterNodes(GR& graph, NF& node_filter)
+ FilterNodes(GR& graph, NF& node_filter)
: Parent(), const_true_map()
{
@@ -1564,9 +1564,9 @@
typename enable_if >::type> :
public GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
true> > {
typedef GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
true> > Parent;
@@ -1654,5 +1654,5 @@
#endif
typedef DigraphAdaptorExtender<
- SubDigraphBase >,
+ SubDigraphBase >,
AF, false> > Parent;
@@ -1762,9 +1762,9 @@
class FilterEdges :
public GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
EF, false> > {
#endif
typedef GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
EF, false> > Parent;
@@ -1791,5 +1791,5 @@
/// Creates a subgraph for the given graph with the given edge
/// filter map.
- FilterEdges(GR& graph, EF& edge_filter)
+ FilterEdges(GR& graph, EF& edge_filter)
: Parent(), const_true_map() {
Parent::initialize(graph, const_true_map, edge_filter);
@@ -1859,5 +1859,5 @@
bool _forward;
- Arc(const Edge& edge, bool forward)
+ Arc(const Edge& edge, bool forward)
: _edge(edge), _forward(forward) {}
@@ -2099,5 +2099,5 @@
ArcMapBase(const UndirectorBase& adaptor, const V& value)
- : _forward(*adaptor._digraph, value),
+ : _forward(*adaptor._digraph, value),
_backward(*adaptor._digraph, value) {}
@@ -2217,5 +2217,5 @@
typedef typename ItemSetTraits::ItemNotifier EdgeNotifier;
EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
-
+
typedef EdgeNotifier ArcNotifier;
ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
@@ -2729,5 +2729,5 @@
typename FM = CM,
typename TL = Tolerance >
- class ResidualDigraph
+ class ResidualDigraph
: public SubDigraph<
Undirector,
@@ -2786,5 +2786,5 @@
ResidualDigraph(const DGR& digraph, const CM& capacity,
FM& flow, const TL& tolerance = Tolerance())
- : Parent(), _capacity(&capacity), _flow(&flow),
+ : Parent(), _capacity(&capacity), _flow(&flow),
_graph(digraph), _node_filter(),
_forward_filter(capacity, flow, tolerance),
@@ -2868,5 +2868,5 @@
/// Constructor
- ResidualCapacity(const ResidualDigraph& adaptor)
+ ResidualCapacity(const ResidualDigraph& adaptor)
: _adaptor(&adaptor) {}
@@ -3448,5 +3448,5 @@
/// to get a node map of the split digraph.
/// Its value type is inherited from the first node map type (\c IN).
- /// \tparam IN The type of the node map for the in-nodes.
+ /// \tparam IN The type of the node map for the in-nodes.
/// \tparam OUT The type of the node map for the out-nodes.
template
Index: lemon/arg_parser.cc
===================================================================
--- lemon/arg_parser.cc (revision 956)
+++ lemon/arg_parser.cc (revision 463)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -21,21 +21,12 @@
namespace lemon {
- void ArgParser::_terminate(ArgParserException::Reason reason) const
- {
- if(_exit_on_problems)
- exit(1);
- else throw(ArgParserException(reason));
- }
-
-
void ArgParser::_showHelp(void *p)
{
(static_cast(p))->showHelp();
- (static_cast(p))->_terminate(ArgParserException::HELP);
+ exit(1);
}
ArgParser::ArgParser(int argc, const char * const *argv)
- :_argc(argc), _argv(argv), _command_name(argv[0]),
- _exit_on_problems(true) {
+ :_argc(argc), _argv(argv), _command_name(argv[0]) {
funcOption("-help","Print a short help message",_showHelp,this);
synonym("help","-help");
@@ -352,5 +343,5 @@
i!=_others_help.end();++i) showHelp(i);
for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
- _terminate(ArgParserException::HELP);
+ exit(1);
}
@@ -361,5 +352,5 @@
std::cerr << "\nType '" << _command_name <<
" --help' to obtain a short summary on the usage.\n\n";
- _terminate(ArgParserException::UNKNOWN_OPT);
+ exit(1);
}
@@ -424,5 +415,5 @@
std::cerr << "\nType '" << _command_name <<
" --help' to obtain a short summary on the usage.\n\n";
- _terminate(ArgParserException::INVALID_OPT);
+ exit(1);
}
}
Index: lemon/arg_parser.h
===================================================================
--- lemon/arg_parser.h (revision 956)
+++ lemon/arg_parser.h (revision 463)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -34,42 +34,4 @@
namespace lemon {
-
- ///Exception used by ArgParser
- class ArgParserException : public Exception {
- public:
- enum Reason {
- HELP, /// --help option was given
- UNKNOWN_OPT, /// Unknown option was given
- INVALID_OPT /// Invalid combination of options
- };
-
- private:
- Reason _reason;
-
- public:
- ///Constructor
- ArgParserException(Reason r) throw() : _reason(r) {}
- ///Virtual destructor
- virtual ~ArgParserException() throw() {}
- ///A short description of the exception
- virtual const char* what() const throw() {
- switch(_reason)
- {
- case HELP:
- return "lemon::ArgParseException: ask for help";
- break;
- case UNKNOWN_OPT:
- return "lemon::ArgParseException: unknown option";
- break;
- case INVALID_OPT:
- return "lemon::ArgParseException: invalid combination of options";
- break;
- }
- return "";
- }
- ///Return the reason for the failure
- Reason reason() const {return _reason; }
- };
-
///Command line arguments parser
@@ -155,8 +117,4 @@
void (*func)(void *),void *data);
- bool _exit_on_problems;
-
- void _terminate(ArgParserException::Reason reason) const;
-
public:
@@ -423,9 +381,4 @@
const std::vector &files() const { return _file_args; }
- ///Throw instead of exit in case of problems
- void throwOnProblems()
- {
- _exit_on_problems=false;
- }
};
}
Index: lemon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h (revision 956)
+++ lemon/bellman_ford.h (revision 958)
@@ -1,7 +1,7 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
+/* -*- C++ -*-
*
- * This file is a part of LEMON, a generic C++ optimization library.
+ * This file is a part of LEMON, a generic C++ optimization library
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -29,5 +29,4 @@
#include
#include
-#include
#include
@@ -36,6 +35,6 @@
namespace lemon {
- /// \brief Default operation traits for the BellmanFord algorithm class.
- ///
+ /// \brief Default OperationTraits for the BellmanFord algorithm class.
+ ///
/// This operation traits class defines all computational operations
/// and constants that are used in the Bellman-Ford algorithm.
@@ -43,11 +42,9 @@
/// If the numeric type does not have infinity value, then the maximum
/// value is used as extremal infinity value.
- ///
- /// \see BellmanFordToleranceOperationTraits
template <
- typename V,
+ typename V,
bool has_inf = std::numeric_limits::has_infinity>
struct BellmanFordDefaultOperationTraits {
- /// \brief Value type for the algorithm.
+ /// \e
typedef V Value;
/// \brief Gives back the zero value of the type.
@@ -87,50 +84,5 @@
}
};
-
- /// \brief Operation traits for the BellmanFord algorithm class
- /// using tolerance.
- ///
- /// This operation traits class defines all computational operations
- /// and constants that are used in the Bellman-Ford algorithm.
- /// The only difference between this implementation and
- /// \ref BellmanFordDefaultOperationTraits is that this class uses
- /// the \ref Tolerance "tolerance technique" in its \ref less()
- /// function.
- ///
- /// \tparam V The value type.
- /// \tparam eps The epsilon value for the \ref less() function.
- /// By default, it is the epsilon value used by \ref Tolerance
- /// "Tolerance".
- ///
- /// \see BellmanFordDefaultOperationTraits
-#ifdef DOXYGEN
- template
-#else
- template <
- typename V,
- V eps = Tolerance::def_epsilon>
-#endif
- struct BellmanFordToleranceOperationTraits {
- /// \brief Value type for the algorithm.
- typedef V Value;
- /// \brief Gives back the zero value of the type.
- static Value zero() {
- return static_cast(0);
- }
- /// \brief Gives back the positive infinity value of the type.
- static Value infinity() {
- return std::numeric_limits::infinity();
- }
- /// \brief Gives back the sum of the given two elements.
- static Value plus(const Value& left, const Value& right) {
- return left + right;
- }
- /// \brief Gives back \c true only if the first value is less than
- /// the second.
- static bool less(const Value& left, const Value& right) {
- return left + eps < right;
- }
- };
-
+
/// \brief Default traits class of BellmanFord class.
///
@@ -140,5 +92,5 @@
template
struct BellmanFordDefaultTraits {
- /// The type of the digraph the algorithm runs on.
+ /// The type of the digraph the algorithm runs on.
typedef GR Digraph;
@@ -156,11 +108,10 @@
/// It defines the used operations and the infinity value for the
/// given \c Value type.
- /// \see BellmanFordDefaultOperationTraits,
- /// BellmanFordToleranceOperationTraits
+ /// \see BellmanFordDefaultOperationTraits
typedef BellmanFordDefaultOperationTraits OperationTraits;
-
- /// \brief The type of the map that stores the last arcs of the
+
+ /// \brief The type of the map that stores the last arcs of the
/// shortest paths.
- ///
+ ///
/// The type of the map that stores the last
/// arcs of the shortest paths.
@@ -169,6 +120,6 @@
/// \brief Instantiates a \c PredMap.
- ///
- /// This function instantiates a \ref PredMap.
+ ///
+ /// This function instantiates a \ref PredMap.
/// \param g is the digraph to which we would like to define the
/// \ref PredMap.
@@ -185,6 +136,6 @@
/// \brief Instantiates a \c DistMap.
///
- /// This function instantiates a \ref DistMap.
- /// \param g is the digraph to which we would like to define the
+ /// This function instantiates a \ref DistMap.
+ /// \param g is the digraph to which we would like to define the
/// \ref DistMap.
static DistMap *createDistMap(const GR& g) {
@@ -193,9 +144,9 @@
};
-
+
/// \brief %BellmanFord algorithm class.
///
/// \ingroup shortest_path
- /// This class provides an efficient implementation of the Bellman-Ford
+ /// This class provides an efficient implementation of the Bellman-Ford
/// algorithm. The maximum time complexity of the algorithm is
/// O(ne).
@@ -208,5 +159,5 @@
///
/// The arc lengths are passed to the algorithm using a
- /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
+ /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
/// kind of length. The type of the length values is determined by the
/// \ref concepts::ReadMap::Value "Value" type of the length map.
@@ -238,5 +189,5 @@
///The type of the underlying digraph.
typedef typename TR::Digraph Digraph;
-
+
/// \brief The type of the arc lengths.
typedef typename TR::LengthMap::Value Value;
@@ -285,10 +236,10 @@
void create_maps() {
if(!_pred) {
- _local_pred = true;
- _pred = Traits::createPredMap(*_gr);
+ _local_pred = true;
+ _pred = Traits::createPredMap(*_gr);
}
if(!_dist) {
- _local_dist = true;
- _dist = Traits::createDistMap(*_gr);
+ _local_dist = true;
+ _dist = Traits::createDistMap(*_gr);
}
if(!_mask) {
@@ -296,7 +247,7 @@
}
}
-
+
public :
-
+
typedef BellmanFord Create;
@@ -321,9 +272,9 @@
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
- struct SetPredMap
+ struct SetPredMap
: public BellmanFord< Digraph, LengthMap, SetPredMapTraits > {
typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create;
};
-
+
template
struct SetDistMapTraits : public Traits {
@@ -342,5 +293,5 @@
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
- struct SetDistMap
+ struct SetDistMap
: public BellmanFord< Digraph, LengthMap, SetDistMapTraits > {
typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create;
@@ -351,6 +302,6 @@
typedef T OperationTraits;
};
-
- /// \brief \ref named-templ-param "Named parameter" for setting
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
/// \c OperationTraits type.
///
@@ -364,13 +315,13 @@
Create;
};
-
+
///@}
protected:
-
+
BellmanFord() {}
- public:
-
+ public:
+
/// \brief Constructor.
///
@@ -382,5 +333,5 @@
_pred(0), _local_pred(false),
_dist(0), _local_dist(false), _mask(0) {}
-
+
///Destructor.
~BellmanFord() {
@@ -409,6 +360,6 @@
BellmanFord &predMap(PredMap &map) {
if(_local_pred) {
- delete _pred;
- _local_pred=false;
+ delete _pred;
+ _local_pred=false;
}
_pred = ↦
@@ -427,6 +378,6 @@
BellmanFord &distMap(DistMap &map) {
if(_local_dist) {
- delete _dist;
- _local_dist=false;
+ delete _dist;
+ _local_dist=false;
}
_dist = ↦
@@ -446,5 +397,5 @@
/// \brief Initializes the internal data structures.
- ///
+ ///
/// Initializes the internal data structures. The optional parameter
/// is the initial distance of each node.
@@ -452,20 +403,20 @@
create_maps();
for (NodeIt it(*_gr); it != INVALID; ++it) {
- _pred->set(it, INVALID);
- _dist->set(it, value);
+ _pred->set(it, INVALID);
+ _dist->set(it, value);
}
_process.clear();
if (OperationTraits::less(value, OperationTraits::infinity())) {
- for (NodeIt it(*_gr); it != INVALID; ++it) {
- _process.push_back(it);
- _mask->set(it, true);
- }
+ for (NodeIt it(*_gr); it != INVALID; ++it) {
+ _process.push_back(it);
+ _mask->set(it, true);
+ }
} else {
- for (NodeIt it(*_gr); it != INVALID; ++it) {
- _mask->set(it, false);
- }
- }
- }
-
+ for (NodeIt it(*_gr); it != INVALID; ++it) {
+ _mask->set(it, false);
+ }
+ }
+ }
+
/// \brief Adds a new source node.
///
@@ -475,6 +426,6 @@
_dist->set(source, dst);
if (!(*_mask)[source]) {
- _process.push_back(source);
- _mask->set(source, true);
+ _process.push_back(source);
+ _mask->set(source, true);
}
}
@@ -501,24 +452,24 @@
bool processNextRound() {
for (int i = 0; i < int(_process.size()); ++i) {
- _mask->set(_process[i], false);
+ _mask->set(_process[i], false);
}
std::vector nextProcess;
std::vector values(_process.size());
for (int i = 0; i < int(_process.size()); ++i) {
- values[i] = (*_dist)[_process[i]];
+ values[i] = (*_dist)[_process[i]];
}
for (int i = 0; i < int(_process.size()); ++i) {
- for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
- Node target = _gr->target(it);
- Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
- if (OperationTraits::less(relaxed, (*_dist)[target])) {
- _pred->set(target, it);
- _dist->set(target, relaxed);
- if (!(*_mask)[target]) {
- _mask->set(target, true);
- nextProcess.push_back(target);
- }
- }
- }
+ for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+ Node target = _gr->target(it);
+ Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
+ if (OperationTraits::less(relaxed, (*_dist)[target])) {
+ _pred->set(target, it);
+ _dist->set(target, relaxed);
+ if (!(*_mask)[target]) {
+ _mask->set(target, true);
+ nextProcess.push_back(target);
+ }
+ }
+ }
}
_process.swap(nextProcess);
@@ -542,21 +493,21 @@
bool processNextWeakRound() {
for (int i = 0; i < int(_process.size()); ++i) {
- _mask->set(_process[i], false);
+ _mask->set(_process[i], false);
}
std::vector nextProcess;
for (int i = 0; i < int(_process.size()); ++i) {
- for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
- Node target = _gr->target(it);
- Value relaxed =
- OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
- if (OperationTraits::less(relaxed, (*_dist)[target])) {
- _pred->set(target, it);
- _dist->set(target, relaxed);
- if (!(*_mask)[target]) {
- _mask->set(target, true);
- nextProcess.push_back(target);
- }
- }
- }
+ for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+ Node target = _gr->target(it);
+ Value relaxed =
+ OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
+ if (OperationTraits::less(relaxed, (*_dist)[target])) {
+ _pred->set(target, it);
+ _dist->set(target, relaxed);
+ if (!(*_mask)[target]) {
+ _mask->set(target, true);
+ nextProcess.push_back(target);
+ }
+ }
+ }
}
_process.swap(nextProcess);
@@ -580,5 +531,5 @@
int num = countNodes(*_gr) - 1;
for (int i = 0; i < num; ++i) {
- if (processNextWeakRound()) break;
+ if (processNextWeakRound()) break;
}
}
@@ -592,16 +543,16 @@
/// if the digraph contains cycles with negative total length.
///
- /// The algorithm computes
+ /// The algorithm computes
/// - the shortest path tree (forest),
/// - the distance of each node from the root(s).
- ///
+ ///
/// \return \c false if there is a negative cycle in the digraph.
///
/// \pre init() must be called and at least one root node should be
- /// added with addSource() before using this function.
+ /// added with addSource() before using this function.
bool checkedStart() {
int num = countNodes(*_gr);
for (int i = 0; i < num; ++i) {
- if (processNextWeakRound()) return true;
+ if (processNextWeakRound()) return true;
}
return _process.empty();
@@ -627,13 +578,13 @@
///
/// \pre init() must be called and at least one root node should be
- /// added with addSource() before using this function.
+ /// added with addSource() before using this function.
void limitedStart(int num) {
for (int i = 0; i < num; ++i) {
- if (processNextRound()) break;
- }
- }
-
+ if (processNextRound()) break;
+ }
+ }
+
/// \brief Runs the algorithm from the given root node.
- ///
+ ///
/// This method runs the Bellman-Ford algorithm from the given root
/// node \c s in order to compute the shortest path to each node.
@@ -654,8 +605,8 @@
start();
}
-
+
/// \brief Runs the algorithm from the given root node with arc
/// number limit.
- ///
+ ///
/// This method runs the Bellman-Ford algorithm from the given root
/// node \c s in order to compute the shortest path distance for each
@@ -683,5 +634,5 @@
limitedStart(num);
}
-
+
///@}
@@ -698,5 +649,5 @@
///
/// Constructor for getting the active nodes of the given BellmanFord
- /// instance.
+ /// instance.
ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
{
@@ -712,5 +663,5 @@
///
/// Conversion to \c Node.
- operator Node() const {
+ operator Node() const {
return _index >= 0 ? _algorithm->_process[_index] : INVALID;
}
@@ -721,31 +672,31 @@
ActiveIt& operator++() {
--_index;
- return *this;
- }
-
- bool operator==(const ActiveIt& it) const {
- return static_cast(*this) == static_cast(it);
- }
- bool operator!=(const ActiveIt& it) const {
- return static_cast(*this) != static_cast(it);
- }
- bool operator<(const ActiveIt& it) const {
- return static_cast(*this) < static_cast(it);
- }
-
+ return *this;
+ }
+
+ bool operator==(const ActiveIt& it) const {
+ return static_cast(*this) == static_cast(it);
+ }
+ bool operator!=(const ActiveIt& it) const {
+ return static_cast(*this) != static_cast(it);
+ }
+ bool operator<(const ActiveIt& it) const {
+ return static_cast(*this) < static_cast(it);
+ }
+
private:
const BellmanFord* _algorithm;
int _index;
};
-
+
/// \name Query Functions
/// The result of the Bellman-Ford algorithm can be obtained using these
/// functions.\n
/// Either \ref run() or \ref init() should be called before using them.
-
+
///@{
/// \brief The shortest path to the given node.
- ///
+ ///
/// Gives back the shortest path to the given node from the root(s).
///
@@ -758,5 +709,5 @@
return Path(*_gr, *_pred, t);
}
-
+
/// \brief The distance of the given node from the root(s).
///
@@ -798,8 +749,8 @@
/// \pre Either \ref run() or \ref init() must be called before
/// using this function.
- Node predNode(Node v) const {
- return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
- }
-
+ Node predNode(Node v) const {
+ return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
+ }
+
/// \brief Returns a const reference to the node map that stores the
/// distances of the nodes.
@@ -811,5 +762,5 @@
/// using this function.
const DistMap &distMap() const { return *_dist;}
-
+
/// \brief Returns a const reference to the node map that stores the
/// predecessor arcs.
@@ -821,5 +772,5 @@
/// using this function.
const PredMap &predMap() const { return *_pred; }
-
+
/// \brief Checks if a node is reached from the root(s).
///
@@ -833,5 +784,5 @@
/// \brief Gives back a negative cycle.
- ///
+ ///
/// This function gives back a directed cycle with negative total
/// length if the algorithm has already found one.
@@ -860,8 +811,8 @@
return cycle;
}
-
+
///@}
};
-
+
/// \brief Default traits class of bellmanFord() function.
///
@@ -871,5 +822,5 @@
template
struct BellmanFordWizardDefaultTraits {
- /// The type of the digraph the algorithm runs on.
+ /// The type of the digraph the algorithm runs on.
typedef GR Digraph;
@@ -887,11 +838,10 @@
/// It defines the used operations and the infinity value for the
/// given \c Value type.
- /// \see BellmanFordDefaultOperationTraits,
- /// BellmanFordToleranceOperationTraits
+ /// \see BellmanFordDefaultOperationTraits
typedef BellmanFordDefaultOperationTraits OperationTraits;
/// \brief The type of the map that stores the last
/// arcs of the shortest paths.
- ///
+ ///
/// The type of the map that stores the last arcs of the shortest paths.
/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
@@ -899,5 +849,5 @@
/// \brief Instantiates a \c PredMap.
- ///
+ ///
/// This function instantiates a \ref PredMap.
/// \param g is the digraph to which we would like to define the
@@ -915,5 +865,5 @@
/// \brief Instantiates a \c DistMap.
///
- /// This function instantiates a \ref DistMap.
+ /// This function instantiates a \ref DistMap.
/// \param g is the digraph to which we would like to define the
/// \ref DistMap.
@@ -928,5 +878,5 @@
typedef lemon::Path Path;
};
-
+
/// \brief Default traits class used by BellmanFordWizard.
///
@@ -935,5 +885,5 @@
/// \tparam LEN The type of the length map.
template
- class BellmanFordWizardBase
+ class BellmanFordWizardBase
: public BellmanFordWizardDefaultTraits {
@@ -958,5 +908,5 @@
public:
/// Constructor.
-
+
/// This constructor does not require parameters, it initiates
/// all of the attributes to default values \c 0.
@@ -965,17 +915,17 @@
/// Constructor.
-
+
/// This constructor requires two parameters,
/// others are initiated to \c 0.
/// \param gr The digraph the algorithm runs on.
/// \param len The length map.
- BellmanFordWizardBase(const GR& gr,
- const LEN& len) :
- _graph(reinterpret_cast(const_cast(&gr))),
- _length(reinterpret_cast(const_cast(&len))),
+ BellmanFordWizardBase(const GR& gr,
+ const LEN& len) :
+ _graph(reinterpret_cast(const_cast(&gr))),
+ _length(reinterpret_cast(const_cast(&len))),
_pred(0), _dist(0), _path(0), _di(0) {}
};
-
+
/// \brief Auxiliary class for the function-type interface of the
/// \ref BellmanFord "Bellman-Ford" algorithm.
@@ -1002,5 +952,5 @@
typedef typename Digraph::Arc Arc;
typedef typename Digraph::OutArcIt ArcIt;
-
+
typedef typename TR::LengthMap LengthMap;
typedef typename LengthMap::Value Value;
@@ -1019,5 +969,5 @@
/// \param gr The digraph the algorithm runs on.
/// \param len The length map.
- BellmanFordWizard(const Digraph& gr, const LengthMap& len)
+ BellmanFordWizard(const Digraph& gr, const LengthMap& len)
: TR(gr, len) {}
@@ -1028,10 +978,10 @@
/// \brief Runs the Bellman-Ford algorithm from the given source node.
- ///
+ ///
/// This method runs the Bellman-Ford algorithm from the given source
/// node in order to compute the shortest path to each node.
void run(Node s) {
- BellmanFord
- bf(*reinterpret_cast(Base::_graph),
+ BellmanFord
+ bf(*reinterpret_cast(Base::_graph),
*reinterpret_cast(Base::_length));
if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred));
@@ -1068,5 +1018,5 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
-
+
/// \brief \ref named-templ-param "Named parameter" for setting
/// the predecessor map.
@@ -1079,5 +1029,5 @@
return BellmanFordWizard >(*this);
}
-
+
template
struct SetDistMapBase : public Base {
@@ -1086,5 +1036,5 @@
SetDistMapBase(const TR &b) : TR(b) {}
};
-
+
/// \brief \ref named-templ-param "Named parameter" for setting
/// the distance map.
@@ -1127,7 +1077,7 @@
return *this;
}
-
+
};
-
+
/// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
/// algorithm.
@@ -1137,6 +1087,6 @@
/// algorithm.
///
- /// This function also has several \ref named-templ-func-param
- /// "named parameters", they are declared as the members of class
+ /// This function also has several \ref named-templ-func-param
+ /// "named parameters", they are declared as the members of class
/// \ref BellmanFordWizard.
/// The following examples show how to use these parameters.
@@ -1155,5 +1105,5 @@
BellmanFordWizard >
bellmanFord(const GR& digraph,
- const LEN& length)
+ const LEN& length)
{
return BellmanFordWizard >(digraph, length);
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 956)
+++ lemon/bfs.h (revision 891)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -83,6 +83,5 @@
///The type of the map that indicates which nodes are reached.
- ///It must conform to
- ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a \c ReachedMap.
@@ -273,6 +272,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c ReachedMap type.
- ///It must conform to
- ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
template
struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > {
@@ -875,6 +873,5 @@
///The type of the map that indicates which nodes are reached.
- ///It must conform to
- ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a ReachedMap.
@@ -1269,6 +1266,5 @@
///
/// The type of the map that indicates which nodes are reached.
- /// It must conform to
- ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
Index: lemon/binom_heap.h
===================================================================
--- lemon/binom_heap.h (revision 754)
+++ lemon/binom_heap.h (revision 754)
@@ -0,0 +1,445 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_BINOM_HEAP_H
+#define LEMON_BINOM_HEAP_H
+
+///\file
+///\ingroup heaps
+///\brief Binomial Heap implementation.
+
+#include
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \ingroup heaps
+ ///
+ ///\brief Binomial heap data structure.
+ ///
+ /// This class implements the \e binomial \e heap data structure.
+ /// It fully conforms to the \ref concepts::Heap "heap concept".
+ ///
+ /// The methods \ref increase() and \ref erase() are not efficient
+ /// in a binomial heap. In case of many calls of these operations,
+ /// it is better to use other heap structure, e.g. \ref BinHeap
+ /// "binary heap".
+ ///
+ /// \tparam PR Type of the priorities of the items.
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam CMP A functor class for comparing the priorities.
+ /// The default is \c std::less.
+#ifdef DOXYGEN
+ template
+#else
+ template >
+#endif
+ class BinomHeap {
+ public:
+ /// Type of the item-int map.
+ typedef IM ItemIntMap;
+ /// Type of the priorities.
+ typedef PR Prio;
+ /// Type of the items stored in the heap.
+ typedef typename ItemIntMap::Key Item;
+ /// Functor type for comparing the priorities.
+ typedef CMP Compare;
+
+ /// \brief Type to represent the states of the items.
+ ///
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
+ /// heap's point of view, but may be useful to the user.
+ ///
+ /// The item-int map must be initialized in such way that it assigns
+ /// \c PRE_HEAP (-1) to any element to be put in the heap.
+ enum State {
+ IN_HEAP = 0, ///< = 0.
+ PRE_HEAP = -1, ///< = -1.
+ POST_HEAP = -2 ///< = -2.
+ };
+
+ private:
+ class Store;
+
+ std::vector _data;
+ int _min, _head;
+ ItemIntMap &_iim;
+ Compare _comp;
+ int _num_items;
+
+ public:
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (-1) for each item.
+ explicit BinomHeap(ItemIntMap &map)
+ : _min(0), _head(-1), _iim(map), _num_items(0) {}
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (-1) for each item.
+ /// \param comp The function object used for comparing the priorities.
+ BinomHeap(ItemIntMap &map, const Compare &comp)
+ : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
+
+ /// \brief The number of items stored in the heap.
+ ///
+ /// This function returns the number of items stored in the heap.
+ int size() const { return _num_items; }
+
+ /// \brief Check if the heap is empty.
+ ///
+ /// This function returns \c true if the heap is empty.
+ bool empty() const { return _num_items==0; }
+
+ /// \brief Make the heap empty.
+ ///
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
+ void clear() {
+ _data.clear(); _min=0; _num_items=0; _head=-1;
+ }
+
+ /// \brief Set the priority of an item or insert it, if it is
+ /// not stored in the heap.
+ ///
+ /// This method sets the priority of the given item if it is
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
+ /// \param item The item.
+ /// \param value The priority.
+ void set (const Item& item, const Prio& value) {
+ int i=_iim[item];
+ if ( i >= 0 && _data[i].in ) {
+ if ( _comp(value, _data[i].prio) ) decrease(item, value);
+ if ( _comp(_data[i].prio, value) ) increase(item, value);
+ } else push(item, value);
+ }
+
+ /// \brief Insert an item into the heap with the given priority.
+ ///
+ /// This function inserts the given item into the heap with the
+ /// given priority.
+ /// \param item The item to insert.
+ /// \param value The priority of the item.
+ /// \pre \e item must not be stored in the heap.
+ void push (const Item& item, const Prio& value) {
+ int i=_iim[item];
+ if ( i<0 ) {
+ int s=_data.size();
+ _iim.set( item,s );
+ Store st;
+ st.name=item;
+ st.prio=value;
+ _data.push_back(st);
+ i=s;
+ }
+ else {
+ _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
+ _data[i].degree=0;
+ _data[i].in=true;
+ _data[i].prio=value;
+ }
+
+ if( 0==_num_items ) {
+ _head=i;
+ _min=i;
+ } else {
+ merge(i);
+ if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
+ }
+ ++_num_items;
+ }
+
+ /// \brief Return the item having minimum priority.
+ ///
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
+ Item top() const { return _data[_min].name; }
+
+ /// \brief The minimum priority.
+ ///
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
+ Prio prio() const { return _data[_min].prio; }
+
+ /// \brief The priority of the given item.
+ ///
+ /// This function returns the priority of the given item.
+ /// \param item The item.
+ /// \pre \e item must be in the heap.
+ const Prio& operator[](const Item& item) const {
+ return _data[_iim[item]].prio;
+ }
+
+ /// \brief Remove the item having minimum priority.
+ ///
+ /// This function removes the item having minimum priority.
+ /// \pre The heap must be non-empty.
+ void pop() {
+ _data[_min].in=false;
+
+ int head_child=-1;
+ if ( _data[_min].child!=-1 ) {
+ int child=_data[_min].child;
+ int neighb;
+ while( child!=-1 ) {
+ neighb=_data[child].right_neighbor;
+ _data[child].parent=-1;
+ _data[child].right_neighbor=head_child;
+ head_child=child;
+ child=neighb;
+ }
+ }
+
+ if ( _data[_head].right_neighbor==-1 ) {
+ // there was only one root
+ _head=head_child;
+ }
+ else {
+ // there were more roots
+ if( _head!=_min ) { unlace(_min); }
+ else { _head=_data[_head].right_neighbor; }
+ merge(head_child);
+ }
+ _min=findMin();
+ --_num_items;
+ }
+
+ /// \brief Remove the given item from the heap.
+ ///
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param item The item to delete.
+ /// \pre \e item must be in the heap.
+ void erase (const Item& item) {
+ int i=_iim[item];
+ if ( i >= 0 && _data[i].in ) {
+ decrease( item, _data[_min].prio-1 );
+ pop();
+ }
+ }
+
+ /// \brief Decrease the priority of an item to the given value.
+ ///
+ /// This function decreases the priority of an item to the given value.
+ /// \param item The item.
+ /// \param value The priority.
+ /// \pre \e item must be stored in the heap with priority at least \e value.
+ void decrease (Item item, const Prio& value) {
+ int i=_iim[item];
+ int p=_data[i].parent;
+ _data[i].prio=value;
+
+ while( p!=-1 && _comp(value, _data[p].prio) ) {
+ _data[i].name=_data[p].name;
+ _data[i].prio=_data[p].prio;
+ _data[p].name=item;
+ _data[p].prio=value;
+ _iim[_data[i].name]=i;
+ i=p;
+ p=_data[p].parent;
+ }
+ _iim[item]=i;
+ if ( _comp(value, _data[_min].prio) ) _min=i;
+ }
+
+ /// \brief Increase the priority of an item to the given value.
+ ///
+ /// This function increases the priority of an item to the given value.
+ /// \param item The item.
+ /// \param value The priority.
+ /// \pre \e item must be stored in the heap with priority at most \e value.
+ void increase (Item item, const Prio& value) {
+ erase(item);
+ push(item, value);
+ }
+
+ /// \brief Return the state of an item.
+ ///
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
+ /// \param item The item.
+ State state(const Item &item) const {
+ int i=_iim[item];
+ if( i>=0 ) {
+ if ( _data[i].in ) i=0;
+ else i=-2;
+ }
+ return State(i);
+ }
+
+ /// \brief Set the state of an item in the heap.
+ ///
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
+ /// \param i The item.
+ /// \param st The state. It should not be \c IN_HEAP.
+ void state(const Item& i, State st) {
+ switch (st) {
+ case POST_HEAP:
+ case PRE_HEAP:
+ if (state(i) == IN_HEAP) {
+ erase(i);
+ }
+ _iim[i] = st;
+ break;
+ case IN_HEAP:
+ break;
+ }
+ }
+
+ private:
+
+ // Find the minimum of the roots
+ int findMin() {
+ if( _head!=-1 ) {
+ int min_loc=_head, min_val=_data[_head].prio;
+ for( int x=_data[_head].right_neighbor; x!=-1;
+ x=_data[x].right_neighbor ) {
+ if( _comp( _data[x].prio,min_val ) ) {
+ min_val=_data[x].prio;
+ min_loc=x;
+ }
+ }
+ return min_loc;
+ }
+ else return -1;
+ }
+
+ // Merge the heap with another heap starting at the given position
+ void merge(int a) {
+ if( _head==-1 || a==-1 ) return;
+ if( _data[a].right_neighbor==-1 &&
+ _data[a].degree<=_data[_head].degree ) {
+ _data[a].right_neighbor=_head;
+ _head=a;
+ } else {
+ interleave(a);
+ }
+ if( _data[_head].right_neighbor==-1 ) return;
+
+ int x=_head;
+ int x_prev=-1, x_next=_data[x].right_neighbor;
+ while( x_next!=-1 ) {
+ if( _data[x].degree!=_data[x_next].degree ||
+ ( _data[x_next].right_neighbor!=-1 &&
+ _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
+ x_prev=x;
+ x=x_next;
+ }
+ else {
+ if( _comp(_data[x_next].prio,_data[x].prio) ) {
+ if( x_prev==-1 ) {
+ _head=x_next;
+ } else {
+ _data[x_prev].right_neighbor=x_next;
+ }
+ fuse(x,x_next);
+ x=x_next;
+ }
+ else {
+ _data[x].right_neighbor=_data[x_next].right_neighbor;
+ fuse(x_next,x);
+ }
+ }
+ x_next=_data[x].right_neighbor;
+ }
+ }
+
+ // Interleave the elements of the given list into the list of the roots
+ void interleave(int a) {
+ int p=_head, q=a;
+ int curr=_data.size();
+ _data.push_back(Store());
+
+ while( p!=-1 || q!=-1 ) {
+ if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
+ _data[curr].right_neighbor=p;
+ curr=p;
+ p=_data[p].right_neighbor;
+ }
+ else {
+ _data[curr].right_neighbor=q;
+ curr=q;
+ q=_data[q].right_neighbor;
+ }
+ }
+
+ _head=_data.back().right_neighbor;
+ _data.pop_back();
+ }
+
+ // Lace node a under node b
+ void fuse(int a, int b) {
+ _data[a].parent=b;
+ _data[a].right_neighbor=_data[b].child;
+ _data[b].child=a;
+
+ ++_data[b].degree;
+ }
+
+ // Unlace node a (if it has siblings)
+ void unlace(int a) {
+ int neighb=_data[a].right_neighbor;
+ int other=_head;
+
+ while( _data[other].right_neighbor!=a )
+ other=_data[other].right_neighbor;
+ _data[other].right_neighbor=neighb;
+ }
+
+ private:
+
+ class Store {
+ friend class BinomHeap;
+
+ Item name;
+ int parent;
+ int right_neighbor;
+ int child;
+ int degree;
+ bool in;
+ Prio prio;
+
+ Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
+ in(true) {}
+ };
+ };
+
+} //namespace lemon
+
+#endif //LEMON_BINOM_HEAP_H
+
Index: mon/binomial_heap.h
===================================================================
--- lemon/binomial_heap.h (revision 956)
+++ (revision )
@@ -1,445 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2010
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_BINOMIAL_HEAP_H
-#define LEMON_BINOMIAL_HEAP_H
-
-///\file
-///\ingroup heaps
-///\brief Binomial Heap implementation.
-
-#include
-#include
-#include
-#include
-#include
-
-namespace lemon {
-
- /// \ingroup heaps
- ///
- ///\brief Binomial heap data structure.
- ///
- /// This class implements the \e binomial \e heap data structure.
- /// It fully conforms to the \ref concepts::Heap "heap concept".
- ///
- /// The methods \ref increase() and \ref erase() are not efficient
- /// in a binomial heap. In case of many calls of these operations,
- /// it is better to use other heap structure, e.g. \ref BinHeap
- /// "binary heap".
- ///
- /// \tparam PR Type of the priorities of the items.
- /// \tparam IM A read-writable item map with \c int values, used
- /// internally to handle the cross references.
- /// \tparam CMP A functor class for comparing the priorities.
- /// The default is \c std::less.
-#ifdef DOXYGEN
- template
-#else
- template >
-#endif
- class BinomialHeap {
- public:
- /// Type of the item-int map.
- typedef IM ItemIntMap;
- /// Type of the priorities.
- typedef PR Prio;
- /// Type of the items stored in the heap.
- typedef typename ItemIntMap::Key Item;
- /// Functor type for comparing the priorities.
- typedef CMP Compare;
-
- /// \brief Type to represent the states of the items.
- ///
- /// Each item has a state associated to it. It can be "in heap",
- /// "pre-heap" or "post-heap". The latter two are indifferent from the
- /// heap's point of view, but may be useful to the user.
- ///
- /// The item-int map must be initialized in such way that it assigns
- /// \c PRE_HEAP (-1) to any element to be put in the heap.
- enum State {
- IN_HEAP = 0, ///< = 0.
- PRE_HEAP = -1, ///< = -1.
- POST_HEAP = -2 ///< = -2.
- };
-
- private:
- class Store;
-
- std::vector _data;
- int _min, _head;
- ItemIntMap &_iim;
- Compare _comp;
- int _num_items;
-
- public:
- /// \brief Constructor.
- ///
- /// Constructor.
- /// \param map A map that assigns \c int values to the items.
- /// It is used internally to handle the cross references.
- /// The assigned value must be \c PRE_HEAP (-1) for each item.
- explicit BinomialHeap(ItemIntMap &map)
- : _min(0), _head(-1), _iim(map), _num_items(0) {}
-
- /// \brief Constructor.
- ///
- /// Constructor.
- /// \param map A map that assigns \c int values to the items.
- /// It is used internally to handle the cross references.
- /// The assigned value must be \c PRE_HEAP (-1) for each item.
- /// \param comp The function object used for comparing the priorities.
- BinomialHeap(ItemIntMap &map, const Compare &comp)
- : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
-
- /// \brief The number of items stored in the heap.
- ///
- /// This function returns the number of items stored in the heap.
- int size() const { return _num_items; }
-
- /// \brief Check if the heap is empty.
- ///
- /// This function returns \c true if the heap is empty.
- bool empty() const { return _num_items==0; }
-
- /// \brief Make the heap empty.
- ///
- /// This functon makes the heap empty.
- /// It does not change the cross reference map. If you want to reuse
- /// a heap that is not surely empty, you should first clear it and
- /// then you should set the cross reference map to \c PRE_HEAP
- /// for each item.
- void clear() {
- _data.clear(); _min=0; _num_items=0; _head=-1;
- }
-
- /// \brief Set the priority of an item or insert it, if it is
- /// not stored in the heap.
- ///
- /// This method sets the priority of the given item if it is
- /// already stored in the heap. Otherwise it inserts the given
- /// item into the heap with the given priority.
- /// \param item The item.
- /// \param value The priority.
- void set (const Item& item, const Prio& value) {
- int i=_iim[item];
- if ( i >= 0 && _data[i].in ) {
- if ( _comp(value, _data[i].prio) ) decrease(item, value);
- if ( _comp(_data[i].prio, value) ) increase(item, value);
- } else push(item, value);
- }
-
- /// \brief Insert an item into the heap with the given priority.
- ///
- /// This function inserts the given item into the heap with the
- /// given priority.
- /// \param item The item to insert.
- /// \param value The priority of the item.
- /// \pre \e item must not be stored in the heap.
- void push (const Item& item, const Prio& value) {
- int i=_iim[item];
- if ( i<0 ) {
- int s=_data.size();
- _iim.set( item,s );
- Store st;
- st.name=item;
- st.prio=value;
- _data.push_back(st);
- i=s;
- }
- else {
- _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
- _data[i].degree=0;
- _data[i].in=true;
- _data[i].prio=value;
- }
-
- if( 0==_num_items ) {
- _head=i;
- _min=i;
- } else {
- merge(i);
- if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
- }
- ++_num_items;
- }
-
- /// \brief Return the item having minimum priority.
- ///
- /// This function returns the item having minimum priority.
- /// \pre The heap must be non-empty.
- Item top() const { return _data[_min].name; }
-
- /// \brief The minimum priority.
- ///
- /// This function returns the minimum priority.
- /// \pre The heap must be non-empty.
- Prio prio() const { return _data[_min].prio; }
-
- /// \brief The priority of the given item.
- ///
- /// This function returns the priority of the given item.
- /// \param item The item.
- /// \pre \e item must be in the heap.
- const Prio& operator[](const Item& item) const {
- return _data[_iim[item]].prio;
- }
-
- /// \brief Remove the item having minimum priority.
- ///
- /// This function removes the item having minimum priority.
- /// \pre The heap must be non-empty.
- void pop() {
- _data[_min].in=false;
-
- int head_child=-1;
- if ( _data[_min].child!=-1 ) {
- int child=_data[_min].child;
- int neighb;
- while( child!=-1 ) {
- neighb=_data[child].right_neighbor;
- _data[child].parent=-1;
- _data[child].right_neighbor=head_child;
- head_child=child;
- child=neighb;
- }
- }
-
- if ( _data[_head].right_neighbor==-1 ) {
- // there was only one root
- _head=head_child;
- }
- else {
- // there were more roots
- if( _head!=_min ) { unlace(_min); }
- else { _head=_data[_head].right_neighbor; }
- merge(head_child);
- }
- _min=findMin();
- --_num_items;
- }
-
- /// \brief Remove the given item from the heap.
- ///
- /// This function removes the given item from the heap if it is
- /// already stored.
- /// \param item The item to delete.
- /// \pre \e item must be in the heap.
- void erase (const Item& item) {
- int i=_iim[item];
- if ( i >= 0 && _data[i].in ) {
- decrease( item, _data[_min].prio-1 );
- pop();
- }
- }
-
- /// \brief Decrease the priority of an item to the given value.
- ///
- /// This function decreases the priority of an item to the given value.
- /// \param item The item.
- /// \param value The priority.
- /// \pre \e item must be stored in the heap with priority at least \e value.
- void decrease (Item item, const Prio& value) {
- int i=_iim[item];
- int p=_data[i].parent;
- _data[i].prio=value;
-
- while( p!=-1 && _comp(value, _data[p].prio) ) {
- _data[i].name=_data[p].name;
- _data[i].prio=_data[p].prio;
- _data[p].name=item;
- _data[p].prio=value;
- _iim[_data[i].name]=i;
- i=p;
- p=_data[p].parent;
- }
- _iim[item]=i;
- if ( _comp(value, _data[_min].prio) ) _min=i;
- }
-
- /// \brief Increase the priority of an item to the given value.
- ///
- /// This function increases the priority of an item to the given value.
- /// \param item The item.
- /// \param value The priority.
- /// \pre \e item must be stored in the heap with priority at most \e value.
- void increase (Item item, const Prio& value) {
- erase(item);
- push(item, value);
- }
-
- /// \brief Return the state of an item.
- ///
- /// This method returns \c PRE_HEAP if the given item has never
- /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
- /// and \c POST_HEAP otherwise.
- /// In the latter case it is possible that the item will get back
- /// to the heap again.
- /// \param item The item.
- State state(const Item &item) const {
- int i=_iim[item];
- if( i>=0 ) {
- if ( _data[i].in ) i=0;
- else i=-2;
- }
- return State(i);
- }
-
- /// \brief Set the state of an item in the heap.
- ///
- /// This function sets the state of the given item in the heap.
- /// It can be used to manually clear the heap when it is important
- /// to achive better time complexity.
- /// \param i The item.
- /// \param st The state. It should not be \c IN_HEAP.
- void state(const Item& i, State st) {
- switch (st) {
- case POST_HEAP:
- case PRE_HEAP:
- if (state(i) == IN_HEAP) {
- erase(i);
- }
- _iim[i] = st;
- break;
- case IN_HEAP:
- break;
- }
- }
-
- private:
-
- // Find the minimum of the roots
- int findMin() {
- if( _head!=-1 ) {
- int min_loc=_head, min_val=_data[_head].prio;
- for( int x=_data[_head].right_neighbor; x!=-1;
- x=_data[x].right_neighbor ) {
- if( _comp( _data[x].prio,min_val ) ) {
- min_val=_data[x].prio;
- min_loc=x;
- }
- }
- return min_loc;
- }
- else return -1;
- }
-
- // Merge the heap with another heap starting at the given position
- void merge(int a) {
- if( _head==-1 || a==-1 ) return;
- if( _data[a].right_neighbor==-1 &&
- _data[a].degree<=_data[_head].degree ) {
- _data[a].right_neighbor=_head;
- _head=a;
- } else {
- interleave(a);
- }
- if( _data[_head].right_neighbor==-1 ) return;
-
- int x=_head;
- int x_prev=-1, x_next=_data[x].right_neighbor;
- while( x_next!=-1 ) {
- if( _data[x].degree!=_data[x_next].degree ||
- ( _data[x_next].right_neighbor!=-1 &&
- _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
- x_prev=x;
- x=x_next;
- }
- else {
- if( _comp(_data[x_next].prio,_data[x].prio) ) {
- if( x_prev==-1 ) {
- _head=x_next;
- } else {
- _data[x_prev].right_neighbor=x_next;
- }
- fuse(x,x_next);
- x=x_next;
- }
- else {
- _data[x].right_neighbor=_data[x_next].right_neighbor;
- fuse(x_next,x);
- }
- }
- x_next=_data[x].right_neighbor;
- }
- }
-
- // Interleave the elements of the given list into the list of the roots
- void interleave(int a) {
- int p=_head, q=a;
- int curr=_data.size();
- _data.push_back(Store());
-
- while( p!=-1 || q!=-1 ) {
- if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
- _data[curr].right_neighbor=p;
- curr=p;
- p=_data[p].right_neighbor;
- }
- else {
- _data[curr].right_neighbor=q;
- curr=q;
- q=_data[q].right_neighbor;
- }
- }
-
- _head=_data.back().right_neighbor;
- _data.pop_back();
- }
-
- // Lace node a under node b
- void fuse(int a, int b) {
- _data[a].parent=b;
- _data[a].right_neighbor=_data[b].child;
- _data[b].child=a;
-
- ++_data[b].degree;
- }
-
- // Unlace node a (if it has siblings)
- void unlace(int a) {
- int neighb=_data[a].right_neighbor;
- int other=_head;
-
- while( _data[other].right_neighbor!=a )
- other=_data[other].right_neighbor;
- _data[other].right_neighbor=neighb;
- }
-
- private:
-
- class Store {
- friend class BinomialHeap;
-
- Item name;
- int parent;
- int right_neighbor;
- int child;
- int degree;
- bool in;
- Prio prio;
-
- Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
- in(true) {}
- };
- };
-
-} //namespace lemon
-
-#endif //LEMON_BINOMIAL_HEAP_H
-
Index: lemon/bits/array_map.h
===================================================================
--- lemon/bits/array_map.h (revision 956)
+++ lemon/bits/array_map.h (revision 664)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -71,5 +71,5 @@
private:
-
+
// The MapBase of the Map which imlements the core regisitry function.
typedef typename Notifier::ObserverBase Parent;
Index: lemon/bits/default_map.h
===================================================================
--- lemon/bits/default_map.h (revision 956)
+++ lemon/bits/default_map.h (revision 674)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -158,5 +158,5 @@
public:
typedef DefaultMap<_Graph, _Item, _Value> Map;
-
+
typedef typename Parent::GraphType GraphType;
typedef typename Parent::Value Value;
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h (revision 956)
+++ lemon/bits/edge_set_extender.h (revision 732)
@@ -1,7 +1,7 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
+/* -*- C++ -*-
*
- * This file is a part of LEMON, a generic C++ optimization library.
+ * This file is a part of LEMON, a generic C++ optimization library
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -64,9 +64,9 @@
Node oppositeNode(const Node &n, const Arc &e) const {
if (n == Parent::source(e))
- return Parent::target(e);
+ return Parent::target(e);
else if(n==Parent::target(e))
- return Parent::source(e);
+ return Parent::source(e);
else
- return INVALID;
+ return INVALID;
}
@@ -92,5 +92,5 @@
// Iterable extensions
- class NodeIt : public Node {
+ class NodeIt : public Node {
const Digraph* digraph;
public:
@@ -101,19 +101,19 @@
explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
- _graph.first(static_cast(*this));
- }
-
- NodeIt(const Digraph& _graph, const Node& node)
- : Node(node), digraph(&_graph) {}
-
- NodeIt& operator++() {
- digraph->next(*this);
- return *this;
- }
-
- };
-
-
- class ArcIt : public Arc {
+ _graph.first(static_cast(*this));
+ }
+
+ NodeIt(const Digraph& _graph, const Node& node)
+ : Node(node), digraph(&_graph) {}
+
+ NodeIt& operator++() {
+ digraph->next(*this);
+ return *this;
+ }
+
+ };
+
+
+ class ArcIt : public Arc {
const Digraph* digraph;
public:
@@ -124,19 +124,19 @@
explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
- _graph.first(static_cast(*this));
- }
-
- ArcIt(const Digraph& _graph, const Arc& e) :
- Arc(e), digraph(&_graph) { }
-
- ArcIt& operator++() {
- digraph->next(*this);
- return *this;
- }
-
- };
-
-
- class OutArcIt : public Arc {
+ _graph.first(static_cast(*this));
+ }
+
+ ArcIt(const Digraph& _graph, const Arc& e) :
+ Arc(e), digraph(&_graph) { }
+
+ ArcIt& operator++() {
+ digraph->next(*this);
+ return *this;
+ }
+
+ };
+
+
+ class OutArcIt : public Arc {
const Digraph* digraph;
public:
@@ -146,21 +146,21 @@
OutArcIt(Invalid i) : Arc(i) { }
- OutArcIt(const Digraph& _graph, const Node& node)
- : digraph(&_graph) {
- _graph.firstOut(*this, node);
- }
-
- OutArcIt(const Digraph& _graph, const Arc& arc)
- : Arc(arc), digraph(&_graph) {}
-
- OutArcIt& operator++() {
- digraph->nextOut(*this);
- return *this;
- }
-
- };
-
-
- class InArcIt : public Arc {
+ OutArcIt(const Digraph& _graph, const Node& node)
+ : digraph(&_graph) {
+ _graph.firstOut(*this, node);
+ }
+
+ OutArcIt(const Digraph& _graph, const Arc& arc)
+ : Arc(arc), digraph(&_graph) {}
+
+ OutArcIt& operator++() {
+ digraph->nextOut(*this);
+ return *this;
+ }
+
+ };
+
+
+ class InArcIt : public Arc {
const Digraph* digraph;
public:
@@ -170,15 +170,15 @@
InArcIt(Invalid i) : Arc(i) { }
- InArcIt(const Digraph& _graph, const Node& node)
- : digraph(&_graph) {
- _graph.firstIn(*this, node);
- }
-
- InArcIt(const Digraph& _graph, const Arc& arc) :
- Arc(arc), digraph(&_graph) {}
-
- InArcIt& operator++() {
- digraph->nextIn(*this);
- return *this;
+ InArcIt(const Digraph& _graph, const Node& node)
+ : digraph(&_graph) {
+ _graph.firstIn(*this, node);
+ }
+
+ InArcIt(const Digraph& _graph, const Arc& arc) :
+ Arc(arc), digraph(&_graph) {}
+
+ InArcIt& operator++() {
+ digraph->nextIn(*this);
+ return *this;
}
@@ -216,18 +216,18 @@
// Mappable extension
-
+
template
- class ArcMap
+ class ArcMap
: public MapExtender > {
typedef MapExtender > Parent;
public:
- explicit ArcMap(const Digraph& _g)
- : Parent(_g) {}
- ArcMap(const Digraph& _g, const _Value& _v)
- : Parent(_g, _v) {}
+ explicit ArcMap(const Digraph& _g)
+ : Parent(_g) {}
+ ArcMap(const Digraph& _g, const _Value& _v)
+ : Parent(_g, _v) {}
ArcMap& operator=(const ArcMap& cmap) {
- return operator=(cmap);
+ return operator=(cmap);
}
@@ -235,5 +235,5 @@
ArcMap& operator=(const CMap& cmap) {
Parent::operator=(cmap);
- return *this;
+ return *this;
}
@@ -248,5 +248,5 @@
return arc;
}
-
+
void clear() {
notifier(Arc()).clear();
@@ -311,9 +311,9 @@
Node oppositeNode(const Node &n, const Edge &e) const {
if( n == Parent::u(e))
- return Parent::v(e);
+ return Parent::v(e);
else if( n == Parent::v(e))
- return Parent::u(e);
+ return Parent::u(e);
else
- return INVALID;
+ return INVALID;
}
@@ -339,5 +339,5 @@
using Parent::notifier;
-
+
ArcNotifier& notifier(Arc) const {
return arc_notifier;
@@ -349,5 +349,5 @@
- class NodeIt : public Node {
+ class NodeIt : public Node {
const Graph* graph;
public:
@@ -358,19 +358,19 @@
explicit NodeIt(const Graph& _graph) : graph(&_graph) {
- _graph.first(static_cast(*this));
- }
-
- NodeIt(const Graph& _graph, const Node& node)
- : Node(node), graph(&_graph) {}
-
- NodeIt& operator++() {
- graph->next(*this);
- return *this;
- }
-
- };
-
-
- class ArcIt : public Arc {
+ _graph.first(static_cast(*this));
+ }
+
+ NodeIt(const Graph& _graph, const Node& node)
+ : Node(node), graph(&_graph) {}
+
+ NodeIt& operator++() {
+ graph->next(*this);
+ return *this;
+ }
+
+ };
+
+
+ class ArcIt : public Arc {
const Graph* graph;
public:
@@ -381,19 +381,19 @@
explicit ArcIt(const Graph& _graph) : graph(&_graph) {
- _graph.first(static_cast(*this));
- }
-
- ArcIt(const Graph& _graph, const Arc& e) :
- Arc(e), graph(&_graph) { }
-
- ArcIt& operator++() {
- graph->next(*this);
- return *this;
- }
-
- };
-
-
- class OutArcIt : public Arc {
+ _graph.first(static_cast(*this));
+ }
+
+ ArcIt(const Graph& _graph, const Arc& e) :
+ Arc(e), graph(&_graph) { }
+
+ ArcIt& operator++() {
+ graph->next(*this);
+ return *this;
+ }
+
+ };
+
+
+ class OutArcIt : public Arc {
const Graph* graph;
public:
@@ -403,21 +403,21 @@
OutArcIt(Invalid i) : Arc(i) { }
- OutArcIt(const Graph& _graph, const Node& node)
- : graph(&_graph) {
- _graph.firstOut(*this, node);
- }
-
- OutArcIt(const Graph& _graph, const Arc& arc)
- : Arc(arc), graph(&_graph) {}
-
- OutArcIt& operator++() {
- graph->nextOut(*this);
- return *this;
- }
-
- };
-
-
- class InArcIt : public Arc {
+ OutArcIt(const Graph& _graph, const Node& node)
+ : graph(&_graph) {
+ _graph.firstOut(*this, node);
+ }
+
+ OutArcIt(const Graph& _graph, const Arc& arc)
+ : Arc(arc), graph(&_graph) {}
+
+ OutArcIt& operator++() {
+ graph->nextOut(*this);
+ return *this;
+ }
+
+ };
+
+
+ class InArcIt : public Arc {
const Graph* graph;
public:
@@ -427,21 +427,21 @@
InArcIt(Invalid i) : Arc(i) { }
- InArcIt(const Graph& _graph, const Node& node)
- : graph(&_graph) {
- _graph.firstIn(*this, node);
- }
-
- InArcIt(const Graph& _graph, const Arc& arc) :
- Arc(arc), graph(&_graph) {}
-
- InArcIt& operator++() {
- graph->nextIn(*this);
- return *this;
- }
-
- };
-
-
- class EdgeIt : public Parent::Edge {
+ InArcIt(const Graph& _graph, const Node& node)
+ : graph(&_graph) {
+ _graph.firstIn(*this, node);
+ }
+
+ InArcIt(const Graph& _graph, const Arc& arc) :
+ Arc(arc), graph(&_graph) {}
+
+ InArcIt& operator++() {
+ graph->nextIn(*this);
+ return *this;
+ }
+
+ };
+
+
+ class EdgeIt : public Parent::Edge {
const Graph* graph;
public:
@@ -452,13 +452,13 @@
explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
- _graph.first(static_cast(*this));
- }
-
- EdgeIt(const Graph& _graph, const Edge& e) :
- Edge(e), graph(&_graph) { }
-
- EdgeIt& operator++() {
- graph->next(*this);
- return *this;
+ _graph.first(static_cast(*this));
+ }
+
+ EdgeIt(const Graph& _graph, const Edge& e) :
+ Edge(e), graph(&_graph) { }
+
+ EdgeIt& operator++() {
+ graph->next(*this);
+ return *this;
}
@@ -476,15 +476,15 @@
IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
- _graph.firstInc(*this, direction, n);
+ _graph.firstInc(*this, direction, n);
}
IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
- : graph(&_graph), Edge(ue) {
- direction = (_graph.source(ue) == n);
+ : graph(&_graph), Edge(ue) {
+ direction = (_graph.source(ue) == n);
}
IncEdgeIt& operator++() {
- graph->nextInc(*this, direction);
- return *this;
+ graph->nextInc(*this, direction);
+ return *this;
}
};
@@ -533,16 +533,16 @@
template
- class ArcMap
+ class ArcMap
: public MapExtender > {
typedef MapExtender > Parent;
public:
- explicit ArcMap(const Graph& _g)
- : Parent(_g) {}
- ArcMap(const Graph& _g, const _Value& _v)
- : Parent(_g, _v) {}
+ explicit ArcMap(const Graph& _g)
+ : Parent(_g) {}
+ ArcMap(const Graph& _g, const _Value& _v)
+ : Parent(_g, _v) {}
ArcMap& operator=(const ArcMap& cmap) {
- return operator=(cmap);
+ return operator=(cmap);
}
@@ -550,5 +550,5 @@
ArcMap& operator=(const CMap& cmap) {
Parent::operator=(cmap);
- return *this;
+ return *this;
}
@@ -557,17 +557,17 @@
template
- class EdgeMap
+ class EdgeMap
: public MapExtender > {
typedef MapExtender > Parent;
public:
- explicit EdgeMap(const Graph& _g)
- : Parent(_g) {}
-
- EdgeMap(const Graph& _g, const _Value& _v)
- : Parent(_g, _v) {}
+ explicit EdgeMap(const Graph& _g)
+ : Parent(_g) {}
+
+ EdgeMap(const Graph& _g, const _Value& _v)
+ : Parent(_g, _v) {}
EdgeMap& operator=(const EdgeMap& cmap) {
- return operator=(cmap);
+ return operator=(cmap);
}
@@ -575,5 +575,5 @@
EdgeMap& operator=(const CMap& cmap) {
Parent::operator=(cmap);
- return *this;
+ return *this;
}
@@ -592,5 +592,5 @@
return edge;
}
-
+
void clear() {
notifier(Arc()).clear();
@@ -618,5 +618,5 @@
arc_notifier.clear();
}
-
+
};
Index: lemon/bits/solver_bits.h
===================================================================
--- lemon/bits/solver_bits.h (revision 956)
+++ lemon/bits/solver_bits.h (revision 566)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
Index: lemon/bits/windows.cc
===================================================================
--- lemon/bits/windows.cc (revision 956)
+++ lemon/bits/windows.cc (revision 513)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -97,5 +97,5 @@
GetSystemTime(&time);
char buf1[11], buf2[9], buf3[5];
- if (GetDateFormat(MY_LOCALE, 0, &time,
+ if (GetDateFormat(MY_LOCALE, 0, &time,
("ddd MMM dd"), buf1, 11) &&
GetTimeFormat(MY_LOCALE, 0, &time,
Index: lemon/bucket_heap.h
===================================================================
--- lemon/bucket_heap.h (revision 956)
+++ lemon/bucket_heap.h (revision 758)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -385,5 +385,5 @@
///
/// Note that this implementation does not conform to the
- /// \ref concepts::Heap "heap concept" due to the lack of some
+ /// \ref concepts::Heap "heap concept" due to the lack of some
/// functionality.
///
Index: lemon/capacity_scaling.h
===================================================================
--- lemon/capacity_scaling.h (revision 956)
+++ lemon/capacity_scaling.h (revision 899)
@@ -1,7 +1,7 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
+/* -*- C++ -*-
*
- * This file is a part of LEMON, a generic C++ optimization library.
+ * This file is a part of LEMON, a generic C++ optimization library
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -134,5 +134,5 @@
UNBOUNDED
};
-
+
private:
@@ -140,8 +140,7 @@
typedef std::vector IntVector;
+ typedef std::vector BoolVector;
typedef std::vector ValueVector;
typedef std::vector CostVector;
- typedef std::vector BoolVector;
- // Note: vector is used instead of vector for efficiency reasons
private:
@@ -185,5 +184,5 @@
public:
-
+
/// \brief Constant for infinite upper bounds (capacities).
///
@@ -212,8 +211,8 @@
CostVector &_pi;
IntVector &_pred;
-
+
IntVector _proc_nodes;
CostVector _dist;
-
+
public:
@@ -302,8 +301,4 @@
/// @}
- protected:
-
- CapacityScaling() {}
-
public:
@@ -440,5 +435,5 @@
return *this;
}
-
+
/// @}
@@ -576,5 +571,5 @@
_cost.resize(_res_arc_num);
_supply.resize(_node_num);
-
+
_res_cap.resize(_res_arc_num);
_pi.resize(_node_num);
@@ -620,5 +615,5 @@
_reverse[bi] = fi;
}
-
+
// Reset parameters
resetParams();
@@ -729,5 +724,5 @@
}
if (_sum_supply > 0) return INFEASIBLE;
-
+
// Initialize vectors
for (int i = 0; i != _root; ++i) {
@@ -777,5 +772,5 @@
}
}
-
+
// Handle GEQ supply type
if (_sum_supply < 0) {
@@ -804,13 +799,13 @@
if (_factor > 1) {
// With scaling
- Value max_sup = 0, max_dem = 0, max_cap = 0;
- for (int i = 0; i != _root; ++i) {
+ Value max_sup = 0, max_dem = 0;
+ for (int i = 0; i != _node_num; ++i) {
Value ex = _excess[i];
if ( ex > max_sup) max_sup = ex;
if (-ex > max_dem) max_dem = -ex;
- int last_out = _first_out[i+1] - 1;
- for (int j = _first_out[i]; j != last_out; ++j) {
- if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
- }
+ }
+ Value max_cap = 0;
+ for (int j = 0; j != _res_arc_num; ++j) {
+ if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
}
max_sup = std::min(std::min(max_sup, max_dem), max_cap);
@@ -845,7 +840,7 @@
for (int i = 0; i != _node_num; ++i) {
_pi[i] -= pr;
- }
- }
-
+ }
+ }
+
return pt;
}
Index: lemon/cbc.h
===================================================================
--- lemon/cbc.h (revision 956)
+++ lemon/cbc.h (revision 793)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -122,5 +122,5 @@
int _message_level;
-
+
};
Index: lemon/circulation.h
===================================================================
--- lemon/circulation.h (revision 956)
+++ lemon/circulation.h (revision 891)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -60,6 +60,6 @@
/// \brief The type of supply map.
///
- /// The type of the map that stores the signed supply values of the
- /// nodes.
+ /// The type of the map that stores the signed supply values of the
+ /// nodes.
/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
typedef SM SupplyMap;
@@ -142,5 +142,5 @@
\geq sup(u) \quad \forall u\in V, \f]
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
-
+
The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
zero or negative in order to have a feasible solution (since the sum
@@ -152,5 +152,5 @@
constraints have to be satisfied with equality, i.e. all demands
have to be satisfied and all supplies have to be used.
-
+
If you need the opposite inequalities in the supply/demand constraints
(i.e. the total demand is less than the total supply and all the demands
@@ -338,5 +338,5 @@
/// \param graph The digraph the algorithm runs on.
/// \param lower The lower bounds for the flow values on the arcs.
- /// \param upper The upper bounds (capacities) for the flow values
+ /// \param upper The upper bounds (capacities) for the flow values
/// on the arcs.
/// \param supply The signed supply values of the nodes.
Index: lemon/clp.cc
===================================================================
--- lemon/clp.cc (revision 956)
+++ lemon/clp.cc (revision 793)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
Index: lemon/clp.h
===================================================================
--- lemon/clp.h (revision 956)
+++ lemon/clp.h (revision 793)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -139,5 +139,5 @@
virtual void _messageLevel(MessageLevel);
-
+
public:
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h (revision 956)
+++ lemon/concepts/digraph.h (revision 833)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -435,5 +435,5 @@
private:
///Copy constructor
- NodeMap(const NodeMap& nm) :
+ NodeMap(const NodeMap& nm) :
ReferenceMap(nm) { }
///Assignment operator
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h (revision 956)
+++ lemon/concepts/graph.h (revision 833)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -44,5 +44,5 @@
/// run properly, of course.
/// An actual graph implementation like \ref ListGraph or
- /// \ref SmartGraph may have additional functionality.
+ /// \ref SmartGraph may have additional functionality.
///
/// The undirected graphs also fulfill the concept of \ref Digraph
@@ -86,5 +86,5 @@
///
/// Undirected graphs should be tagged with \c UndirectedTag.
- ///
+ ///
/// This tag helps the \c enable_if technics to make compile time
/// specializations for undirected graphs.
@@ -361,5 +361,5 @@
/// Converison to \c Edge
-
+
/// Converison to \c Edge.
///
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h (revision 956)
+++ lemon/concepts/graph_components.h (revision 833)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -39,5 +39,5 @@
/// \note This class is a template class so that we can use it to
/// create graph skeleton classes. The reason for this is that \c Node
- /// and \c Arc (or \c Edge) types should \e not derive from the same
+ /// and \c Arc (or \c Edge) types should \e not derive from the same
/// base class. For \c Node you should instantiate it with character
/// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
@@ -90,5 +90,5 @@
///
/// This operator defines an ordering of the items.
- /// It makes possible to use graph item types as key types in
+ /// It makes possible to use graph item types as key types in
/// associative containers (e.g. \c std::map).
///
@@ -123,5 +123,5 @@
/// This class describes the base interface of directed graph types.
/// All digraph %concepts have to conform to this class.
- /// It just provides types for nodes and arcs and functions
+ /// It just provides types for nodes and arcs and functions
/// to get the source and the target nodes of arcs.
class BaseDigraphComponent {
@@ -427,5 +427,5 @@
/// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
///
- /// This class describes the concept of \c NodeIt, \c ArcIt and
+ /// This class describes the concept of \c NodeIt, \c ArcIt and
/// \c EdgeIt subtypes of digraph and graph types.
template
@@ -467,5 +467,5 @@
/// next item.
GraphItemIt& operator++() { return *this; }
-
+
/// \brief Equality operator
///
@@ -502,13 +502,13 @@
};
- /// \brief Concept class for \c InArcIt, \c OutArcIt and
+ /// \brief Concept class for \c InArcIt, \c OutArcIt and
/// \c IncEdgeIt types.
///
- /// This class describes the concept of \c InArcIt, \c OutArcIt
+ /// This class describes the concept of \c InArcIt, \c OutArcIt
/// and \c IncEdgeIt subtypes of digraph and graph types.
///
/// \note Since these iterator classes do not inherit from the same
/// base class, there is an additional template parameter (selector)
- /// \c sel. For \c InArcIt you should instantiate it with character
+ /// \c sel. For \c InArcIt you should instantiate it with character
/// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
template ::template Map::Type
- {
+ class AutoNodeMap : public ItemSetTraits::template Map::Type {
typedef typename ItemSetTraits::template Map::Type Parent;
@@ -1280,5 +1279,5 @@
};
- protected:
+ protected:
const Digraph &_g;
Index: lemon/cost_scaling.h
===================================================================
--- lemon/cost_scaling.h (revision 956)
+++ lemon/cost_scaling.h (revision 899)
@@ -1,7 +1,7 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
+/* -*- C++ -*-
*
- * This file is a part of LEMON, a generic C++ optimization library.
+ * This file is a part of LEMON, a generic C++ optimization library
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -93,5 +93,5 @@
/// push/augment and relabel operations for finding a \ref min_cost_flow
/// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
- /// \ref goldberg97efficient, \ref bunnagel98efficient.
+ /// \ref goldberg97efficient, \ref bunnagel98efficient.
/// It is a highly efficient primal-dual solution method, which
/// can be viewed as the generalization of the \ref Preflow
@@ -190,5 +190,5 @@
/// paths from a node with excess to a node with deficit.
AUGMENT,
- /// Partial augment operations are used, i.e. flow is moved on
+ /// Partial augment operations are used, i.e. flow is moved on
/// admissible paths started from a node with excess, but the
/// lengths of these paths are limited. This method can be viewed
@@ -202,12 +202,11 @@
typedef std::vector IntVector;
+ typedef std::vector BoolVector;
typedef std::vector ValueVector;
typedef std::vector CostVector;
typedef std::vector LargeCostVector;
- typedef std::vector BoolVector;
- // Note: vector is used instead of vector for efficiency reasons
private:
-
+
template
class StaticVectorMap {
@@ -215,7 +214,7 @@
typedef KT Key;
typedef VT Value;
-
+
StaticVectorMap(std::vector& v) : _v(v) {}
-
+
const Value& operator[](const Key& key) const {
return _v[StaticDigraph::id(key)];
@@ -225,5 +224,5 @@
return _v[StaticDigraph::id(key)];
}
-
+
void set(const Key& key, const Value& val) {
_v[StaticDigraph::id(key)] = val;
@@ -250,5 +249,4 @@
bool _have_lower;
Value _sum_supply;
- int _sup_node_num;
// Data structures for storing the digraph
@@ -279,10 +277,4 @@
int _alpha;
- IntVector _buckets;
- IntVector _bucket_next;
- IntVector _bucket_prev;
- IntVector _rank;
- int _max_rank;
-
// Data for a StaticDigraph structure
typedef std::pair IntPair;
@@ -292,7 +284,7 @@
LargeCostArcMap _cost_map;
LargeCostNodeMap _pi_map;
-
+
public:
-
+
/// \brief Constant for infinite upper bounds (capacities).
///
@@ -325,8 +317,4 @@
/// @}
-
- protected:
-
- CostScaling() {}
public:
@@ -349,5 +337,5 @@
LEMON_ASSERT(std::numeric_limits::is_signed,
"The cost type of CostScaling must be signed");
-
+
// Reset data structures
reset();
@@ -465,5 +453,5 @@
return *this;
}
-
+
/// @}
@@ -567,5 +555,5 @@
_scost[j] = 0;
_scost[_reverse[j]] = 0;
- }
+ }
_have_lower = false;
return *this;
@@ -602,5 +590,5 @@
_scost.resize(_res_arc_num);
_supply.resize(_res_node_num);
-
+
_res_cap.resize(_res_arc_num);
_cost.resize(_res_arc_num);
@@ -650,5 +638,5 @@
_reverse[bi] = fi;
}
-
+
// Reset parameters
resetParams();
@@ -759,5 +747,5 @@
}
if (_sum_supply > 0) return INFEASIBLE;
-
+
// Initialize vectors
@@ -766,5 +754,5 @@
_excess[i] = _supply[i];
}
-
+
// Remove infinite upper bounds and check negative arcs
const Value MAX = std::numeric_limits::max();
@@ -841,9 +829,4 @@
}
- _sup_node_num = 0;
- for (NodeIt n(_graph); n != INVALID; ++n) {
- if (sup[n] > 0) ++_sup_node_num;
- }
-
// Find a feasible flow using Circulation
Circulation, ValueArcMap, ValueNodeMap>
@@ -880,5 +863,5 @@
for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
int ra = _reverse[a];
- _res_cap[a] = 0;
+ _res_cap[a] = 1;
_res_cap[ra] = 0;
_cost[a] = 0;
@@ -886,5 +869,5 @@
}
}
-
+
return OPTIMAL;
}
@@ -894,12 +877,5 @@
// Maximum path length for partial augment
const int MAX_PATH_LENGTH = 4;
-
- // Initialize data structures for buckets
- _max_rank = _alpha * _res_node_num;
- _buckets.resize(_max_rank);
- _bucket_next.resize(_res_node_num + 1);
- _bucket_prev.resize(_res_node_num + 1);
- _rank.resize(_res_node_num + 1);
-
+
// Execute the algorithm
switch (method) {
@@ -941,171 +917,59 @@
}
- // Initialize a cost scaling phase
- void initPhase() {
- // Saturate arcs not satisfying the optimality condition
- for (int u = 0; u != _res_node_num; ++u) {
- int last_out = _first_out[u+1];
- LargeCost pi_u = _pi[u];
- for (int a = _first_out[u]; a != last_out; ++a) {
- int v = _target[a];
- if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
+ /// Execute the algorithm performing augment and relabel operations
+ void startAugment(int max_length = std::numeric_limits::max()) {
+ // Paramters for heuristics
+ const int BF_HEURISTIC_EPSILON_BOUND = 1000;
+ const int BF_HEURISTIC_BOUND_FACTOR = 3;
+
+ // Perform cost scaling phases
+ IntVector pred_arc(_res_node_num);
+ std::vector path_nodes;
+ for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
+ 1 : _epsilon / _alpha )
+ {
+ // "Early Termination" heuristic: use Bellman-Ford algorithm
+ // to check if the current flow is optimal
+ if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
+ _arc_vec.clear();
+ _cost_vec.clear();
+ for (int j = 0; j != _res_arc_num; ++j) {
+ if (_res_cap[j] > 0) {
+ _arc_vec.push_back(IntPair(_source[j], _target[j]));
+ _cost_vec.push_back(_cost[j] + 1);
+ }
+ }
+ _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
+
+ BellmanFord bf(_sgr, _cost_map);
+ bf.init(0);
+ bool done = false;
+ int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
+ for (int i = 0; i < K && !done; ++i)
+ done = bf.processNextWeakRound();
+ if (done) break;
+ }
+
+ // Saturate arcs not satisfying the optimality condition
+ for (int a = 0; a != _res_arc_num; ++a) {
+ if (_res_cap[a] > 0 &&
+ _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
Value delta = _res_cap[a];
- _excess[u] -= delta;
- _excess[v] += delta;
+ _excess[_source[a]] -= delta;
+ _excess[_target[a]] += delta;
_res_cap[a] = 0;
_res_cap[_reverse[a]] += delta;
}
}
- }
-
- // Find active nodes (i.e. nodes with positive excess)
- for (int u = 0; u != _res_node_num; ++u) {
- if (_excess[u] > 0) _active_nodes.push_back(u);
- }
-
- // Initialize the next arcs
- for (int u = 0; u != _res_node_num; ++u) {
- _next_out[u] = _first_out[u];
- }
- }
-
- // Early termination heuristic
- bool earlyTermination() {
- const double EARLY_TERM_FACTOR = 3.0;
-
- // Build a static residual graph
- _arc_vec.clear();
- _cost_vec.clear();
- for (int j = 0; j != _res_arc_num; ++j) {
- if (_res_cap[j] > 0) {
- _arc_vec.push_back(IntPair(_source[j], _target[j]));
- _cost_vec.push_back(_cost[j] + 1);
- }
- }
- _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
-
- // Run Bellman-Ford algorithm to check if the current flow is optimal
- BellmanFord bf(_sgr, _cost_map);
- bf.init(0);
- bool done = false;
- int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
- for (int i = 0; i < K && !done; ++i) {
- done = bf.processNextWeakRound();
- }
- return done;
- }
-
- // Global potential update heuristic
- void globalUpdate() {
- int bucket_end = _root + 1;
-
- // Initialize buckets
- for (int r = 0; r != _max_rank; ++r) {
- _buckets[r] = bucket_end;
- }
- Value total_excess = 0;
- for (int i = 0; i != _res_node_num; ++i) {
- if (_excess[i] < 0) {
- _rank[i] = 0;
- _bucket_next[i] = _buckets[0];
- _bucket_prev[_buckets[0]] = i;
- _buckets[0] = i;
- } else {
- total_excess += _excess[i];
- _rank[i] = _max_rank;
- }
- }
- if (total_excess == 0) return;
-
- // Search the buckets
- int r = 0;
- for ( ; r != _max_rank; ++r) {
- while (_buckets[r] != bucket_end) {
- // Remove the first node from the current bucket
- int u = _buckets[r];
- _buckets[r] = _bucket_next[u];
-
- // Search the incomming arcs of u
- LargeCost pi_u = _pi[u];
- int last_out = _first_out[u+1];
- for (int a = _first_out[u]; a != last_out; ++a) {
- int ra = _reverse[a];
- if (_res_cap[ra] > 0) {
- int v = _source[ra];
- int old_rank_v = _rank[v];
- if (r < old_rank_v) {
- // Compute the new rank of v
- LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
- int new_rank_v = old_rank_v;
- if (nrc < LargeCost(_max_rank))
- new_rank_v = r + 1 + int(nrc);
-
- // Change the rank of v
- if (new_rank_v < old_rank_v) {
- _rank[v] = new_rank_v;
- _next_out[v] = _first_out[v];
-
- // Remove v from its old bucket
- if (old_rank_v < _max_rank) {
- if (_buckets[old_rank_v] == v) {
- _buckets[old_rank_v] = _bucket_next[v];
- } else {
- _bucket_next[_bucket_prev[v]] = _bucket_next[v];
- _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
- }
- }
-
- // Insert v to its new bucket
- _bucket_next[v] = _buckets[new_rank_v];
- _bucket_prev[_buckets[new_rank_v]] = v;
- _buckets[new_rank_v] = v;
- }
- }
- }
- }
-
- // Finish search if there are no more active nodes
- if (_excess[u] > 0) {
- total_excess -= _excess[u];
- if (total_excess <= 0) break;
- }
- }
- if (total_excess <= 0) break;
- }
-
- // Relabel nodes
- for (int u = 0; u != _res_node_num; ++u) {
- int k = std::min(_rank[u], r);
- if (k > 0) {
- _pi[u] -= _epsilon * k;
+
+ // Find active nodes (i.e. nodes with positive excess)
+ for (int u = 0; u != _res_node_num; ++u) {
+ if (_excess[u] > 0) _active_nodes.push_back(u);
+ }
+
+ // Initialize the next arcs
+ for (int u = 0; u != _res_node_num; ++u) {
_next_out[u] = _first_out[u];
}
- }
- }
-
- /// Execute the algorithm performing augment and relabel operations
- void startAugment(int max_length = std::numeric_limits::max()) {
- // Paramters for heuristics
- const int EARLY_TERM_EPSILON_LIMIT = 1000;
- const double GLOBAL_UPDATE_FACTOR = 3.0;
-
- const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
- (_res_node_num + _sup_node_num * _sup_node_num));
- int next_update_limit = global_update_freq;
-
- int relabel_cnt = 0;
-
- // Perform cost scaling phases
- std::vector path;
- for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
- 1 : _epsilon / _alpha )
- {
- // Early termination heuristic
- if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
- if (earlyTermination()) break;
- }
-
- // Initialize current phase
- initPhase();
// Perform partial augment and relabel operations
@@ -1118,18 +982,23 @@
if (_active_nodes.size() == 0) break;
int start = _active_nodes.front();
+ path_nodes.clear();
+ path_nodes.push_back(start);
// Find an augmenting path from the start node
- path.clear();
int tip = start;
- while (_excess[tip] >= 0 && int(path.size()) < max_length) {
+ while (_excess[tip] >= 0 &&
+ int(path_nodes.size()) <= max_length) {
int u;
- LargeCost min_red_cost, rc, pi_tip = _pi[tip];
- int last_out = _first_out[tip+1];
+ LargeCost min_red_cost, rc;
+ int last_out = _sum_supply < 0 ?
+ _first_out[tip+1] : _first_out[tip+1] - 1;
for (int a = _next_out[tip]; a != last_out; ++a) {
- u = _target[a];
- if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
- path.push_back(a);
+ if (_res_cap[a] > 0 &&
+ _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
+ u = _target[a];
+ pred_arc[u] = a;
_next_out[tip] = a;
tip = u;
+ path_nodes.push_back(tip);
goto next_step;
}
@@ -1137,11 +1006,7 @@
// Relabel tip node
- min_red_cost = std::numeric_limits::max();
- if (tip != start) {
- int ra = _reverse[path.back()];
- min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
- }
+ min_red_cost = std::numeric_limits::max() / 2;
for (int a = _first_out[tip]; a != last_out; ++a) {
- rc = _cost[a] + pi_tip - _pi[_target[a]];
+ rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
if (_res_cap[a] > 0 && rc < min_red_cost) {
min_red_cost = rc;
@@ -1149,11 +1014,12 @@
}
_pi[tip] -= min_red_cost + _epsilon;
+
+ // Reset the next arc of tip
_next_out[tip] = _first_out[tip];
- ++relabel_cnt;
// Step back
if (tip != start) {
- tip = _source[path.back()];
- path.pop_back();
+ path_nodes.pop_back();
+ tip = path_nodes.back();
}
@@ -1163,9 +1029,9 @@
// Augment along the found path (as much flow as possible)
Value delta;
- int pa, u, v = start;
- for (int i = 0; i != int(path.size()); ++i) {
- pa = path[i];
+ int u, v = path_nodes.front(), pa;
+ for (int i = 1; i < int(path_nodes.size()); ++i) {
u = v;
- v = _target[pa];
+ v = path_nodes[i];
+ pa = pred_arc[v];
delta = std::min(_res_cap[pa], _excess[u]);
_res_cap[pa] -= delta;
@@ -1176,10 +1042,4 @@
_active_nodes.push_back(v);
}
-
- // Global update heuristic
- if (relabel_cnt >= next_update_limit) {
- globalUpdate();
- next_update_limit += global_update_freq;
- }
}
}
@@ -1189,38 +1049,67 @@
void startPush() {
// Paramters for heuristics
- const int EARLY_TERM_EPSILON_LIMIT = 1000;
- const double GLOBAL_UPDATE_FACTOR = 2.0;
-
- const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
- (_res_node_num + _sup_node_num * _sup_node_num));
- int next_update_limit = global_update_freq;
-
- int relabel_cnt = 0;
+ const int BF_HEURISTIC_EPSILON_BOUND = 1000;
+ const int BF_HEURISTIC_BOUND_FACTOR = 3;
// Perform cost scaling phases
BoolVector hyper(_res_node_num, false);
- LargeCostVector hyper_cost(_res_node_num);
for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
1 : _epsilon / _alpha )
{
- // Early termination heuristic
- if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
- if (earlyTermination()) break;
- }
-
- // Initialize current phase
- initPhase();
+ // "Early Termination" heuristic: use Bellman-Ford algorithm
+ // to check if the current flow is optimal
+ if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
+ _arc_vec.clear();
+ _cost_vec.clear();
+ for (int j = 0; j != _res_arc_num; ++j) {
+ if (_res_cap[j] > 0) {
+ _arc_vec.push_back(IntPair(_source[j], _target[j]));
+ _cost_vec.push_back(_cost[j] + 1);
+ }
+ }
+ _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
+
+ BellmanFord bf(_sgr, _cost_map);
+ bf.init(0);
+ bool done = false;
+ int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
+ for (int i = 0; i < K && !done; ++i)
+ done = bf.processNextWeakRound();
+ if (done) break;
+ }
+
+ // Saturate arcs not satisfying the optimality condition
+ for (int a = 0; a != _res_arc_num; ++a) {
+ if (_res_cap[a] > 0 &&
+ _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
+ Value delta = _res_cap[a];
+ _excess[_source[a]] -= delta;
+ _excess[_target[a]] += delta;
+ _res_cap[a] = 0;
+ _res_cap[_reverse[a]] += delta;
+ }
+ }
+
+ // Find active nodes (i.e. nodes with positive excess)
+ for (int u = 0; u != _res_node_num; ++u) {
+ if (_excess[u] > 0) _active_nodes.push_back(u);
+ }
+
+ // Initialize the next arcs
+ for (int u = 0; u != _res_node_num; ++u) {
+ _next_out[u] = _first_out[u];
+ }
// Perform push and relabel operations
while (_active_nodes.size() > 0) {
- LargeCost min_red_cost, rc, pi_n;
+ LargeCost min_red_cost, rc;
Value delta;
int n, t, a, last_out = _res_arc_num;
+ // Select an active node (FIFO selection)
next_node:
- // Select an active node (FIFO selection)
n = _active_nodes.front();
- last_out = _first_out[n+1];
- pi_n = _pi[n];
+ last_out = _sum_supply < 0 ?
+ _first_out[n+1] : _first_out[n+1] - 1;
// Perform push operations if there are admissible arcs
@@ -1228,5 +1117,5 @@
for (a = _next_out[n]; a != last_out; ++a) {
if (_res_cap[a] > 0 &&
- _cost[a] + pi_n - _pi[_target[a]] < 0) {
+ _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
delta = std::min(_res_cap[a], _excess[n]);
t = _target[a];
@@ -1234,9 +1123,9 @@
// Push-look-ahead heuristic
Value ahead = -_excess[t];
- int last_out_t = _first_out[t+1];
- LargeCost pi_t = _pi[t];
+ int last_out_t = _sum_supply < 0 ?
+ _first_out[t+1] : _first_out[t+1] - 1;
for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
- if (_res_cap[ta] > 0 &&
- _cost[ta] + pi_t - _pi[_target[ta]] < 0)
+ if (_res_cap[ta] > 0 &&
+ _cost[ta] + _pi[_source[ta]] - _pi[_target[ta]] < 0)
ahead += _res_cap[ta];
if (ahead >= delta) break;
@@ -1245,5 +1134,5 @@
// Push flow along the arc
- if (ahead < delta && !hyper[t]) {
+ if (ahead < delta) {
_res_cap[a] -= ahead;
_res_cap[_reverse[a]] += ahead;
@@ -1252,5 +1141,4 @@
_active_nodes.push_front(t);
hyper[t] = true;
- hyper_cost[t] = _cost[a] + pi_n - pi_t;
_next_out[n] = a;
goto next_node;
@@ -1275,8 +1163,7 @@
// Relabel the node if it is still active (or hyper)
if (_excess[n] > 0 || hyper[n]) {
- min_red_cost = hyper[n] ? -hyper_cost[n] :
- std::numeric_limits::max();
+ min_red_cost = std::numeric_limits::max() / 2;
for (int a = _first_out[n]; a != last_out; ++a) {
- rc = _cost[a] + pi_n - _pi[_target[a]];
+ rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
if (_res_cap[a] > 0 && rc < min_red_cost) {
min_red_cost = rc;
@@ -1284,9 +1171,10 @@
}
_pi[n] -= min_red_cost + _epsilon;
+ hyper[n] = false;
+
+ // Reset the next arc
_next_out[n] = _first_out[n];
- hyper[n] = false;
- ++relabel_cnt;
}
-
+
// Remove nodes that are not active nor hyper
remove_nodes:
@@ -1296,12 +1184,4 @@
_active_nodes.pop_front();
}
-
- // Global update heuristic
- if (relabel_cnt >= next_update_limit) {
- globalUpdate();
- for (int u = 0; u != _res_node_num; ++u)
- hyper[u] = false;
- next_update_limit += global_update_freq;
- }
}
}
Index: lemon/cplex.cc
===================================================================
--- lemon/cplex.cc (revision 956)
+++ lemon/cplex.cc (revision 793)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -112,5 +112,5 @@
}
- int CplexBase::_addRow(Value lb, ExprIterator b,
+ int CplexBase::_addRow(Value lb, ExprIterator b,
ExprIterator e, Value ub) {
int i = CPXgetnumrows(cplexEnv(), _prob);
@@ -490,5 +490,5 @@
void CplexBase::_applyMessageLevel() {
- CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
+ CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
_message_enabled ? CPX_ON : CPX_OFF);
}
Index: lemon/cycle_canceling.h
===================================================================
--- lemon/cycle_canceling.h (revision 956)
+++ lemon/cycle_canceling.h (revision 898)
@@ -1,7 +1,7 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
+/* -*- C++ -*-
*
- * This file is a part of LEMON, a generic C++ optimization library.
+ * This file is a part of LEMON, a generic C++ optimization library
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -35,5 +35,5 @@
#include
#include
-#include
+#include