Value types break EdmondsKarpMaximumFlowAlgorithm (and potentially others)

[ktnr]

EdmondsKarpMaximumFlowAlgorithm works fine if TEdge is a reference type, e.g. Edge<TVertex> or TaggedEdge<TVertex>. If, however, TEdge is a value type (e.g. STaggedEdge or STaggedEquatableEdge) the algorithm fails:

In ReversedEdgeAugmentorAlgorithm<TVertex, TEdge> the method

private TEdge FindReversedEdge(TEdge edge)
{
    foreach (var redge in this.VisitedGraph.OutEdges(edge.Target))
        if (redge.Target.Equals(edge.Source))
            return redge;
    return default(TEdge);
}

returns default(TEdge). If TEdge is a reference type default(TEdge) returns null... So, the check on line 97 in ReversedEdgeAugmentorAlgorithm<TVertex, TEdge>.AddReversedEdges() if (reversedEdge != null) is valid. If, however, TEdge is a value type, then default(TEdge) returns null->null and the check on line 97 becomes invalid. The next check on line 102 if (!this.reversedEdges.ContainsKey(reversedEdge)) will then throw a System.NullReferenceException.

This kind of null check can be found in other parts of QuickGraph, too.

[ktnr]

To properly check against reference and value types we could replace if (reversedEdge != null) with if (EqualityComparer<TEdge>.Default.Equals(reversedEdge, default(TEdge)))

For reference, see https://stackoverflow.com/a/864860/5587903

This would require a lot of changes throughout the code base. Not only on null checks for TEdge but also for TVertex. I am currently not working to fix this.

[ktnr]

Accidentaly closed the issue. It should still be open.

[Orace]

The C# language since v7.1 allow to write if (reversedEdge != default)

Anyway you have to be sure that the default value will not be meaningful in some corner case.

[KeRNeLith]

I think the best way to handle such thing is to use some TryXXX pattern. Because default can in some cases be a value part of the graph which would be a meaningful value.

I fixed this using this implementation.

I also checked for possible other similar problems in the library. All should be fixed in my fork.