lemon-0.x: Changelog

Various improvements in NetworkSimplex.

- Faster variant of "Altering Candidate List" pivot rule using make_heap
instead of partial_sort.
- Doc improvements.
- Removing unecessary inline keywords.

Improved constructors for min cost flow classes
Removing the non-zero lower bounds is faster

Improve tree update procedure in NetworkSimplex
The new method updates a smaller subtree (fixing a bug) and shifting the
potentials with a costant value.

Backport doxygen options for version 1.5.7 from [9194a12c52e6]

Adapt the doc generation to the hg repo

Major improvement in the cost scaling algorithm

- Add a new variant that use the partial augment-relabel method.
- Use this method instead of push-relabel by default.
- Use the "Early Termination" heuristic instead of "Price Refinement".

Using the new method and heuristic the algorithm proved to be
2-2.5 times faster on all input files.

Bug fixes is HaoOrlin and MinCostArborescence

MinCostArborescence
- proper deallocation
HaoOrlin
- the target needn't to be the last in its bucket
- proper size of container (if each node starts in different buckets initially)

Add missing pointer initializing in min cost flow classes

Bug fix in min_cost_flow_test.cc

Improve network simplex algorithm

- Remove "Limited Search" and "Combined" pivot rules.
- Add a new pivot rule "Altering Candidate List".
- Make the edge selection faster in every pivot rule.
- Set the default rule to "Block Search".
- Doc improvements.

The algorithm became about 15-35 percent faster on various input files.
"Block Search" pivot rule proved to be by far the fastest on all inputs.

G++-4.3 compatibility changes

Backport bug fix for Id handling from hg changeset [e67acd83a9ca]

Back port bug fix from hg changeset [0915721396dc]

Fix bug caused by m4 consuming pairs of square brackets (#108).

Update the version number

Back porting hg commit 81563e019fa4

Bug fix initialization
The std::numeric_limits<double>::min() means the smallest positive number,
and not the smallest number in the whole range of double.

Fixing bug in named parameters (Back port bug fix of ticket #95)

Bug fix full graph problam

Fixing lp constraints (solving ticket #92)

Avoid warning in random.h (backport of chgset 4790635473ef from lemon-1.0)

Remove SspMinCostFlow, since it is fully replaced by other classes.

Revert mistaken changes in NEWS file.

Bug fixes in LP solvers
- the copyLp is clarified
- newLp and copyLp gives back pointers
- cplex gives back empty string for variables without name
- cplex row and column retrieval
- added macro for soplex

Small fixes in NEWS file

Rel.07 NEWS - 3. round

Rel.07 NEWS - 2. round

NEWS file updated for Release 0.7

Serious bugfix in Random::gamma()
Backport from hg b6bede534255

Correcting broken repo

Back porting commit 81563e019fa4

Bug fix for not connected graphs

Executable property removed

Fix static member initializations (ticket #30).

Revert to long long int since currently I don't know a better solution.

In C++98 array size shall be an integral constant expression. Fixes
ticket 12.

There is no 'long long int' type in C++98 (only in C99).

Bug fix in CapacityScaling.

Small improvements in min cost flow files.

External flow and potential maps can be used in MinCostMaxFlow.

Reimplemented Suurballe class.

- The new version is the specialized version of CapacityScaling.
- It is about 10-20 times faster than the former Suurballe algorithm
and about 20-50 percent faster than CapacityScaling.
- Doc improvements.
- The test file is also replaced.

Backport of bug fix hg 2de55e4f57a7

Test file for the min cost flow algorithms.

Small fixes and doc improvements in MinMeanCycle.

Avoid map copy in MinCostMaxFlow.

Query improvements in the min cost flow algorithms.

- External flow and potential maps can be used.
- New query functions: flow() and potential().
- CycleCanceling also provides dual solution (node potentials).
- Doc improvements.

Bug fixes in min cost flow files.
Use enum type instead of static constants in NetworkSimplex to avoid
linker errors.

Put the definitions of global functions into a .cc file.

Add a cost scaling min cost flow algorithm.

Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.

Improvements in MinCostFlow and MinCostMaxFlow.

Main changes:
- MinCostMaxFlow also provides dual solution.
- Change the name of private members to start with "_".
- Change the name of function parameters not to start with "_".
- Remove unnecessary documentation for private members.
- Doc improvements.

Major improvements in NetworkSimplex.

Main changes:
- Use -potenital[] instead of potential[] to conform to the usual
terminology.
- Use function parameter instead of #define commands to select pivot rule.
- Use much faster implementation for the candidate list pivot rule.
It is about 5-20 times faster now.
- Add a new pivot rule called "Limited Search" that is a modified
version of "Block Search". It is about 25 percent faster on rather
sparse graphs.
- By default "Limited Search" is used for sparse graphs and
"Block Search" is used otherwise. This combined method is the most
efficient on every input class.
- Change the name of private members to start with "_".
- Change the name of function parameters not to start with "_".
- Remove unnecessary documentation for private members.
- Many doc improvements.

Improvements in CapacityScaling.

Main changes:
- Use -potenital[] instead of potential[] to conform to the usual
terminology.
- Change the name of private members to start with "_".
- Change the name of function parameters not to start with "_".
- Remove unnecessary documentation for private members.
- Doc improvements.

Improvements in CycleCanceling.

Main changes:
- Use function parameter instead of #define commands to select negative
cycle detection method.
- Change the name of private members to start with "_".
- Change the name of function parameters not to start with "_".
- Remove unnecessary documentation for private members.
- Doc improvements.

Hopefully fix all compilation errors.

#include<cmath> -> #include<lemon/math.h>

Math constants + configure bugfix backported
from hg a315a588a20d and 761622e5ed4c

Update the server and the repository names to lemon.

Doc improvments backported from hg 9df0fe5e5109

Bug fix in heap_test.cc.

Several doc improvements and fixes in maps.h and concepts/maps.h.

Small fixes in README.

Improvements and fixes in dim2.h.

- Several doc improvements.
- Fix BoundingBox::operator& implementation.

Translate Hungarian varible names and improve messages in dim_test.cc.

Fix the rename script.

grid_ugraph.h: fixed #18 (global functions inlined)

Improved rename script to handle includes correctly.

Reveal an existing functionality in the documentation

Cleanup in the minimum cost flow files.
The changes only affects the documentation and the look of the source codes.

Reimplemented MinMeanCycle to be much more efficient.
The new version implements Howard's algorithm instead of Karp's algorithm and
it is at least 10-20 times faster on all the 40-50 random graphs we have tested.

Happy New Year to LEMON (+ better update-copyright-header script)

Improved rename script to avoid "undirected digraph".

Include functional because of std::less.

Changing degree of tournament tree
Bug fix in union find
Small efficiency improvment in bipartite matchings

Test program for max weighted matchings

Edmond's Blossom shrinking algroithm:
MaxWeightedMatching
MaxWeightedPerfectMatching

Renaming state_enum to State
Removing "Type" suffix from typedefs
Moving implementation into the class definition

Casting index to int

Bug fix (Circulation interface changed).

Change the local variables lower case

DynEdgeLookUp implementation based on splay trees
In general case it is slower than the static version, but it should not
refreshed on the change of the graph

Using operation traits in dijkstra

Modified rename script (BpGraph instead of Bigraph).

Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.