Edge routing problems

Shortest path methods

When applying the shortest path solver, one probably thinks of simple paths (paths not repeating any node). In fact, all paths / cycles / trees are represented by the predecessor labels which naturally imposes a restriction to simple paths or cycles. The label correcting codes technically determine walks (which possibly repeat arcs) rather than simple paths and fail if both notations diverge for this graph instance.

The method to compute shortest a path between two given nodes s and t heavily depends on the configuration of arc length labels and orientations. The following list shows the available codes in decreasing order of computational efficiency, and it is recommended to apply the first method which is feasible for the given instance:

• In the case of coinciding, non-negative length labels, a breadth first search is sufficient
• If the graph is directed acyclic, apply the DAG search method
• If all length labels are non-negative, apply the Dijkstra method
• If all negative length arcs are directed, apply a label-correcting method
• If the graph is undirected, apply the T-join method (with T={s,t})

The general NP-hard setting with negative length cycles is not handled by the library.

Most library methods determine a shortest path tree routed at a given source node s rather than a single shortest path between a given node pair s and t, and this tree is exported by the predecessor labels. Specifying a target node t is relevant for the BFS and the Dijkstra method since the seach can be finished prematurely, when t is reached the first time. Only the T-join method constructs an exports a single st-path.

The following figure shows an undirected graph and a shortest path between the red filled nodes. Since negative length edges exist, only the T-join method is formally applicable (undirected edges are interpreted as antiparallel arc pairs in the other codes). If one inspects the graph thoroughly, one finds a negative-length cycle. In general, the T-join method will be aborted when extracting the st-path from the T-join subgraph in such a situation. But if the minimum T-join is nothing else than an st-path, it is a shortest st-path:

[See API]

Minimum mean cycles

Several min-cost flow methods search for negative length cycles in the so-called residual network and push the maximum possible augment of flow on these cycles. If the cycles are arbitrary, the number of iterations cannot be bounded polynomially. But one obtains a strongly polynomial running time if the cycles are minimum mean cycles, that is, if the total edge length divided by the number of edges is minimal. Actually, this min-cost flow method has poor performance compared with the primal network simplex code. The core minimum mean cycle code is provided only to serve other applications in the future.

[See API]

Eulerian cycles and supergraphs

An Eulerian cycle is a cycle which meets every edge exactly once and which traverses every edge in a non-blocking direction. Graphs which admit such cycles are called Eulerian graphs. Due to the interpretation of arc capacities as arc multiplicities, and the fact that Eulerian cycles are stored like an ordering of the edge set, computing an Eulerian cycle requires that the upper capacity bounds are all one. If this is not the case, use sparseRepresentation::ExplicitParallels() for preprocessing.

The following is a so-called Sierpinksi triangle. This is a recursively defined, infinite graph, and Eulerian at any recurrency level. An Eulerian cycle is displayed both by the edge labels and the edge colours:

The well-known Chinese postman problem asks for an increase of the upper capacity bounds (interpreted as arc multiplicities) such that the graph becomes Eulerian and the length of an Eulerian cycle is minimal. In the undirected setting (and only then), it is equivalent to determine a maximum length Eulerian subgraph. The library handles the directed and the undirected case, but not the generalized NP-hard problem for mixed graphs.

For the above graph, with the shown length labels and unit capacities, the following picture shows a maximum Eulerian subgraph in bold face, and a minimum length Eulerian augmentation:

[See API]

Related topics

• Network flows
• Matchings & T-Joins

Return to main page