Tue, 12 May 2009 12:06:40 +0200Fix the GEQ/LEQ handling in NetworkSimplex + improve doc (#291)
Peter Kovacs <kpeter@inf.elte.hu> [Tue, 12 May 2009 12:06:40 +0200] rev 663
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.

Mon, 11 May 2009 16:38:21 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Mon, 11 May 2009 16:38:21 +0100] rev 662
Merge

Sat, 09 May 2009 16:47:26 +0200Remove bits/base_extender.h, which is not used at all (#288)
Peter Kovacs <kpeter@inf.elte.hu> [Sat, 09 May 2009 16:47:26 +0200] rev 661
Remove bits/base_extender.h, which is not used at all (#288)

Mon, 11 May 2009 17:04:40 +0200Move list and edge sets to the graph module (#290)
Peter Kovacs <kpeter@inf.elte.hu> [Mon, 11 May 2009 17:04:40 +0200] rev 660
Move list and edge sets to the graph module (#290)

Mon, 11 May 2009 15:48:37 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Mon, 11 May 2009 15:48:37 +0100] rev 659
Merge

Mon, 11 May 2009 16:42:42 +0200Change the explanation of the acronym LEMON (#289)
Peter Kovacs <kpeter@inf.elte.hu> [Mon, 11 May 2009 16:42:42 +0200] rev 658
Change the explanation of the acronym LEMON (#289)

Sat, 09 May 2009 16:39:59 +0200Change Graph::Edge -> Graph::Arc inheritance to conversion (#283)
Peter Kovacs <kpeter@inf.elte.hu> [Sat, 09 May 2009 16:39:59 +0200] rev 657
Change Graph::Edge -> Graph::Arc inheritance to conversion (#283)

Thu, 07 May 2009 10:46:49 +0200Change Undirector::Edge -> Undirector::Arc inheritance to conversion (#283)
Balazs Dezso <deba@inf.elte.hu> [Thu, 07 May 2009 10:46:49 +0200] rev 656
Change Undirector::Edge -> Undirector::Arc inheritance to conversion (#283)

Fri, 08 May 2009 16:21:06 +0100Fix the faulty merge of unify-sources.sh in [586b65073025]
Alpar Juttner <alpar@cs.elte.hu> [Fri, 08 May 2009 16:21:06 +0100] rev 655
Fix the faulty merge of unify-sources.sh in [586b65073025]

Fri, 08 May 2009 13:15:29 +0200Doc fixes for lgf-gen (#282)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 08 May 2009 13:15:29 +0200] rev 654
Doc fixes for lgf-gen (#282)

Thu, 07 May 2009 12:21:00 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Thu, 07 May 2009 12:21:00 +0100] rev 653
Merge

Thu, 07 May 2009 12:19:41 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Thu, 07 May 2009 12:19:41 +0100] rev 652
Merge

Thu, 07 May 2009 02:07:59 +0200Small doc improvements (#257)
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 07 May 2009 02:07:59 +0200] rev 651
Small doc improvements (#257)

Thu, 07 May 2009 11:53:49 +0200Fix glp_prob definition (#286)
Balazs Dezso <deba@inf.elte.hu> [Thu, 07 May 2009 11:53:49 +0200] rev 650
Fix glp_prob definition (#286)

Wed, 06 May 2009 14:46:05 +0200Add a test file for the connectivity functions (#285)
Peter Kovacs <kpeter@inf.elte.hu> [Wed, 06 May 2009 14:46:05 +0200] rev 649
Add a test file for the connectivity functions (#285)
The Euler tools have a separate test file.

Wed, 06 May 2009 14:44:05 +0200Doc improvements and fixes for connectivity tools (#285)
Peter Kovacs <kpeter@inf.elte.hu> [Wed, 06 May 2009 14:44:05 +0200] rev 648
Doc improvements and fixes for connectivity tools (#285)
And add loopFree(), parallelFree(), simpleGraph() to the module doc.

Wed, 06 May 2009 14:37:44 +0200Bug fixes in connectivity.h (#285)
Peter Kovacs <kpeter@inf.elte.hu> [Wed, 06 May 2009 14:37:44 +0200] rev 647
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().

Wed, 29 Apr 2009 19:22:14 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Wed, 29 Apr 2009 19:22:14 +0100] rev 646
Merge

Wed, 29 Apr 2009 16:15:29 +0100Add the solver libraries to lemon.pc.in (#281)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Wed, 29 Apr 2009 16:15:29 +0100] rev 645
Add the solver libraries to lemon.pc.in (#281)

Wed, 29 Apr 2009 17:48:41 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Wed, 29 Apr 2009 17:48:41 +0100] rev 644
Merge

Wed, 29 Apr 2009 17:48:18 +0100Resolve gcc-4.3 warning in lemon/network_simplex.h
Alpar Juttner <alpar@cs.elte.hu> [Wed, 29 Apr 2009 17:48:18 +0100] rev 643
Resolve gcc-4.3 warning in lemon/network_simplex.h

Wed, 29 Apr 2009 16:54:27 +0200Less map copying in NetworkSimplex (#234)
Peter Kovacs <kpeter@inf.elte.hu> [Wed, 29 Apr 2009 16:54:27 +0200] rev 642
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.

Wed, 29 Apr 2009 14:25:51 +0200Rename Flow to Value in the flow algorithms (#266)
Peter Kovacs <kpeter@inf.elte.hu> [Wed, 29 Apr 2009 14:25:51 +0200] rev 641
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.

Wed, 29 Apr 2009 03:15:24 +0200Support negative costs and bounds in NetworkSimplex (#270)
Peter Kovacs <kpeter@inf.elte.hu> [Wed, 29 Apr 2009 03:15:24 +0200] rev 640
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.

Wed, 29 Apr 2009 16:55:27 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Wed, 29 Apr 2009 16:55:27 +0100] rev 639
Merge

Tue, 28 Apr 2009 11:25:47 +0100Check the version number in FindGLPK (#277)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Tue, 28 Apr 2009 11:25:47 +0100] rev 638
Check the version number in FindGLPK (#277)

Mon, 27 Apr 2009 18:05:04 +0100Add GLPK_ROOT_DIR variable to FindGLPK (#277)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Mon, 27 Apr 2009 18:05:04 +0100] rev 637
Add GLPK_ROOT_DIR variable to FindGLPK (#277)

Tue, 28 Apr 2009 11:55:43 +0100Link libm and libpthread if using CPLEX (#277)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Tue, 28 Apr 2009 11:55:43 +0100] rev 636
Link libm and libpthread if using CPLEX (#277)

Mon, 27 Apr 2009 18:03:18 +0100Add CPLEX_ROOT_DIR variable to FindCPLEX (#277)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Mon, 27 Apr 2009 18:03:18 +0100] rev 635
Add CPLEX_ROOT_DIR variable to FindCPLEX (#277)

Tue, 28 Apr 2009 14:47:25 +0100Look for COIN libraries with and without the lib prefix too (#277)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Tue, 28 Apr 2009 14:47:25 +0100] rev 634
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.

Wed, 29 Apr 2009 15:54:30 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Wed, 29 Apr 2009 15:54:30 +0100] rev 633
Merge

Wed, 29 Apr 2009 15:52:08 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Wed, 29 Apr 2009 15:52:08 +0100] rev 632
Merge

Tue, 28 Apr 2009 16:44:48 +0100Remove superfluous HAVE_CONFIG_H (#278)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Tue, 28 Apr 2009 16:44:48 +0100] rev 631
Remove superfluous HAVE_CONFIG_H (#278)

Tue, 28 Apr 2009 16:49:57 +0100Add cbc.h to lemon/Makefile.am (#279)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Tue, 28 Apr 2009 16:49:57 +0100] rev 630
Add cbc.h to lemon/Makefile.am (#279)

Tue, 28 Apr 2009 12:54:59 +0200Fix Makefile.am EXTRA_DIST (#276)
Balazs Dezso <deba@inf.elte.hu> [Tue, 28 Apr 2009 12:54:59 +0200] rev 629
Fix Makefile.am EXTRA_DIST (#276)

Tue, 28 Apr 2009 14:01:00 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Tue, 28 Apr 2009 14:01:00 +0100] rev 628
Merge

Tue, 28 Apr 2009 13:51:34 +0100Merge and extend the fix of #275
Akos Ladanyi <ladanyi@tmit.bme.hu> [Tue, 28 Apr 2009 13:51:34 +0100] rev 627
Merge and extend the fix of #275

Sun, 26 Apr 2009 16:36:23 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Sun, 26 Apr 2009 16:36:23 +0100] rev 626
Merge

Sun, 26 Apr 2009 16:44:53 +0200Modify the interface of MinCostArborescence + improvements (#267)
Peter Kovacs <kpeter@inf.elte.hu> [Sun, 26 Apr 2009 16:44:53 +0200] rev 625
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.

Sat, 25 Apr 2009 17:51:09 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Sat, 25 Apr 2009 17:51:09 +0100] rev 624
Merge

Sat, 25 Apr 2009 02:12:41 +0200Modify the interface of Suurballe (#266, #181)
Peter Kovacs <kpeter@inf.elte.hu> [Sat, 25 Apr 2009 02:12:41 +0200] rev 623
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.

Sat, 25 Apr 2009 18:25:59 +0200Support infinite bounds in Circulation + fixes (#270, #266)
Peter Kovacs <kpeter@inf.elte.hu> [Sat, 25 Apr 2009 18:25:59 +0200] rev 622
Support infinite bounds in Circulation + fixes (#270, #266)

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

Thu, 23 Apr 2009 07:30:40 +0100FindCOIN for CMake (#256)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Thu, 23 Apr 2009 07:30:40 +0100] rev 621
FindCOIN for CMake (#256)

Thu, 23 Apr 2009 07:29:50 +0100FindCPLEX for CMake (#256)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Thu, 23 Apr 2009 07:29:50 +0100] rev 620
FindCPLEX for CMake (#256)

Thu, 23 Apr 2009 07:28:56 +0100FindGLPK improvements (#256)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Thu, 23 Apr 2009 07:28:56 +0100] rev 619
FindGLPK improvements (#256)

Fri, 24 Apr 2009 12:12:14 +0100Merge
Alpar Juttner <alpar@cs.elte.hu> [Fri, 24 Apr 2009 12:12:14 +0100] rev 618
Merge

Fri, 24 Apr 2009 11:54:48 +0200Fix and uniform the usage of Graph and Parent typedefs (#268)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 24 Apr 2009 11:54:48 +0200] rev 617
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.

Fri, 24 Apr 2009 10:15:33 +0200VS compatibility fix (#268)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 24 Apr 2009 10:15:33 +0200] rev 616
VS compatibility fix (#268)

Fri, 24 Apr 2009 12:23:53 +0200Exploit the changes of #190 in MCF test file (#234, #190)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 24 Apr 2009 12:23:53 +0200] rev 615
Exploit the changes of #190 in MCF test file (#234, #190)

Fri, 24 Apr 2009 12:23:17 +0200Support LEQ and GEQ supply constraints in dimacs-solver (#234, #219)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 24 Apr 2009 12:23:17 +0200] rev 614
Support LEQ and GEQ supply constraints in dimacs-solver (#234, #219)

Fri, 24 Apr 2009 12:22:06 +0200Bug fix in NetworkSimplex (#234)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 24 Apr 2009 12:22:06 +0200] rev 613
Bug fix in NetworkSimplex (#234)

Thu, 23 Apr 2009 10:44:35 +0100Fix usage of sqrt() (#268)
Alpar Juttner <alpar@cs.elte.hu> [Thu, 23 Apr 2009 10:44:35 +0100] rev 612
Fix usage of sqrt() (#268)

Tue, 21 Apr 2009 15:18:54 +0100Merge and fix
Alpar Juttner <alpar@cs.elte.hu> [Tue, 21 Apr 2009 15:18:54 +0100] rev 611
Merge and fix

Fri, 17 Apr 2009 18:14:35 +0200Slightly modify the interface of Circulation and Preflow (#266)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 17 Apr 2009 18:14:35 +0200] rev 610
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.

Fri, 17 Apr 2009 18:04:36 +0200Support >= and <= constraints in NetworkSimplex (#219, #234)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 17 Apr 2009 18:04:36 +0200] rev 609
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.

Fri, 03 Apr 2009 18:59:15 +0200Support real types + numerical stability fix in NS (#254)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 03 Apr 2009 18:59:15 +0200] rev 608
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.