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)