CODEWITHSUNDEEP
algorithmgraphdirected-graphjgrapht
Sebastian
Sebastian

Reputation: 315

Compute all edge-disjoint paths between two given vertices of a simple directed graph

Many similar questions have been asked, but non addresses exactly my situation: Given two vertices in a simple directed unweighed graph, and an integer k, how can I find all k-tuples of edge-disjoint paths between the vertices? (In particular, I'm interested in the case that k is the outdegree of the start vertex.)

I know Suurballe's algorithm will give me k edge-disjoint paths, but it will (non-deterministically) settle on one solution, instead of giving me all of them.

It seems maximum-flow algorithms like Edmonds-Karp are related, but they don't compute paths.

Is there any algorithm already in JGraphT that does what I want?

Upvotes: 2

Views: 667

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65468

Here's a simple recursive method:

if k is 0, output [] and return
otherwise, choose an arbitrary arc from the source vertex
for all paths p that start with that arc and end at the sink,
    for all k-1 tuples T in the graph where the arcs in p are removed,
        output [p] + T

This method can be improved by pruning parts of the recursion tree. The easiest idea is to remove all arcs to the source vertex, since if a path uses two arcs from the source vertex, we won't get to k before disconnecting the source and sink.

A broader version of that idea uses maximum flow to identify arcs that can be part of a solution. Compute the max flow from the source to the sink. By the flow decomposition theorem, there is at least one k-tuple of edge disjoint paths if and only if the value of the flow is at least k. If these conditions are true, then there is a solution that uses the set of arcs carrying flow, so this set needs to be retained. To test the others, compute the strongly connected components of the residual graph (arcs without flow appear forward, arcs with flow appear backward). All arcs without flow that go from one SCC to another can be safely discarded.

Upvotes: 2

Related Questions