search

KeRNeLith / QuikGraph

Generic Graph Data Structures and Algorithms for .NET
https://kernelith.github.io/QuikGraph/
Microsoft Public License
467 stars 69 forks source link

[BUG] Function HasCycles does not compute the correct result #55

Closed TarekSalha closed 2 years ago

TarekSalha commented 2 years ago

Describe the bug Function HasCycles (src/QuikGraph/Extensions/EdgeExtensions.cs) does not compute the correct result

To Reproduce https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ shows two examples. The current implementation would mark both as cyclic, because it just checks, if two edges have the same target. This is not correct.

Expected behavior Only the first example is cyclic, the second is not.

KeRNeLith commented 2 years ago

Hello,

The function is maybe not documented or well enough but its purpose is to check if there is a cycle in a path formed by the given set of edges for which the order is important. So indeed it can result in some weird result if you don't meet the preconditions. This can be seen with this unit test that volontarly has a weird result expectation.

What you're certainly seeking is more the AlgorithmExtension.IsDirectedAcyclicGraph extension which accepts an IVertexListGraph graph (not only a set of edges). Note that there is no equivalent for undirected graph BTW. Maybe adding a method for those, and another one that given a set of edges build a graph under the hood and call the AlgorithmExtension.IsDirectedAcyclicGraph would be also great.

TarekSalha commented 2 years ago

Hi, thanks for the explanation. Got it! I admit, I was asking my self about the argument name "path"... :-)

KeRNeLith commented 2 years ago

Yeah I tried my best to rename stuff and make namings reflect what things are or are expected to be as much as possible.

I close this issue but I opened that one to reflect what could be an improvement in the end!