Merge #179 (Port the min mean cycle algorithms)

Add tolerance() functions for MMC classes (#179)

Separate group for the min mean cycle classes (#179)

Simplify comparisons in min mean cycle classes (#179)
using extreme INF values instead of bool flags.

Add HartmannOrlin algorithm class (#179)
This algorithm is an improved version of Karp's original method,
it applies an efficient early termination scheme.
The interface is the same as Karp's and Howard's interface.

Add Karp algorithm class (#179)
based on the MinMeanCycle implementation in SVN -r3436.
The interface is reworked to be the same as Howard's interface.

Rename MinMeanCycle to Howard (#179)

Add a detailed test file for MinMeanCycle and fix test_tools.h (#179)

Rename cyclePath() to cycle() in MinMeanCycle (#179)

Traits class + named parameters for MinMeanCycle (#179)

- Add a Traits class defining LargeValue, Tolerance, Path types.
LargeValue is used for internal computations, it is 'long long'
if the length type is integer, otherwise it is 'double'.
- Add named template parameters for LargeValue and Path types.
- Improve numerical stability: remove divisions from the internal
computations. If the arc lengths are integers, then all used
values are integers (except for the cycleMean() query function,
of course).

Rework and fix the implementation of MinMeanCycle (#179)

- Fix the handling of the cycle means.
- Many implementation improvements:
- More efficient data storage for the strongly connected
components.
- Better handling of BFS queues.
- Merge consecutive BFS searches (perform two BFS searches
instead of three).

This version is about two times faster on average and an order of
magnitude faster if there are a lot of strongly connected components.

Simplify the interface of MinMeanCycle (#179)
Remove init() and reset(), and move their content into findMinMean().

Port MinMeanCycle from SVN -r3524 (#179)
with some doc improvements

Merge #184

Update Doxygen configuration file

Insert citations into the doc (#184)

- Add general citations to modules.
- Add specific citations for max flow and min cost flow algorithms.
- Add citations for the supported LP and MIP solvers.
- Extend the main page.
- Replace inproceedings entries with the journal versions.
- Add a new bibtex entry about network simplex.
- Remove unwanted entries.

Handle url fields in bib2dox.py (#184)
and modify the bibtex file using url fields.

Merge bugfix #322

Distribute LEMONConfig.cmake.in (#322)

Merge bugfix in #250

Merge #317

Remove unnecessary OsiCbc dependency (#317)

Fix (and improve) error message in mip_test.cc (#317)

Add soplex support to scripts/bootstrap.sh plus...
it checks whether cbc and soplex are installed at the given prefix.

Faster add row operation (#203)

One virtual function call instead of more

Improve bib2dox.py using \section for entiries (#184)

Integrate bib2dox.py into the build environments (#184)

Add bib->dox converter and initial references.bib (#184)

Merge #311

Merge

Add a warning for List(Di)Graph::Snapshot (#311)
and extend tests for snapshots

Modify the implementation of ListDigraph::ArcIt (#311)

The new implementation is based on out-arc iteration (like
ListGraph::ArcIt) instead of in-arc iteration to make it
consistent with the documentation.

Much better implementation for node splitting (#311)
in ListDigraph. This solution is the same as the one that
is used in SmartDigraph. It is much faster and does not
invalidate any iterator like the former implementation.

Add a resize() function to HypercubeGraph (#311)
just like the similar functions in other static graph structures,
and extend the test files to check these functions.

Add reserve functions to ListGraph and SmartGraph (#311)
ListDigraph and SmartDigraph already have such functions.

Doc improvements, fixes and unifications for graphs (#311)

Doc improvements and unification for graph concepts (#311)

Copyright notices added to scripts

Simple interactive bootstrap script

Merge #298

Merge

Small improvements for NetworkSimplex (#298)

Add a parameter to control arc mixing in NS (#298)

Small improvements in NS pivot rules (#298)

Merge #302

Add creator functions for IdMap and RangeIdMap (#302)

Rename ValueIterator to ValueIt in graph maps (#302)
but keep ValueIterator as an alias in CrossRefMap
(only for reverse compatibility).

Extend maps_test.cc (#302)

Doc improvements for several graph maps (#302)

Merge

Improvements for graph maps (#302)

- Add a count() function to CrossRefMap.
- Add tests for IdMap and RangeIdMap.
- Extend tests for CrossRefMap.
- Improve the doc.

Merge

Also check ReferenceMapTag in concept checks (#312)

Merge

Small doc improvements (#304)

Merge

Rearrange modules (#303)

Small doc improvements

Merge

Unify member names in heaps (#299)

The following renamings are made.

Public members:
- UnderFlowPriorityError -> PriorityUnderflowError
("underflow" is only one word)

Private members:
- bubble_up() -> bubbleUp()
- bubble_down() -> bubbleDown()
- second_child() -> secondChild()
- makeroot() -> makeRoot()
- relocate_last() -> relocateLast()
- data -> _data
- boxes -> _boxes

Move the heaps to a separate group (#299)

Improve and unify the documentation of heaps (#299)
and avoid a warning in SimpleBucketHeap::operator[].

Merge

Much faster implementation for BinomHeap (#301)

Smarter bubbleDown() in K-ary heaps (#301)

Small improvements in heap implementations (#301)

Make K a template parameter in KaryHeap (#301)

Improve and unify the doc + names in the new heaps (#301)

Bug fix in PairingHeap::pop() (#301)

Add fourary, k-ary, pairing and binomial heaps (#301)
These structures were implemented by Dorian Batha.

Merge

Add negativeCycle() function to BellmanFord (#51)

Add a detailed test file for BellmanFord (#51)

Improvements and unifications for BellmanFord (#51)

- Rework the function type interface to fit to dijkstra().
- Rename named template parameters (Def* -> Set*).
- Rename some private member variables
(to start with an underscore).
- Simplify template parameter names.
- Many unifications and improvements in the doc.

Port Bellman-Ford algorithm from SVN -r3524 (#51)

Merge

Improvements for iterable maps (#73)

Port iterable maps from SVN 3509 (#73)

Merge

Bug fix + extension in the rename script (#305)

Merge

Test file + doc improvements (#307)

Bug fix in Preflow and Circulation (#307)

Merge

Merge

Add missing 'explicit' keywords (#311)

Fix the implementation and doc of CrossRefMap (#302)

- Handle multiple values correctly with std::multimap.
- Clarify the problematic points in the doc.
- Add some basic tests for the class.

Unification of names in heaps (#50)

Simplified implementation of bucket heaps (#50)

Port remaining heaps from SVN -r 3509 (#50)

- FibHeap
- RadixHeap
- BucketHeap
- SimpleBucketHeap

Set the version to 'hg-tip' if everything fails

Minor CMake improvements

* Use the empty ELSE(), ENDIF(), ENDMACRO(), etc. syntax since this improves
readability and requires less typing.
* Use FIND_PACKAGE() instead of INCLUDE().
* Use the value of CMAKE_COMMAND variable instead of cmake, since this works
even if cmake is not in the PATH.

Put the version string into config.h

Also make it possible to set the version using the LEMON_VERSION environment
variable, and use the hg revision as version string in case this variable is
unset.

Fix the check for the 'long long' type

Change the label of the html project in Visual Studio

Generate and install LEMONConfig.cmake

Add tools/CMakeLists.txt to the tarball

Rename documentation install folder from 'docs' to 'html'

Remove duplications from doc/CMakeLists.txt

Suppress MSVC warnings using pragmas (#295)

Add artificial addNode() function to the arc/edge set classes

Avoid Intel C++ Compiler warnings

Disable Visual Studio warning C4503

Add lemon/config.h.cmake to the tarball

Resolve GCC-4.4 warnings & fix ambiguous op=() in graph_components.h

Update NEWS file

Extend min cost flow test file + check dual costs (#291)

Fix the GEQ/LEQ handling in NetworkSimplex + improve doc (#291)

- Fix the optimality conditions for the GEQ/LEQ form.
- Fix the initialization of the algortihm. It ensures correct
solutions and it is much faster for the inequality forms.
- Fix the pivot rules to search all the arcs that have to be
allowed to get in the basis.
- Better block size for the Block Search pivot rule.
- Improve documentation of the problem and move it to a
separate page.

Merge

Remove bits/base_extender.h, which is not used at all (#288)

Move list and edge sets to the graph module (#290)

Merge

Change the explanation of the acronym LEMON (#289)

Change Graph::Edge -> Graph::Arc inheritance to conversion (#283)

Change Undirector::Edge -> Undirector::Arc inheritance to conversion (#283)

Fix the faulty merge of unify-sources.sh in [586b65073025]

Doc fixes for lgf-gen (#282)

Merge

Merge

Small doc improvements (#257)

Fix glp_prob definition (#286)

Add a test file for the connectivity functions (#285)
The Euler tools have a separate test file.

Doc improvements and fixes for connectivity tools (#285)
And add loopFree(), parallelFree(), simpleGraph() to the module doc.

Bug fixes in connectivity.h (#285)

- Bug fix in tree().
- Rename simpleDigraph() to simpleGraph() (it works for both
directed and undirected graphs).
- Possibly faster implementation for parallelFree() and
simpleGraph().

Merge

Add the solver libraries to lemon.pc.in (#281)

Merge

Resolve gcc-4.3 warning in lemon/network_simplex.h

Less map copying in NetworkSimplex (#234)

- The graph is copied in the constructor instead of the init() function.
It must not be modified after the class is constructed.
- The maps are copied once (instead of twice).
- Remove FlowMap, PotentialMap typedefs and flowMap(), pontentialMap()
setter functions.
- flowMap() and potentialMap() query functions copy the values into the
given map (reference) instead of returning a const reference to a
previously constructed map.

Rename Flow to Value in the flow algorithms (#266)

We agreed that using Flow for the value type is misleading, since
a flow should be rather a function on the arcs, not a single value.

This patch reverts the changes of [dacc2cee2b4c] for Preflow and
Circulation.

Support negative costs and bounds in NetworkSimplex (#270)

* The interface is reworked to support negative costs and bounds.
- ProblemType and problemType() are renamed to
SupplyType and supplyType(), see also #234.
- ProblemType type is introduced similarly to the LP interface.
- 'bool run()' is replaced by 'ProblemType run()' to handle
unbounded problem instances, as well.
- Add INF public member constant similarly to the LP interface.
* Remove capacityMap() and boundMaps(), see also #266.
* Update the problem definition in the MCF module.
* Remove the usage of Circulation (and adaptors) for checking feasibility.
Check feasibility by examining the artifical arcs instead (after solving
the problem).
* Additional check for unbounded negative cycles found during the
algorithm (it is possible now, since negative costs are allowed).
* Fix in the constructor (the value types needn't be integer any more),
see also #254.
* Improve and extend the doc.
* Rework the test file and add test cases for negative costs and bounds.

Merge

Check the version number in FindGLPK (#277)

Add GLPK_ROOT_DIR variable to FindGLPK (#277)

Link libm and libpthread if using CPLEX (#277)

Add CPLEX_ROOT_DIR variable to FindCPLEX (#277)

Look for COIN libraries with and without the lib prefix too (#277)

This is necessary because on Windows when built using autotools the COIN
libraries are named in UNIX style, i.e. libCbc.lib insetad of Cbc.lib.

Merge

Merge

Remove superfluous HAVE_CONFIG_H (#278)

Add cbc.h to lemon/Makefile.am (#279)

Fix Makefile.am EXTRA_DIST (#276)

Merge

Merge and extend the fix of #275

Merge

Modify the interface of MinCostArborescence + improvements (#267)

- Rename arborescenceValue() to arborescenceCost().
- Rename DefXyz template named paramaters to SetXyz.
- Rearrange public functions (for better doc).
- Doc improvements.
- Extend the test file with interface checking.

Merge

Modify the interface of Suurballe (#266, #181)

- Move the parameters s and t from the constructor to the run()
function. It makes the interface capable for multiple run(s,t,k)
calls (possible improvement in the future) and it is more similar
to Dijkstra.
- Simliarly init() and findFlow(k) were replaced by init(s) and
findFlow(t,k). The separation of parameters s and t is for the
future plans of supporting multiple targets with one source node.
For more information see #181.
- LEMON_ASSERT for the Length type (check if it is integer).
- Doc improvements.
- Rearrange query functions.
- Extend test file.

Support infinite bounds in Circulation + fixes (#270, #266)

- Support infinite capacities.
- Bug fix in upperMap().
- Fixes and improvements in the documentation.

FindCOIN for CMake (#256)

FindCPLEX for CMake (#256)

FindGLPK improvements (#256)

Merge

Fix and uniform the usage of Graph and Parent typedefs (#268)

- Rename Graph typedefs to GraphType in the implementation of graph
maps and MapExtender to prevent conflicts (especially using VS).
They are not public.
- Make Parent typedefs private in all classes.
- Replace Digraph with Graph in some places
(fix faulty renamings of the script).
- Use Graph and Digraph typedefs (more) consequently.

VS compatibility fix (#268)

Exploit the changes of #190 in MCF test file (#234, #190)

Support LEQ and GEQ supply constraints in dimacs-solver (#234, #219)

Bug fix in NetworkSimplex (#234)

Fix usage of sqrt() (#268)

Merge and fix

Slightly modify the interface of Circulation and Preflow (#266)
in order to synchronize them to the interface of NetworkSimplex.

Circulation:
- The "delta" notation is replaced by "supply".
- lowerCapMap(), upperCapMap() are renamed to lowerMap() and upperMap().
- Value is renamed to Flow.

Preflow:
- Value is renamed to Flow.

Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.

Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.

Separate types for flow and cost values in NetworkSimplex (#234)

Support multiple run() calls in NetworkSimplex (#234)

Rework the interface of NetworkSimplex (#234)

The parameters of the problem can be set with separate functions
instead of different constructors.

Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).

Internal restructuring and renamings in NetworkSimplex (#234)

Support min cost flow in dimacs-solver (#234)

Port NetworkSimplex from SVN -r3520 (#234)

Merge

Merge

Add more docs to LGF function interface (#109)

Fix in HaoOrlin (#264)

Improvements and fixes for the minimum cut algorithms (#264)

Merge

Rename max_matching.h to matching.h (#265)

Extend and modify the interface of matching algorithms (#265)

- Rename decomposition() to status() in MaxMatching.
- Add a new query function statusMap() to MaxMatching.
- Add a new query function matchingMap() to all the three classes.
- Rename matchingValue() to matchingWeight() in the weighted
matching classes.

Improvements for the Euler tools and the test file (#264)

Bug fix in the Euler iterators (#264)
Handle the case when the first node is isolated.

Imporvements for the matching algorithms (#264)

Merge

Merge

Rotate and enlarge some images (#262)

Add images + fixes in the doc of connectivity tools (#262)

Improve test files for some algorithms (#263)

Small doc improvements (#263)

Merge

Remove notes about reference maps as extra features (#190)

Exploit that the standard maps are reference maps (#190)

Standard graph maps are required to be reference maps (#190)

Various improvements and fixes (mainly in the doc) (#190)

Merge

Merge

Unified message handling for LP and MIP solvers (#9)

Force cplex checking (#260)

Add RangeIdMap, CrossRefMap to the rename script (#160)

Merge

DescriptorMap->RangeIdMap, InvertableMap->CrossRefMap (#160)

Merge

Fix compilation with MSVC (#259)

Fix compilation with MSVC (#258)

Single check macro for all COIN-OR dependencies (#204)

Add CBC support (#204)

Silent glp_adv_basis() (#255)

Fixing presolver and basis handling (#255)

Add 'demo' make target for building the demo programs

Fix in .hgignore

Merge

Accept negative values as unbounded capacity in dimacs readers (#243)
and some doc improvements.

Merge

Various doc improvements (#248)
- Rename all the ugly template parameters (too long and/or starting
with an underscore).
- Rename function parameters starting with an underscore.
- Extend the doc for many classes.
- Use LaTeX-style O(...) expressions only for the complicated ones.
- A lot of small unification changes.
- Small fixes.
- Some other improvements.

Improve timer and counter tests (#253)

- Do not print the output of counter_test.cc.
- Check the output of counter_test.cc.
- Shorten the running time of time_measure_test.cc.

Merge

Merge

Fix and extend the migration script (#245)

Bug fix in unify-sources.sh (#245)

Merge

CMake subproject support fixes (#240)

Fix lp related errors and warnings (#241 and #242)

Switch on warnings when compiling the lib

Make it possible to use LEMON as a CMake subproject (#240)

Merge

Merge

Doc improvements in GomoryHu (#66)
And make init() and start() private + bug fix in the test file.

Remane GomoryHuTree to GomoryHu (#66)

Cut iterators for GomoryHuTree + doc cleanup + bug fixes (#66)

Porting Gomory-Hu algorithm (#66)

Merge

Remove \bug and \todo comments

Fix newSolver()/cloneSolver() API in LP tools + doc improvements (#230)
- More logical structure for newSolver()/cloneSolver()
- Fix compilation problem with gcc-3.3
- Doc improvements

Fix Soplex config in autoconf (#230)

Automatic GLPK env deallocation (#213)

Fix GLPK tests (#213)

Merge

Merge

Merge

Merge

Small improvements in DIMACS solver (#226)

Avoid warnings in test/euler_test.h (#65)

Merge

Fix the naming convention of guards and remove one unnecessary include

Merge

CMAKE builds the tools/ dir, too (#228)

DIMACS solver utility (#226)

dimacs.h reads MAT files to both dir and undir graphs (#231)

Option for lgf-gen to draw the edges only

Port lgf-gen from SVN -r3512 (#45)

- apply the migrate script
- apply the source unifyer
- fix the compilation

Test for euler.h (#65)

Rename euler() to eulerian() (#65)

Port Euler walk tools from SVN -r3512 (#65)

Fix several missing includes (#232)

Merge

Merge

Use pathCopy(from,to) instead of copyPath(to,from) (#321)
The old version is kept as a deprecated alternative.

Slightly simplify adaptors_test.cc

Fix in pathSource() and pathTarget() (#250)
and extend the doc.

Remove duplicate list_graph.h entry from source list (#308)

Do not distribute lemon/config.h and fix its bad include by core.h (#280)

Prefix macro names with LEMON_ in lemon/config.h (#275)

Install lemon/config.h (#274)

unify-sources.sh refresh the dates according to the last modification

Small script making a release

LEMON is a COIN-OR project now

Minor fix in the LICENSE file

Fix missing 'inline' specifier in time_measure.h (#239)

Also note the cmake based build environment in INSTALL file

Various doc improvements

Include /lemon/config.h globally (#230)

Port MinCostArborescence algorithm from SVN #3509

CMAKE config improvements
- install docs in share/doc/
- look for newer versions of Ghostscript

Merge

Various fixes for compiling on AIX (#211, #212)

Default implementation of Tolerance<> is used for integer types (#229)

Add long long checking to build systems (#230)

Fixes in adaptors.h to compile on AIX

Add cmake/cmake.version to .hgignore

Further fixes to windows.cc (#215)

Merge

Wrap around the usages of windows.h

Dirty hacking for VS 2005 in lp_base.h (#209)

Merge

Fixes for MSVC 2008 in grap_adaptors.h and edge_set.h (#194)

Several renamings and changes in adaptors and edge sets

- Fixing scope usage for MSVC
- ResidualDigraph based on SubDigraph instead of FilterArcs
- Use initialize() in adaptors and edge sets
- Wrap ListDigraph for edge set tests

Change LEMON's isnan() to isNaN() for the sake of AIX/xlC

Certain xlC versions implement isnan() as a #define.

Fix in lp_base.cc targeting AIX/xlC compatibility

Merge

Set the compatibily related MSVC defines only if they has't been defined yet

Compilation bug fixed in graph_to_eps.h with VS2005 (#214)

Add missing include to time_measure.h

Merge (manually add cmake/FindGLPK.cmake to Makefile.am)

Set the proper version for CMAKE in the tarballs (made by autotools).

Enable the component-based installer

Update the lemon icon

Suppress or fix VS2008 warnings + turn off faulty tests using CMAKE (#208)

Merge

Fix 'make install' without 'make html' using CMAKE (#207)

Fix CMAKE build without GLPK

Build GLPK dependent parts with CMake too

(.hg)ignore more build-like dirs (*objs* and *build*)

Fix lp indexing bug (#205)

Own support for isnan()

Merge

ArcSet and EdgeSet ports from SVN 3489 (ticket #67)

Merge

Rename graph adaptors with the migration script (#67)

Rename graph_adaptor_test.cc to adaptors_test.cc (#67)

Rename Residual to ResidualDigraph (#67)
The new name is more analogous to other adaptor names.

Greatly extend and improve the test file for adaptors (#67)

- Add concept checks for the alterable, extendable, erasable
and clearable adaptors.
- Add test cases for modifying the underlying graphs through adaptors
whenever it is possible.
- Check the conversions between Node, Arc and Edge types.
- Add more test cases for the adaptor-specific functions and maps:
enable(), disable(), status(), forward(), backward(), CombinedArcMap,
CombinedNodeMap, ResidualCapacity etc.
- Use checkGraphIncEdgeArcLists() to simplify the test cases for
undirected graphs.
- Add test cases that use static graph structure (GridGraph) with
several adaptors combined.
- Add comments for the test cases.

Rename Lp*/Mip* to *Lp/*Mip

Remove lp_ prefix from the solver's header name

Bypass warnings with gcc 4.3

Thorough redesign of the LP/MIP interface (#44)

- Redesigned class structure
- Redesigned iterators
- Some functions in the basic interface redesigned
- More complete setting functions
- Ray retrieving functions
- Lot of improvements
- Cplex common env
- CLP macro definition to config.h.in
- Update lp.h to also use soplex and clp
- Remove default_solver_name
- New solverName() function in solvers
- Handle exceptions for MipCplex test
- Rename tolerance parameter to epsilon
- Rename MapIt to CoeffIt
- Lot of documentation improvements
- Various bugfixes

Port LP and MIP solvers from SVN -r3509 (#44)

Add HAVE_LP and HAVE_MIP #defines

Ignore standard .m4 files

Merge

Update lemon/adaptors.h's header to 2009

Remove non-checked subgraph adaptors + rename parameters (#67)

Rename convenience functions in subgraph adaptors (#67)

- Rename hide(), unHide() to disable(), enable().
- Add new set function status(Item, bool).
- Remove hidden() and add status() instead
(which returns the opposite value).

Various doc improvements for graph adaptors (#67)

- Add notes about modifying the adapted graphs through adaptors
if it is possible.
- Add notes about the possible conversions between the Node, Arc and
Edge types of the adapted graphs and the adaptors.
- Hide the default values for template parameters (describe them
in the doc instead).
- More precise docs for template parameters.
- More precise docs for member functions.
- Add docs for important public typedefs.
- Unify the docs of the adaptors.
- Add \relates commands for the creator functions.
- Fixes and improvements the module documentation.

Add creator functions for Residual and Residual::ResidualCapacity (#67)

Various bug fixes and code improvements in adaptors.h (#67)

- Fix UndirectorBase::nodeNum().
- Fix UndirectorBase::findEdge().
- Fix OrienterBase::addArc().
- Fix OrienterBase::findArc().
- Improve SplitNodesBase::findArc().
- Add missing notifier() function in UndirectorBase.
- Add missing typedefs for maps (conform to the ReferenceMap concept).
- Add some useful typedefs for graph adaptors.

Add missing const keywords (+ remove misleading ones) (#67)

Avoid warning in adaptors.h (#67)

Fix the usage of tags in adaptors.h (#67)
There are separate tags for arcs and edges now.

Merge

Update to 2009 plus whitespace unification

Rename counterSort to stableRadixSort

Doc improvements and source unification in radix_sort (#72)

Porting radix sorts from SVN #3509

Happy New Year again
- update the copyright headers + run the source unifier

Merge bugfix #197

Bug fix in heap unionfind (ticket #197)

The previous bugfix set the minimum value in internal nodes
wrongly. It corrects the problem.

Merge bugfix #197

Bug fix in heap unionfind (ticket #197)

The minimum item in the unionfind tree might become inconsistent when
the split operation merges two subtrees which have equal keys. The
current changeset fix the problem. It also fix a wrong index.

Merge

Merge

Merge

Merge

Hide all docs in variant.h (#196)

Bug fix in variant.h (#196)

Bug fix in ConEdgeIt (#195)

Merge

Fix skipSection() function (ticket #193)

Merge

Fix typos (ticket #192)

Update test/CMakeLists.txt and test/Makefile.am

Inline the test input files into the source code

chg-len.py does not scan any hg config file now

Merge

Add missing 'const' for query functions of algorithms

Renamings in connectivity.h and bug fix in DfsVisit (#61)

- The include guard, the private namespace and some local varibles
are renamed
- The stop() must be called in DfsVisit, if there are not outgoing
arcs from the added node

Merge

Port topology.h as connectivity.h from SVN -r3509 (#61)

Reorganication of graph adaptors and doc improvements (#67)

- Moving to one file, lemon/adaptors.h
- Renamings
- Doc cleanings

Improvements in graph adaptors (#67)

Remove DigraphAdaptor and GraphAdaptor
Remove docs of base classes
Move the member documentations to real adaptors
Minor improvements in documentation

Port graph adaptors from svn -r3498 (#67)

Merge

Minor doc improvements in HaoOrlin (#58)

New queue implementation for HaoOrlin class (#58)

Simple test for HaoOrlin algorithm class (#58)

Port Hao-Orlin algorithm from SVN -r3509 (#58)

Merge

Merge

Improvements in groups.dox (#188)

- Unify the notations used for formulas.
- Add 'namespace lemon {...}' to simplify the references.
- Improved doc for algorithm groups.
- Extend the doc of the "shortest path" and "minimum cost flow" modules.

Doc improvements for Bfs, Dfs, Dijkstra (#185)

- More precise references to overloaded member functions.
- Hide the doc of the traits class parameters.
- Better doc for named groups.
- More precise doc for the case of multiple sources in Dfs.

Merge

Improve test file for Circulation (#175)

- Bug fix: add a missing #include.
- Add compile test for various functions and named parameters.
- Use a smaller digraph with lower bounds.
- Test eight instances instead of two.
- Remove the doc that was for the demo file.

Many doc improvements for Circulation (#175)

- More precise doc for members.
- Several doc fixes.
- Add doc for public types.
- Better formulations.
- Add useful notes to the problem description.
- Use supply instead of excess in the doc.
- Hide the doc of the traits class parameter.
- Use \tparam for template parameters.

Def->Set change in lemon/circulation.h

Transform circulation demo to test

Port Circulation from svn -r3516 (#175)
Namely,
- port the files
- apply the migrate script
- apply the unify script
- fix the compilation
- strip the demo input file
- break long lines

Merge

Remove DijkstraWidestPathOperationTraits (#187)

Improve unify-sources.sh (#186)
Errors can also be accepted when the script is used as a hg hook.
Sometimes it is useful (e.g. if someone else made the errors).

Merge

Better test files for Preflow (#176)

- Slightly improve preflow_test.cc.
- Change preflow_test.lgf to meet the new LGF format
and remove trailing tabs.

Many doc improvements for Preflow (#176)

- More precise doc for members.
- Add doc for public types.
- Hide the doc of the traits class parameter.
- Removing \author comments.
- Use \tparam for template parameters.

Rename flowInit() to init() in Preflow (#176)

Def -> Set renaming in Preflow

Get rid of exceptions in Preflow

Port preflow push max flow alg. from svn -r3516 (#176)
Namely,
- port the files
- apply the migrate script
- apply the unify script
- break the long lines in lemon/preflow.h
- convert the .dim test file to .lgf
- fix compilation problems

Doc improvements for the DIMACS tools (#167)
The doc group is moved to groups.dox.

Refactoring of DIMACS tools

Give different names to the different DIMACS readers

Port DIMACS tools from svn -r3516

Namely,
- apply migrate script
- apply unify sources
- break long lines
- Fixes the compilation
- dim_to_lgf -> dimacs-to-lgf
- better .hgignore
- shorten the doc of dimacs-to-lgf

Merge

Doc improvements for elevator classes (#174)

Don't assume that the default maps are reference maps (in Elevator)

Avoid STL panic at Elevator when compiled with -D_GLIBCXX_DEBUG

Rename markToBottom() to dirtyTopButOne() + better doc (#174)

Port Elevator from svn -r3516 (#174)
- the unify script hes also been applied

Merge

Bugfix in Random (#173)

- operator()s always return a double now
- the faulty real<Num>(Num) and real<Num>(Num,Num) have been removed

chg-len.py uses the Mercurial API directly

This makes chg-len.py much faster.

Merge

Extend test cases for graphs and digraphs (#172)

Bug fix in SmartGraph::restoreSnapshot() (#171)

Avoid bit operator precedence warning with gcc-4.3

Some of these warnings are actually revealed real bugs

Merge

Critical bug fix in SmartDigraph::split() #170

Merge

Add missing tags and functions for item counting in SmartGraph (#3)

Hide "used files" on the doc pages

Merge

Rework hypercube graph implementation to be undirected (#57)

Port hypercube digraph structure from SVN 3503 (#57)

Revert to the canonical way of customizing CXXFLAGS

A default list of compiler flags is set via AM_CXXFLAGS Automake variable.
However this gets overridden by per-target CXXFLAGS variables (e.g.
foo_CXXFLAGS in case the foo target). Because of this you should append
$(AM_CXXFLAGS) to the end of the per-target CXXFLAGS variables (e.g.
foo_CXXFLAGS = ... $(AM_CXXFLAGS)).

After this default list of flags the contents of the CXXFLAGS user variable is
passed to the compiler. This variable has a default value determined by
configure (in case of g++ it is '-g -O2'). You can override this by specifying
CXXFLAGS when invoking make (e.g. make CXXFLAGS='-O3').

Merge

Doc improvements for the graph related tools in lemon/bits

Add missing tags and indicators

Rename readNauty() to readNautyGraph() (#55)

Redo erroneous modification of [7c5d8de2eac7] (#55)

Merge

Merge

Bug fix in FullDigraphBase::findArc()

Improvements related to full graphs (#57)

Porting full graphs from svn 3498

- the FullGraph is redesigned in implementation
- some improvemnts in documentation

Small improvements for the nauty reader (#55)

Move the doc of the nauty group to groups.dox (#55)

Swap parameters in readNauty()

Merge

Porting nauty reader function from SVN #3509

Merge

Minor doc improvements related to Suurballe (#47)

Port Suurballe algorithm from svn -r3512

More improvement in the migration script

- Rename (U)GRAPH_TYPEDEFS.
- Rename "directed graph" to "digraph".

Improve the migration script and guide (#166)

- Safer replacement of 'graph' and 'edge'.
- Fix the erroneous renaming of [Gg]raphToEps.
- Fixes and improvements in the migration guide.

Merge

Use standard error/warning message format in the unifier script

Minor doc improvements

Lognormal distribution added (#102)

Fix latex image generation

Merge

Fixes and improvements related to GridGraph

Improvement on grid graphs

- The indexing of matrix is changed according to integer points of the plane.
- The graph type does not depend on the UndirGraphExtender.
- Improving documentation.
- Improved image generation.

Port grid graph structure from SVN 3503 (ticket #57)

Merge

Merge

Merge

Doc improvements in lemon/max_matching.h

Print the failed line numbers in the unifier script (ticket #138)

Small improvements in the unifier script

Several improvements in maximum matching algorithms
- The interface of MaxMatching is changed to be similar to the
weighted algorithms
- The internal data structure (the queue implementation and the
matching map) is changed in the MaxMatching algorithm, which
provides better runtime properties
- The Blossom iterators are changed slightly in the weighted matching
algorithms
- Several documentation improvments
- The test files are merged

Port maximum matching algorithms from svn 3498 (ticket #48)

Better help message and user question in unify-sources.sh

Improved unifier and checker script

- Unify and check modes
- Several file listing modes

Improve the 0.x->1.x converter script (ticket #157)

- Support updating more files at once.
- Much better regexp solution for "whole words only" replacements.

Update NEWS file

Merge

AUTHORS file added

arrert.h is now included by core.h (#161)

Doc improvements

Merge

Updated doxygen options to version 1.5.7.1

Merge

Doc reorganization + improvements

- Reorganize several tools (move them to other modules).
- Add new module for map concepts.
- Remove the doc of all tools in lemon/bits.
- Improvements in groups.dox.
- Fix some doxygen warnings.

Fix several doxygen warnings

Merge

Fix an erroneous const declaration in ArgParser

Repository reorganization

- lemon-0.x-to-1.x.sh moved to tools/ and it installs to $(bindir).
- benchmark/ dir has been removed.

Merge

Changes in LGF related part of the migration guide

Further extension of the migration guide

Improvements in the migration script and guide (ticket #157)

0.x -> 1.x migration script and guide (preliminary version) (#157)

Merge

Fix compilation with Visual Studio 2005.

Merge

Fix several doxygen warings

Revert faulty changes of [dc9e8d2c0df9]

Doxygen 1.5.7.1 somehow needs this to generate the graphs

Fix ignoring Emacs backup/temp files

Merge

Properly detect the Intel C++ compiler (ticket #154).

Fix memory leak hazard

If the constructor throws an exception, it should deallocate each
dynamically allocated memory.

Merge

Change the parameter order in LGF reader and writer tools

Merge

Changing parameter order in exception classes + improvements

Simplifying exceptions

- Using asserts instead of exceptions for unitialized parameters
- Only the IO exceptions are used in the lemon
- DataFormatError is renamed to FormatError
- The IoError is used for file access errors

Use DEBUG instead of ASSERT in graph extenders (ticket #17)

Use proper traits class in visitor based algorithms

Merge

Improvements related to BFS/DFS/Dijkstra (ticket #96)
- Add run(s,t) function to BfsVisit.
- Modify run(s,t) functions in the class interfaces to return bool value.
- Bug fix in Dijkstra::start(t) function.
- Improve Dijkstra::currentDist().
- Extend test files to check named class template parameters.
- Doc improvements.

Remove the BOOST copyright notice from lemon/concept_check.h
as it no longer applies there.

Make chg-len.py independent from the global Mercurial config files

Merge

Using from-to order in graph copying tools + doc improvements (ticket #150)

Merge

Remove todo-s and convert them to trac tickets

Merge

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)
- BfsWizard and DfsWizard have run(s), run(s,t), and run() functions,
DijkstraWizard has run(s) and run(s,t) functions.
- Set NodeMap<T> instead of NullMap as PredMap and DistMap in the default
traits classes for the function-type interface.
- Modify the related test files.
- Doc improvements.
- Bug fix in concepts/path.h.

Removing fixme an log assert handler from assertion system

Merge

Merge

Use only a single (cached) variable to hold the version number.

Better versioning (#144)

Python script for computing the longest path in the revision tree

Merge

doc/named-param.dox was missing from doc/Makefile.am

Improvements in named-param.dox (ticket #147)

Improvements in named-param.dox

Port named-param.dox from svn -r3504

Use __func__ only if the compiler supports it (ticket #148).

Merge

Merge

Make copy constr and op= of the default maps private (ticket #137)

Update NEWS file (ticket #121)

Use standard #ifndef/#define for avoiding multiple include.

Merge

Disable checks for ILP solvers.

Merge

Rename Def* to Set* in Bfs, Dfs, Dijkstra (ticket #134)
- DefXyzMap --> SetXyzMap
- DefHeap --> SetHeap
- DefStandardHeap --> SetStandardHeap
- DefOperationTraits --> SetOperationTraits
- DefProcessedMapToBeDefaultMap --> SetStandardProcessedMap
- Bug fix: SetStandardProcessedMap shouldn't be template

Bug fix + doc improvement in UndirDigraphExtender (ticket #141)

Merge

Merge

Rename BoundingBox to Box (ticket #126)

Doc improvement for visitor classes (ticket #134)

Fix processedMap() named parameter for dijkstra() (ticket #140)

Stream operators for Point and BoundingBox classes (ticket #126)
- Add operator<< and operator>> for BoundingBox.
- operator<< of Point gives space-less output.

Ignore the downloaded tag files

Section writer class

Merge

Update README file.

Update INSTALL file.

Many improvements in bfs.h, dfs.h and dijkstra.h
- Add run() function to Bfs and run(s,t) function to DfsVisit.
- Add debug checking to addSource() function of Dfs and DfsVisit.
- Add a few missing named parameters (according to \todo notes).
- Small fixes in the code (e.g. missing derivations).
- Many doc improvements.
- Remove \todo and \warning comments which are no longer valid.
- Remove \author commands (see ticket #39).
- Fixes in the the doc (e.g. wrong references).
- Hide the doc of most of the private and protected members.
- Use public typedefs instead of template parameters in public functions.
- Use better parameter names for some functions.
- Other small changes to make the doc more uniform.

Merge

Improve test/dim_test.cc

Improvements in dim2::BoundingBox (ticket #126)
- Rename the private varibles to start with underscore.
- Doc improvements.

Merge

Merge

Converting INVALID arc to INVALID edge

Fixing constness of Graph in GraphWriter

Unify the spelling of LEMON (#103).

Correcting changeSource interface and documentation

- The changeSource() and changeTarget() is renamed to changeU() and
changeV() in undirected graphs
- The changeSource(a, n) and changeTarget(a, n) is removed from
undirected graphs
- Correcting invalidating iterators in documentation

Erase in the documentation of list graphs

Unify DynArcLookUp interface (ticket #127)

Two bug fixes in DynArcLookUp

Merge

Fix ImmediateDetach in AlterationObserver (ticket #130)

Doc improvement in core.h (ticket #97)

Reworking graph testing

- The graph tests check more graph functionality.
- The petersen graph is too regular, therefore special graphs are used.
- The graph_test.h contains just general tools to test graphs.

Include CMake related files in the tarball.

Merge

CMake improvements.
- documentation generation with Doxygen
- installation support

Quote path names.

Fix compilation error when NDEBUG is defined.

Fixing bfs test (Ticket #128)

Merge

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap<G, K, V> is replaced with
ItemSetTraits<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

Turn off treeview in the doc.

make now recognises if Doxygen.in has updated. (Thanks to Akos)

Bug fix in assert.h (ticket #125)

Merge

Doc improvement for kruskal() (ticket #114)

Merge

Some cleanup in ArgParser API (ticket #116)

Merge

Fix the incorrect tab replacements of unify-sources.sh

Small fixes in graph_to_eps_demo.cc

Remove long lines (from all but one file)

Apply unify-sources.sh to the source tree

Better source unifier

- now it is called scripts/unify-sources.sh
- replaces each tab with 8 spaces
- remove trailing spaces (and tabs)
- warnings on long lines (i.e. on lines that are more than 80 characters)
- the standard file header now turns off the space-to-tab replacement in Emacs

Merge

Improvements related to graphToEps()

Merge

Doc improvements related to ArgParser

Cleaning of heap test and bug fix in heap concept check (ticket #100)

* The dijkstra heap test's digraph is inlined into the source file
* The random sequences are fixed
* The content of the header is moved to the source file
* Only the binary heap is checked

Merge

More docs for undirected LGF IO

Porting graph_copy_test.cc from SVN 3498

Bug fix in GraphCopy (ticket #117)