The above produces correct results, but after the algorithm terminates it leaves the graph with the augmented edges that were added using ReversedEdgeAugmentorAlgorithm. There should be a way to remove those edges.
In QuickGraph/src/QuickGraph/Algorithms/MaximumBipartiteMatchingAlgorithm.cs we see that ReversedEdgeAugmentorAlgorithm is instantiated outside the constructor of EdmondsKarpMaximumFlowAlgorithm and then RemoveReversedEdges() is called a finally block.
reverser = new ReversedEdgeAugmentorAlgorithm<TVertex, TEdge>(
this,
this.VisitedGraph,
this.EdgeFactory
);
reverser.AddReversedEdges();
if (cancelManager.IsCancelling)
return;
...
// compute maxflow
var flow = new EdmondsKarpMaximumFlowAlgorithm<TVertex, TEdge>(
this,
this.VisitedGraph,
e => 1,
this.EdgeFactory
);
...
finally
{
if (reverser != null && reverser.Augmented)
{
reverser.RemoveReversedEdges();
reverser = null;
}
...
}
The call to RemoveReversedEdges() removes the augmented edges. But ReversedEdgeAugmentorAlgorithm is not passed to EdmondsKarpMaximumFlowAlgorithm, as a result EdmondsKarpMaximumFlowAlgorithm computes incorrect maximum flows, see #183.
I don't know how to correctly implement the removing of edges/disposing of ReversedEdgeAugmentorAlgorithm.
In the fix proposed in #183, ReversedEdgeAugmentorAlgorithm.Dispose() could be called after the max flow algorithm terminates. But then, one could not have access to the residual capacities afterwards (think min cut).
In contrast to the proposed fix in #183, the constructor of EdmondsKarpMaximumFlowAlgorithm could be overloaded to take an instance of ReversedEdgeAugmentorAlgorithm. (This seems OK to me and this is how it was implemented in an earlier version of QuickGraph, see #183. But obviously, for some reason that is above my head, the choice for a different implementation was made.)
The user then would have to call RemoveReversedEdges() or Dispose(), analogous to the way it is implemented in QuickGraph/src/QuickGraph/Algorithms/MaximumBipartiteMatchingAlgorithm.cs.
A followup on #183 and #184.
The above produces correct results, but after the algorithm terminates it leaves the graph with the augmented edges that were added using ReversedEdgeAugmentorAlgorithm. There should be a way to remove those edges.
In QuickGraph/src/QuickGraph/Algorithms/MaximumBipartiteMatchingAlgorithm.cs we see that ReversedEdgeAugmentorAlgorithm is instantiated outside the constructor of EdmondsKarpMaximumFlowAlgorithm and then RemoveReversedEdges() is called a finally block.
The call to RemoveReversedEdges() removes the augmented edges. But ReversedEdgeAugmentorAlgorithm is not passed to EdmondsKarpMaximumFlowAlgorithm, as a result EdmondsKarpMaximumFlowAlgorithm computes incorrect maximum flows, see #183.
I don't know how to correctly implement the removing of edges/disposing of ReversedEdgeAugmentorAlgorithm.
In the fix proposed in #183, ReversedEdgeAugmentorAlgorithm.Dispose() could be called after the max flow algorithm terminates. But then, one could not have access to the residual capacities afterwards (think min cut).
In contrast to the proposed fix in #183, the constructor of EdmondsKarpMaximumFlowAlgorithm could be overloaded to take an instance of ReversedEdgeAugmentorAlgorithm. (This seems OK to me and this is how it was implemented in an earlier version of QuickGraph, see #183. But obviously, for some reason that is above my head, the choice for a different implementation was made.) The user then would have to call RemoveReversedEdges() or Dispose(), analogous to the way it is implemented in QuickGraph/src/QuickGraph/Algorithms/MaximumBipartiteMatchingAlgorithm.cs.
I added the latter, alternative fix in #184.