search

dominikbraun / graph

A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
https://graph.dominikbraun.io
Apache License 2.0
1.81k stars 94 forks source link

Add a fastpath for CreateCycles in memoryStore #133

Closed jonjohnsonjr closed 1 year ago

jonjohnsonjr commented 1 year ago

Our workload was spending most of its time in CreatesCycle, which was spending most of its time constructing the PredecessorMap. Because we don't need to modify the PredecessorMap, we don't really need to make any copies and can use memoryStore's inEdges to satisfy CreatesCycle, instead.

This seemed like the least intrusive way to make this change, but let me know if you have another preferred way to do this.

I also only added this to directed.go because that's all we use, please let me know if you'd like me to do similar things elsewhere.

dominikbraun commented 1 year ago

This change has been released in graph v0.22.3.