Peter Kovacs <kpeter@inf.elte.hu> [Tue, 02 Mar 2010 10:27:47 +0100] rev 858
Also test fullInit() in suurballe_test (#181, #323)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 16 Oct 2009 09:35:46 +0200] rev 857
Add traits class + named parameters to Suurballe (#323)
The following types can be modified using named parameters:
- FlowMap
- PotentialMap
- Path
- Heap + HeapCrossRef
Alpar Juttner <alpar@cs.elte.hu> [Wed, 03 Mar 2010 17:14:17 +0000] rev 856
Merge #181, #323
Peter Kovacs <kpeter@inf.elte.hu> [Tue, 29 Sep 2009 13:32:01 +0200] rev 855
Rename heap structures (#301)
- KaryHeap --> DHeap
- FouraryHeap --> QuadHeap
- BinomHeap --> BinomialHeap
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 16 Oct 2009 02:32:30 +0200] rev 854
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.
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 16 Oct 2009 01:06:16 +0200] rev 853
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.
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 15 Oct 2009 21:04:50 +0200] rev 852
Remove unnecessary integer requirement in Suurballe (#323)
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 15 Oct 2009 21:03:17 +0200] rev 851
Bug fix in Suurballe (#323)
Alpar Juttner <alpar@cs.elte.hu> [Mon, 01 Mar 2010 07:51:45 +0100] rev 850
Configurable glpk prefix in ./scripts/bootstrap.sh and ...
unneeded solver backends are explicitely switched off with --without-*
Alpar Juttner <alpar@cs.elte.hu> [Sun, 28 Feb 2010 20:52:08 +0100] rev 849
Merge #342
Peter Kovacs <kpeter@inf.elte.hu> [Sun, 14 Feb 2010 19:06:07 +0100] rev 848
Improve README and mainpage.dox (#342)
Alpar Juttner <alpar@cs.elte.hu> [Sun, 28 Feb 2010 19:58:24 +0100] rev 847
Merge #347
Peter Kovacs <kpeter@inf.elte.hu> [Sat, 20 Feb 2010 16:51:43 +0100] rev 846
Use 'long long' flow cost in dimacs-solver.cc (#347)
Alpar Juttner <alpar@cs.elte.hu> [Sun, 28 Feb 2010 19:38:29 +0100] rev 845
Merge
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 19 Feb 2010 14:08:32 +0100] rev 844
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.
Alpar Juttner <alpar@cs.elte.hu> [Sun, 28 Feb 2010 19:23:01 +0100] rev 843
Merge #332
Alpar Juttner <alpar@cs.elte.hu> [Sun, 14 Feb 2010 19:23:55 +0100] rev 842
ArgParser can throw exception instead of exit(1) (#332)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 26 Feb 2010 23:53:09 +0100] rev 841
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.
Alpar Juttner <alpar@cs.elte.hu> [Fri, 26 Feb 2010 14:00:20 +0100] rev 840
Merge #340
Peter Kovacs <kpeter@inf.elte.hu> [Sat, 20 Feb 2010 18:39:03 +0100] rev 839
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.
Alpar Juttner <alpar@cs.elte.hu> [Sun, 21 Feb 2010 18:55:30 +0100] rev 838
Merge bugfix #336
Alpar Juttner <alpar@cs.elte.hu> [Thu, 11 Feb 2010 10:02:11 +0100] rev 837
Fix the date field comment of graphToEps() output (#336)
Peter Kovacs <kpeter@inf.elte.hu> [Wed, 17 Feb 2010 23:10:36 +0100] rev 836
Modify the header of scripts/bib2dox.py (#184)
Alpar Juttner <alpar@cs.elte.hu> [Mon, 15 Feb 2010 09:03:11 +0100] rev 835
Merge
Balazs Dezso <deba@inf.elte.hu> [Thu, 10 Dec 2009 09:09:08 +0100] rev 834
Fix LpBase::addRow(Constr) (#334)
Balazs Dezso <deba@inf.elte.hu> [Sun, 14 Feb 2010 23:14:09 +0100] rev 833
Merge bugfix #337
Balazs Dezso <deba@inf.elte.hu> [Sun, 14 Feb 2010 23:10:24 +0100] rev 832
Use void* like LPX object (#337)
Alpar Juttner <alpar@cs.elte.hu> [Fri, 12 Feb 2010 22:24:26 +0100] rev 831
Merge
Peter Kovacs <kpeter@inf.elte.hu> [Wed, 10 Feb 2010 19:05:20 +0100] rev 830
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.
Alpar Juttner <alpar@cs.elte.hu> [Fri, 12 Feb 2010 22:17:20 +0100] rev 829
Merge
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 11 Feb 2010 07:40:29 +0100] rev 828
Doc improvements for planarity related tools (#62)
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 11 Feb 2010 07:39:57 +0100] rev 827
Port planar image from SVN -r3524 (#62)
Alpar Juttner <alpar@cs.elte.hu> [Fri, 12 Feb 2010 21:53:15 +0100] rev 826
Merge
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 12 Feb 2010 11:00:20 +0100] rev 825
Add doc for the traits class parameters (#315)
Akos Ladanyi <ladanyi@tmit.bme.hu> [Thu, 11 Feb 2010 16:55:54 +0000] rev 824
Add more information on Makefile variables (#316)
Peter Kovacs <kpeter@inf.elte.hu> [Tue, 09 Feb 2010 23:29:51 +0100] rev 823
Add a warning about huge capacities in Preflow (#319)
Alpar Juttner <alpar@cs.elte.hu> [Mon, 14 Dec 2009 06:07:52 +0100] rev 822
Merge #180 and a bugfix in #51
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 00:39:28 +0100] rev 821
Small bug fixes (#180)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 00:37:55 +0100] rev 820
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.
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 00:24:39 +0100] rev 819
Adds tests for the new MCF algorithms (#180)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 00:23:07 +0100] rev 818
Rework the MCF test file to help extending it (#180)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 00:15:50 +0100] rev 817
Fixes in the heap concept to avoid warnings (#180)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 00:11:11 +0100] rev 816
Add citations to CycleCanceling (#180, #184)
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 00:10:33 +0100] rev 815
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.
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 00:09:35 +0100] rev 814
Port cycle canceling algorithms from SVN -r3524 (#180)
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:52:51 +0100] rev 813
Add citations to the scaling MCF algorithms (#180, #184)
and improve the doc of their group.
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:49:05 +0100] rev 812
Small doc improvements + unifications in MCF classes (#180)
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:45:15 +0100] rev 811
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.
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:34:35 +0100] rev 810
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.
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:30:45 +0100] rev 809
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.
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:29:42 +0100] rev 808
Port CostScaling from SVN -r3524 (#180)
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:27:21 +0100] rev 807
Traits class + a named parameter for CapacityScaling (#180)
to specify the heap used in internal Dijkstra computations.
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:26:13 +0100] rev 806
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.
Peter Kovacs <kpeter@inf.elte.hu> [Thu, 12 Nov 2009 23:17:34 +0100] rev 805
Port CapacityScaling from SVN -r3524 (#180)
Peter Kovacs <kpeter@inf.elte.hu> [Sun, 13 Dec 2009 22:19:08 +0100] rev 804
Memory leak bugfix in BellmanFord (#51)
Alpar Juttner <alpar@cs.elte.hu> [Thu, 10 Dec 2009 17:18:25 +0100] rev 803
Merge bugfix #330
Alpar Juttner <alpar@cs.elte.hu> [Thu, 10 Dec 2009 17:05:35 +0100] rev 802
Merge
Peter Kovacs <kpeter@inf.elte.hu> [Fri, 13 Nov 2009 12:33:33 +0100] rev 801
Bug fix in map_extender.h (#330)
Balazs Dezso <deba@inf.elte.hu> [Thu, 10 Dec 2009 09:14:47 +0100] rev 800
Fix clear() function in ExtendFindEnum (#335)
Alpar Juttner <alpar@cs.elte.hu> [Wed, 09 Dec 2009 11:14:06 +0100] rev 799
Merge #62