Merge

Merge

LEMON 1.2.3 released (9e587caed953 tagged as r1.2.3)

Unify sources

Update NEWS file

LEMON 1.1.5 released (74e2dac774c8 tagged as r1.1.5)

Unify sources

Update NEWS file

Merge bugfix #430

Merge bugfix #430 to branch 1.2

Merge bugfix #430 to branch 1.1

Fix LpBase::Constr two-side limit bug (#430)

Merge #428 and #429

Merge #428 and #429 to branch 1.2

Merge #428 and #429 to branch 1.1

Fix windows-specific compilation error (#429)

Fix VS warnings (#429)

Add lemon/lemon.pc.cmake to the release tarball (#428)

LEMON 1.2.2 released (d303bfa8b1ed tagged as r1.2.2)

Unify sources

Update NEWS file

LEMON 1.1.4 released (f1398882a928 tagged as r1.1.4)

Unify sources

Update NEWS file

LEMON 1.0.7 released (c59bdcc8e33e tagged as r1.0.7)

Unify sources

Update NEWS file

Merge AUTHORS file update

Merge AUTHORS file update to branch 1.2

Merge AUTHORS file update to branch 1.1

Merge AUTHORS file update to branch 1.0

Update the AUTHORS file

Merge #382

Merge #382 to branch 1.2

Merge #382 to branch 1.1

Merge #382 to branch 1.0

Allow lgf file without Arc maps (#382)

A single '-' character in the @arcs sectio header indicates that
there is no arc map.

Merge #419

Merge #419 to branch 1.2

Merge #419 to branch 1.1

Do not look for COIN_VOL libraries

Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin (#419)

Build of mip_test and lp_test precede the running of the tests (#419)

Merge GLPK fix #337 with CMAKE improvements

Merge bugfix #420

Merge bugfix #420 to branch 1.2

Fix IterableValueMap (#420)

Merge #418

Merge #418 to branch 1.2

Merge #418 to branch 1.1

Better Win CodeBlock/MinGW support (#418)
- Remove -ansi compilation flag
- Don't include sys/times.h when WIN32 is defined

Merge #416 to branch 1.1

Merge #416 to branch 1.2

Merge #416

Change the default scaling factor in CostScaling (#417)

Faster computation of the dual solution in CostScaling (#417)

Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well.

Fix and improve refine methods in CostScaling (#417)

Minor improvements in CostScaling (#417)

Support tests with valgrind (#416)

Merge bugfix in #417 to branch 1.2

Merge #417

Bug fix in CostScaling (#417)

Merge #404

Merge #404 to branch 1.2

Merge #404 to branch 1.1

Remove doc header (show version number on the main page) (#404)

Update Doxygen config files + enable search (#404)

Merge CMAKE backports to branch 1.2

Merge CMAKE and Doxygen backports to branch 1.1

Backport the CMAKE related changesets from the main branch

[e20fecd1945f] Add check target for CMake (#388)
[e74b5db4f2c6] Put the output of chg-len.py in the version string (#389)
[7d166b8b8018] Safer call of ./scripts/chg-len.py on Windows (#389)
[659ba4805a48] Make CMAKE config more consistent with configure.ac (#390)
[63e4468c680e] Add 'Maintainer' CMAKE build type (#388, #390)
[a725503acfe9] Allow CPACK configuration on all platforms
[10242c611190] Create and install lemon.pc (#393)
[48e29534cf03] The deafult target doesn't build lp_test and mip_test (#388)
[0fbbdd578c06] Full path for DoxygenLayout.xml in Doxyfile.in (#395)
[481496e6d71f] SOURCE_BROWSER Doxygen switch is configurable from CMAKE (#395)
[09282720100b] update-external-tags CMAKE target (#395)

Backport [53bea38f71cb] 'Update Doxygen configuration file'

Add contrib dir (#401)

Merge bugfix #414

Merge bugfix #414 to branch 1.2

Merge bugfix #414 to branch 1.1

Fix wrong initialization in Preflow (#414)

Merge

Minor doc improvements

Improve the doc of path structures (#406)

Various doc improvements (#406)

Various search limits for the max clique alg (#405)

Merge

Port max. card. search alg. from svn -r3512 (#397) and (#56)

Doc improvements in HaoOrlin (#398)

Merge

New implementation for Nagamochi-Ibaraki algorithm

update-external-tags CMAKE target (#395)

SOURCE_BROWSER Doxygen switch is configurable from CMAKE (#395)

Full path for DoxygenLayout.xml in Doxyfile.in (#395)

The deafult target doesn't build lp_test and mip_test (#388)

Create and install lemon.pc (#393)

Merge bugfix #392

Merge bugfix #392 to branch 1.2

Merge bugfix #392 to branch 1.1

Merge bugfix #392 to branch 1.0

Bug fix in Dfs::start(s,t) (#392)

LEMON 1.2.1 released (ffc2d2559fc9 tagged as r1.2.1)

Update NEWS file

LEMON 1.1.3 released (dfdb58f52f02 tagged as r1.1.3)

Update NEWS file

LEMON 1.0.6 released (7d26a96745f7 tagged as r1.0.6)

Update NEWS file

Merge #380

Add a heuristic algorithm for the max clique problem (#380)

Merge CMAKE config improvements (#388, #389, #390)

Allow CPACK configuration on all platforms

Add 'Maintainer' CMAKE build type (#388, #390)

- some extra warning and debug options
- build stops on warning (-Werror)
- tests are built and run by default

Make CMAKE config more consistent with configure.ac (#390)

- CMAKE_BUILD_TYPE is Release by deafult
- The same set of warnings are used when compiling with gcc

Safer call of ./scripts/chg-len.py on Windows (#389)

Still hard to get it worked properly by user. It needs
- a python interpreter in the exec path
- the mercurial modules accessible by this interpreter

Put the output of chg-len.py in the version string (#389)

Add check target for CMake (#388)

Improve arc mixing in NS and enable it by default (#391)

Improve the tree update process and a pivot rule (#391)
and make some parts of the code clearer using better names

Improve graph_copy_test.cc

Merge bugfix #371

Merge bugfix #372

Merge bugfix #371 to branch 1.2

Merge bugfix #372 to branch 1.2

Merge bugfix #371 to branch 1.1

Merge bugfix #372 to branch 1.1

Fix critical bug in preflow (#372)

The wrong transition between the bound decrease and highest active
heuristics caused the bug. The last node chosen in bound decrease mode
is used in the first iteration in highest active mode.

Merge bugfix #371 to branch 1.0

Bug fix in (di)graphCopy() (#371)

The target graph is cleared before adding nodes and arcs/edges.

Merge bugfix #368

Merge bugfix #368 to branch 1.2

Merge bugfix #368 to branch 1.1

Fix the usage of min() (#368)

Merge bugfix #366

Merge bugfix #366 to branch 1.2

Merge bugfix #366 to branch 1.1

Merge bugfix #366 to branch 1.0

Fix PredMatrixMapPath::empty() (#366)

Fix PredMapPath::empty() (#366)

Merge bugfix #364

Merge bugfix #364 to branch 1.2

Merge bugfix #364 to branch 1.1

Add an undirected() function (#364)

Add missing UndirectedTags (#364)

LEMON 1.2 released (3ed8f7c8bed8 tagged as r1.2)

Merge #341, #360, #51, #359 to branch 1.2

Update NEWS file

Trim the documentation (#359)

Merge backout of a6eb9698c321 (#360,#51)

Small doc fixes and improvements (#359)

Backed out changeset a6eb9698c321 (#360, #51)

Release branch 1.2 created

Unify the sources (#339)

Fix multiple executions in matchings (fract. mathcings) (#356)

Merge #356

Merge #314

Minor doc fix related to #348

Uniforming primal scale to 2 (#314)

Fix documentation issues (#314)

Fractional matching initialization of weighted matchings (#314)

Add fractional matching algorithms (#314)

General improvements in weighted matching algorithms (#314)

- Fix include guard
- Uniform handling of MATCHED and UNMATCHED blossoms
- Prefer operations which decrease the number of trees
- Fix improper use of '/='

The solved problems did not cause wrong solution.

Merge bugfix #356 to branch 1.1

Fix multiple execution bug in weighted matchings (#356)

This chgset also redoes the fix of [28c7ad6f8d91] and its backpont to 1.1,
[268a052c3043].

Add doc/references.dox to .hgignore

Replace figure at matching doc #348

The original bibartite_matching.eps is kept for future use.

Rename min mean cycle classes and their members (#179)
with respect to the possible introduction of min ratio
cycle algorithms in the future.

The renamed classes:
- Karp --> KarpMmc
- HartmannOrlin --> HartmannOrlinMmc
- Howard --> HowardMmc

The renamed members:
- cycleLength() --> cycleCost()
- cycleArcNum() --> cycleSize()
- findMinMean() --> findCycleMean()
- Value --> Cost
- LargeValue --> LargeCost
- SetLargeValue --> SetLargeCost

Fix gcc 3.3 compilation error (#354)

gcc 3.3 requires that a class has a default constructor if it has
template named parameters. (That constructor can be protected.)

LEMON 1.1.2 released (86a880ba752d tagged as r1.1.2)

Update NEWS file

LEMON 1.0.5 released (50b6b66daafd tagged as r1.0.5)

Update NEWS file

Clarify type names in NetworkSimplex (#353)

This patch clarifies the misleading effects of the renamings
in [f3bc4e9b5f3a].

Merge #306

Add tolerance() functions for HaoOrlin (#306)

Merge #301

Also test fullInit() in suurballe_test (#181, #323)

Add traits class + named parameters to Suurballe (#323)

The following types can be modified using named parameters:
- FlowMap
- PotentialMap
- Path
- Heap + HeapCrossRef

Merge #181, #323

Rename heap structures (#301)

- KaryHeap --> DHeap
- FouraryHeap --> QuadHeap
- BinomHeap --> BinomialHeap

Merge bugfixes #323 to branch 1.1

Add a fullInit() function to Suurballe (#181, #323)
to provide faster handling of multiple targets.
A start() function is also added, just for the sake of
convenience.

Rework and improve Suurballe (#323)

- Improve the implementation: use a specific, faster variant of
residual Dijkstra for the first search.
- Some reorganizatiopn to make the code simpler.
- Small doc improvements.

Remove unnecessary integer requirement in Suurballe (#323)

Bug fix in Suurballe (#323)

Configurable glpk prefix in ./scripts/bootstrap.sh and ...
unneeded solver backends are explicitely switched off with --without-*

Merge #342

Improve README and mainpage.dox (#342)

Merge #347

Use 'long long' flow cost in dimacs-solver.cc (#347)

Merge

Support tolerance technique for BellmanFord (#51)

A new operation traits class BellmanFordToleranceOperationTraits
is introduced, which uses the tolerance technique in its less()
function. This class can be used with the SetOperationTraits
named template parameter.

Merge #332

ArgParser can throw exception instead of exit(1) (#332)

Better return type for cycleLength() functions (#179)
in the min mean cycle algorithms.

The original Value type is used instead of the LargeValue type,
which is introduced for internal computations.

Merge 4 backouts (#50, #312)

Back out 4 changesets (#50, #312)
- 532697c9fa53
- bb8c4cd57900
- 9f529abcaebf
- 703ebf476a1d

Merge #340

New heuristics for MCF algorithms (#340)
and some implementation improvements.

- A useful heuristic is added to NetworkSimplex to make the
initial pivots faster.
- A powerful global update heuristic is added to CostScaling
and the implementation is reworked with various improvements.
- Better relabeling in CostScaling to improve numerical stability
and make the code faster.
- A small improvement is made in CapacityScaling for better
delta computation.
- Add notes to the classes about the usage of vector<char> instead
of vector<bool> for efficiency reasons.

Merge bugfix #336

Merge bugfix #336 to branch 1.1

Merge bugfix #336 to branch 1.0

Fix the date field comment of graphToEps() output (#336)

Modify the header of scripts/bib2dox.py (#184)

Merge

Fix LpBase::addRow(Constr) (#334)

Merge bugfix #337

Merge bugfix #337 to branch 1.1

Use void* like LPX object (#337)

Merge

Handle graph changes in the MCF algorithms (#327)

The reset() functions are renamed to resetParams() and the new reset()
functions handle the graph chnages, as well.

Merge

Doc improvements for planarity related tools (#62)

Port planar image from SVN -r3524 (#62)

Fix clear() function in ExtendFindEnum (#335), backport of [28c7ad6f8d91]

Fix clear() function in ExtendFindEnum (#335), backport of [28c7ad6f8d91]

Merge

Add doc for the traits class parameters (#315)

Add more information on Makefile variables (#316)

Add a warning about huge capacities in Preflow (#319)

Merge #180 and a bugfix in #51

Small bug fixes (#180)

Rename a private type in MCF classes (#180)

The new MCF algorithms define a private map type VectorMap,
which could be misleading, since there is an other VectorMap
defined in lemon/bits/vector_map.h. Thus the new type is
is renamed to StaticVectorMap.

Adds tests for the new MCF algorithms (#180)

Rework the MCF test file to help extending it (#180)

Fixes in the heap concept to avoid warnings (#180)

Add citations to CycleCanceling (#180, #184)

Entirely rework cycle canceling algorithms (#180)

- Move the cycle canceling algorithms (CycleCanceling, CancelAndTighten)
into one class (CycleCanceling).
- Add a Method parameter to the run() function to be able to select
the used cycle canceling method.
- Use the new interface similarly to NetworkSimplex.
- Rework the implementations using an efficient internal structure
for handling the residual network.
This improvement made the codes much faster.
- Handle GEQ supply type (LEQ is not supported).
- Handle infinite upper bounds.
- Handle negative costs (for arcs of finite upper bound).
- Extend the documentation.

Port cycle canceling algorithms from SVN -r3524 (#180)

Add citations to the scaling MCF algorithms (#180, #184)
and improve the doc of their group.

Small doc improvements + unifications in MCF classes (#180)

Small implementation improvements in MCF algorithms (#180)

- Handle max() as infinite value (not only infinity()).
- Better GEQ handling in CapacityScaling.
- Skip the unnecessary saturating operations in the first phase in
CapacityScaling.
- Use vector<char> instead of vector<bool> and vector<int> if it is
possible and it proved to be usually faster.

More options for run() in scaling MCF algorithms (#180)

- Three methods can be selected and the scaling factor can be
given for CostScaling.
- The scaling factor can be given for CapacityScaling.

Entirely rework CostScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster.
- Handle GEQ supply type (LEQ is not supported).
- Handle infinite upper bounds.
- Handle negative costs (for arcs of finite upper bound).
- Traits class + named parameter for the LargeCost type used in
internal computations.
- Extend the documentation.

Port CostScaling from SVN -r3524 (#180)

Traits class + a named parameter for CapacityScaling (#180)
to specify the heap used in internal Dijkstra computations.

Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.

Port CapacityScaling from SVN -r3524 (#180)

Memory leak bugfix in BellmanFord (#51)

Merge bugfix #330

Merge bugfix #330 to branch 1.1

Merge

Merge bugfix #330 to branch 1.0

Bug fix in map_extender.h (#330)

Fix clear() function in ExtendFindEnum (#335)