Using problem solvers

Solving max-flow instances

To call a problem solver, one usually can choose from two interface functions. To the one function, a mathematical method is explicitly specified. The second function looks up the preferred mathematical method in the goblinController default settings.

It is unwanted to call a mathematical implementation method directly, since some code is method independent, and centralized in the interface function. In the max-flow case, the mathematical implementation methods apply to digraphs only. The interface function handles the flow values of undirected edges.

The codes

    TCap flowValue = G.MaxFlow(MXF_SAP_SCALE,source,target);


    G.Context().methMaxFlow = G.MXF_SAP_SCALE;
    TCap flowValue = G.MaxFlow(source,target);

are equivalent up to the obvious side-effect of the second code: Later calls of the max-flow solver would also apply the capacity scaling method. This tells that the first version is best practice.

As other solvers, the max-flow solver returns an objective value, and stores the found solutions object internally: The flow is maintained by the subgraph multiplicities, and the dual solution (a minimum edge cut) by the node distance labels". When the object is saved to file, the solutions are also saved.

If the max-flow solver is called again, it starts from the existing subgraph. This might be unwanted, especially in the case of changing source and target nodes:

    sparseDiGraph G(filename);
    TCap lambda = InfCap;
    for (TNode source=0;source<n;++source)
       TNode target = (source+1)%n;
       TCap flowValue = G.MaxFlow(source,target);
       if (flowValue < lambda) lambda = flowValue;

This procedure loads a sparseDiGraph G from file and then determines the strong edge connectivity number of G as the final value of lambda. The flow of the previous iteration is infeasible as a starting solution, since all nodes other than the source and the target must be balanced. The abstractMixedGraph::InitSubgraph() operation reverts to a zero flow - but only if the lower capacity bounds are all zero. Most likely, the lines

    sparseDiGraph G(filename);
    static_cast<sparseRepresentation*>(G.Representation()) -> SetCUCap(1);
    static_cast<sparseRepresentation*>(G.Representation()) -> SetCLCap(0);
    static_cast<sparseRepresentation*>(G.Representation()) -> SetCDemand(0);

should be added to obtain the expected result. The graphRepresentation::SetCDemand() call is necessary when the goblinController::methFailSave option is set: Then the max-flow solver verifies on exit if the node demands and flow imbalances match.

The max-flow solver can deal with infinite capacity bounds. But if the lower capacity bounds are non-trivial, the solver must be supplied with a starting solution, by calling abstractMixedGraph::AdmissibleBFlow(). This evaluates the node demands, and calls the max-flow solver for a digraphToDigraph instance (but this is only an implementational detail).

Further reading:

Solving shortest path instances

The determination of shortest paths between two graph nodes is probably the most fundamental task in graph optimization. It forms part of many other graph optimization methods, several min-cost flow methods for example. Usually, it is assumed that all edge lengths are non-negative. If so, the well-known Dijkstra method applies, and this is elementary in that it does not depend on any library configuration parameters. In the setting with negative edge lengths, selecting an adequate methods takes much more care.

Hiding all technical details, the basic application of the shortest path solver is as follows:

    if (ShortestPath(source,target))
       TFloat dt = Dist(target);
       TArc pred = GetPredecessors();
       TNode v = target;
       do {
          TArc a = pred[v];
          v = StartNode(a);
       while (v!=source);

The return value of abstractMixedGraph::ShortestPath() tells whether the target node can be accessed on an eligible path from the source node. In occasion, the determined path is stored by the Predecessor labels, and the path length can be retrieved by the abstractMixedGraph::Dist() function which is short-hand for accessing the Distance labels. The loop does nothing else than traversing this path back from the target node to the source node.

A first technical explanation concerns the definition of eligible arcs: In the default setting as above, directed arcs may be traversed only one-way, but undirected edge can be traversed in both directions. By using other interface methods, one might modify this eligibily rule:

would determine a path in the current subgraph. This path does not minimize the sum of edge length but only the number of path edges, as it is computed by breadth-first search. This code is roughly the same as
but the latter method requires uniform edge lengths.

There is a strong impact of method selection and solver configuration on the performance:

At the time, there is no implementation to handle the very general setting of mixed graphs with negative edge lengths. This setting is equivalent with the longest path problem in the literature, which can be considered hard to solve.

Even if such a general method would exist, it would be no good idea to apply it by default. There are a lot of applications which can guarantee non-negativity of the edge lengths, and hence can solved by the Dijkstra method.

But what is special about the non-negative edge length setting? To understand this, consider the difference between walks (a series of adjacent arcs), paths (walks without arc repetitions) and simple paths (walks without node repetitions):

The predecessor labels register can only represent simple paths, and those are the intended output of the shortest path solver. Technically, all methods which deal with negative edge lengths operate on paths rather than simple paths. If no negative length subcycle exists in the found path, it can be reduced to a simple path of the same length.

Accepting negative edge lengths, the following cases can be solved efficiently:

Further reading: