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

Add to edges with no node check #47

Open andrea-cassioli-maersk opened 2 years ago

andrea-cassioli-maersk commented 2 years ago

Is your feature request related to a problem? Please describe. Running some profiling on our application, it seems that adding edges to a bidirectional graph is quite expensive, and in particular quite an amount of time is spent in looking up if origin and destination nodes are valid, i.e. they exists.

Describe the solution you'd like I was thinking about a flag to disable node existence checking. It could be enable by default, without breaking current interface.

KeRNeLith commented 2 years ago

Hello @andrea-cassioli-maersk!

Thank you for showing interest to QuikGraph :-)

Oh I see, that's mainly the integrity contrainst that is responsible of this. Do you have some profiling data to share on that topic? This may impact other graph implementation I imagine, but maybe you're focusing on bidirectional one.

Hum something that can be indeed implemented, it would be like an unsafe mode I imagine. Like disable checking producing better performance but user is responsible of maintaining the integrity. Note that this may produce unexpected behaviors in case the constraint is not met, since the whole design of those structures was to ensure logic is not broken at any point.

andrea-cassioli-maersk commented 2 years ago

Hi @KeRNeLith , this cost is no more that relevant for us as we progress, but still not negligible. I do not have a profiling right now. In general I can imagine that for performance sake one may want to switch off checking nodes every time...

KeRNeLith commented 2 years ago

In this case we can consider what I was talking about an unsafe mode. BTW such mode would require a check at each insertion. Considering that insert most of the time use map container for checks, I'm not sure we will gain a lot.

KeRNeLith commented 2 years ago

@andrea-cassioli-maersk did you find time to have some profiling data? I was wondering if for such scenario it would be better to go with a dedicated method not doing the check or adding a flag to it which in the later case add the cost of the flag to verify. Any thoughts on that?