summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files | bz2 | zip | gz |
help

(0) -300 -100 -30 -10 +10 +30 +100 +300 tip

(0) -300 -100 -30 -10 +10 +30 +100 +300 tip

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.

- 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.

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.

- 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.

- 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.

- 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.

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.

- 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.