Rel.07 NEWS - 2. round

NEWS file updated for Release 0.7

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

Minor bug fix

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

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.

Fix VPATH builds.

Hopefully fix all compilation errors.

Fix a silly typo

#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.

Minor doc fix

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

Bug fix in erase