Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Properly disposing of ReversedEdgeAugmentorAlgorithm #185

Closed
ktnr opened this issue Nov 6, 2018 · 0 comments
Closed

Properly disposing of ReversedEdgeAugmentorAlgorithm #185

ktnr opened this issue Nov 6, 2018 · 0 comments

Comments

@ktnr
Copy link
Contributor

ktnr commented Nov 6, 2018

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.

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.

I added the latter, alternative fix in #184.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants