search

mfe- / DataStructures.Algorithms

DataStructures and algorithms
Other
52 stars 10 forks source link

Too many collisions with <250000 edges when comparing with Edge.GetHashCode for transposed #9

Closed mfe- closed 4 years ago

mfe- commented 4 years ago

When generating more than 250000 edges with Generate_Grid_Graph there are many collisions using Edge.GetHashCode

return Math.Abs(U.GetHashCode()) + (V != null ? Math.Abs(V.GetHashCode()) : 0);

U.GetHashCode() =       return this._Guid.Equals((obj as Vertex)?._Guid);

Currently workaround.

return ($"{U}{V}" == $"{edge.U}{edge.V}" || $"{U}{V}" == $"{edge.V}{edge.U}");

Maybe the Guid of the Vertex should be exposed in IVertex so it can be used for comparison in the implementation of Edge. The Edge itself could generate a new Guid of Vertex.U and Vertex.V.

https://gist.github.com/mfe-/c23279f73f1b2373eeeb4a8baa5d7906

mfe- commented 4 years ago

Workaround with return ($"{U}{V}" == $"{edge.U}{edge.V}" || $"{U}{V}" == $"{edge.V}{edge.U}"); seems to be efficiency enough.