[BUG] ToGraphViz fails on DelegateVertexAndEdgeListGraph when using `Edge`

[shuebner]

Describe the bug When creating a DelegateVertexAndEdgeListGraph and then calling ToGraphViz on it, GraphvizAlgorithm.WriteEdges will cause a KeyNotFoundException. The reason is that GraphvizAlgorithm enumerates the DelegateVertexAndEdgeListGraph's edges once for populating the verticesColors Dictionary in Generate and then again in WriteEdges by calling IEdgeListGraph<,>.Edges. The iterator implementation of DelegateVertexAndEdgeListGraph will create one instance for the edge in the first call and then another in the second call. Since Edge does not override Equals, using the second instance as a dictionary key will fail.

I had to actually check out the source and debug it to find the reason. While doing that, I also saw that there is EquatableEdge that prevents this error. But using it is IMHO far from obvious and should at least be highlighted in the documentation.

I would even go so far as to call this a bug. I cannot imagine any use-case of an Edge<TVertex> that does not include source and target in its Equals semantics.

I suggest either of the following:

• enumerate the edges only once in ToGraphViz (this would only mask the symptoms)
• removing the class entirely
• make it abstract to prevent usage
• implement Equals via comparing source and target

To Reproduce Steps to reproduce the behavior:

1. Create a DelegateVertexAndEdgeListGraph
2. Call ToGraphViz on it

Expected behavior It should not throw KeyNotFoundException.

[KeRNeLith]

Hello @shuebner!

Hum indeed this is a problem to have such behavior when trying to convert to Graphviz (using ToGraphviz) extension. First thing to note is that indeed delegate graph implementation does not bufferize anything to allow "evolution" of the graph based on the provided delegate. This has the consequence of indeed enumerating multiple times what comes from the enumerable of vertices. But since the content of this enumerable and the delegate to get out edges is user provided then it's difficult to do in another way if we want the keep the evolutive behavior.

Concerning the Edge implementation it indeed not override the Equals method on purpose because by design we have bot Edge and EquatableEdge that answer to each constraint (Note that there are also struct versions).

Of course we can add a mention to the different kind of edges that are exposed by the library to highlight this point. Which for sure is something important. BTW I take this opportunity to remind this wiki page about edges. But the idea is not to change the default implementation of Edge but more to communicate on other implementations. Note also that you may also inherit from QuikGraph edge structures, or create from scratch your own implementation fitting your needs. In your case, existing classes/structures are maybe enough BTW.

Since it's in the design of those defined classes/structures to not be equatable by default and also because there is a version that implement the behavior, I would say that it's not reasonable to break this old design of the API.

So concerning next steps, adding Equals to the Edge is not really a feasable move as well as removing or making it abstract since it can be use on its own like this. Most cases can use Edge without the need of being equatable. It becomes more important to use EquatableEdge in delegate graph scenario I think due to the nature of the graph. So the point would certainly be to investigate deeper the ToGraphviz algorithm.

Do you agree with that?

[shuebner]

Hello @KeRNeLith, thank you for picking up the issue. After reading your explanation, it does seem sensible to solve the issue within the confines of the ToGraphviz use-case.

Please note that I never said that the edge types were not documented. I merely said it is not obvious from the graphviz page that the used edge type must implements Equals in a way that incorporates source and target to work correctly.

[KeRNeLith]

Okey so will go this way in the case of ToGraphviz.

Oh misunderstood your point, sorry about that :-(

Indeed I think we need to make it clearer in this documentation page. Note that I didn't tested it yet, but I'm pretty sure the main problem is using a delegate graph implementation which "forces" having the Equals implemented to properly work because I didn't noticed issue on AdjacencyGraph for example. Even if I tried to put a big test suite for the libraries, I also sometimes fallback a lot on the AdjacencyGraph implementation for testing which may not catch issues triggered by other implementations.

But this need to be checked in more details. And of course if that's the case a mention in the pointed documentation will be mandatory!

[KeRNeLith]

@shuebner I improved the implementation of the GraphvizAlgorithm so that delegate graph implementation you mentionned no more throw regardless of the Edge implementation (equatable or not). This is now unit tested to avoid regressions.