Member in Circulation to transform the solution to a basic one

[Alpar Juttner]

Having a basic solution for the circulation problem is sometime quite useful, e.g. it can be used as a staring solution of the primal Network Simplex algorithm.

The interface should also provide the tree (or forest) of the basis.

[Peter Kovacs]

Replying to alpar:

Having a basic solution for the circulation problem is sometime quite useful,

Maybe we should implement a separate class that could transform any flow to a cycle-free one. It could be combined either with Circulation or any max. flow algorithm (Preflow, EdmondsKarp etc.).

e.g. it can be used as a staring solution of the primal Network Simplex algorithm.

Note, that a starting solution for NetworkSimplex needs different cycle-free property than other applications. I think in most cases a flow (or circulation) is called cycle-free, if the arcs with positive flow value don't form directed cycles. However NS needs a flow in which the arcs with such a flow value that can be modified in both directions (i.e. it is not zero and less than the capacity) don't form a cycle in undirected manner.

In fact, both requirements can be satisfied using almost the same algorithm. I have already implemented such a method inside a minimum cost flow algorithm, but I haven't pushed it to the LEMON repository, yet.

[Alpar Juttner]

Replying to kpeter:

Maybe we should implement a separate class that could transform any flow to a cycle-free one. It could be combined either with Circulation or any max. flow algorithm (Preflow, EdmondsKarp etc.).

As you rightly noticed below, the problem are not exactly the same for max. flow and for circulations.

e.g. it can be used as a staring solution of the primal Network Simplex algorithm.

Note, that a starting solution for NetworkSimplex needs different cycle-free property than other applications. I think in most cases a flow (or circulation) is called cycle-free, if the arcs with positive flow value don't form directed cycles.

Not really, the expression "cycle free" makes no sense for circulations, but only for flows (more exactly where the arc lower bounds are 0 everywhere).

Notice the important difference between the notion "cycle free" (in your answer) and "without free cycle" (in the ticket title). This later one is equivalent with the "basic solution" which is needed by the simplex like algorithms, and by many other problems, and it is also meaningful for the flow problems. A "cycle free" solution (for flows) is something more.

However NS needs a flow in which the arcs with such a flow value that can be modified in both directions (i.e. it is not zero and less than the capacity) don't form a cycle in undirected manner.

So, it has nothing to do with NS vs. other algorithms but the the circulations problems vs. flow problem. In the latter case we sometimes interested in a special basic solution (i.e. a "cycle free" one).

[Peter Kovacs]

Replying to alpar:

As you rightly noticed below, the problem are not exactly the same for max. flow and for circulations.

I think there are two independent definitons of a "flow without cycles":

1. A flow without directed cycles consisting of arcs with positive flow value (here the lower bounds should be zero on all arcs).
2. A flow without undirected cycles consisting of "free arcs", i.e. arcs with flow value that is strictly larger than the lower bound and strictly less than the upper bound. So there are no cycles on which the flow value could be modified in both directions.

Here I call "flow" all kind of flows and circualtions.

Both concepts are suitable for either max. flows, feasible circulations, min. cost flows (with given supply-demand constraints) or min. cost max. flows (if all lower bounds are zero). Sometimes we need the first one, sometimes we need the second one.

Suppose you have a max. flow on a digraph (e.g. you get it by using Preflow). It is a natural request to have such a max. flow that doesn't contain unnecessary "flow cycles", so a max. flow that conforms to the first concept. On the other hand if you would like to transform your solution into a min. cost max. flow (e.g. with a network simplex method), than you need a max. flow that conforms to the second concept.

That's why I don't support introducing these transforming methods into one or more existing algorithms. I prefer having separate tools for that. These algorithms needn't know what kind of flow or circulation they have to make cycle free (according to one of the above concepts), since they don't modify the difference between the outgoing and incoming flow of each nodes.

Not really, the expression "cycle free" makes no sense for circulations, but only for flows (more exactly where the arc lower bounds are 0 everywhere).

That's a special case for circulations. Now a flow having non-zero lower bounds is called "flow" if it has costs and called "circulation" otherwise. In fact, these notions are equivalent. I don't want to make strict difference, since a lot of papers and books use "flow", and some works use "circulation". I accept if the algorithm class is called Circulation, although I could imagine something with "flow", e.g. FeasibleFlow, GeneralFlow etc. Circulation is better only because it is shorter and simpler. But I do want to be allowed to call "flow" the result of Circulation. Since it is also a kind of flow.

Notice the important difference between the notion "cycle free" (in your answer) and "without free cycle" (in the ticket title).

It was not clear for me how you used these namings. I tried to make everything clear above.

A "cycle free" solution (for flows) is something more.

No, neither of them is stronger than the other. There are flows that conform to the 1st concept, but don't conform to the 2nd concept, and vice versa.

So, it has nothing to do with NS vs. other algorithms but the the circulations problems vs. flow problem.

Definitely not. That is an incorrect separation. See the reasons above.

[Peter Kovacs]

As both of us described above, there are two similar but different definitions of particular importance.

1. The "cycle free" property can only be applied to flows/circulations with zero lower bounds, it is discussed in #217.
2. The "without free cycles" property is needed for the basic solutions of NetworkSimplex. But if we would like to use an initial solution for NS, then it probably worth to use the arc costs for the transformation to determine the better (cheaper) direction when a cycle is removed. However, we don't have costs in Circulation, thus I find it better to have this transformation inside NS. Assuming this, would we also need a similar function in Circulation without the usage of arc costs?

[Peter Kovacs]

I suggest a class called CycleFreeFlow or AcyclicFlow for the first problem, which should be able to give a path decomposition, as well (see #217, #218). This class could be used in combination with any max. flow algorithm and even with Circulation or min. cost flow algorithms if all lower bounds are zero (and the costs are non-negative).

I don't find the second problem so important (except for the usage in NS). However, we could also have a class for that, if we want. It could be called BasicCirculation or something similar.