dag icon indicating copy to clipboard operation
dag copied to clipboard

Lenient cycle checking

Open dtelad11 opened this issue 7 years ago • 2 comments

Hey Kevin -- thank you for releasing this package, it has made my life much easier. One of the things my co-founder and I noticed is that checking for cycles with every new edge becomes a significant performance issue as DAGs grow larger (we could not build a graph with ~1,000 vertices and ~2,000 edges in a reasonable amount of time). I developed a tweak (check out my fork) where the user can choose to turn off cycle checking. Then, whenever an edge is added, the DAG "shuts off" and vertices and edges cannot be accessed until the user triggers a manual cycle checking.

It's working for our purposes but the code is messy and there are no tests -- is this something you want to merge into the main fork? If yes, let me know and I'll clean it up.

dtelad11 avatar Dec 06 '17 13:12 dtelad11

Kevin has stated that he currently doesn't have time to maintain the project. I have created my own fork and plan on releasing a ruby gem with the changes that I commited to my fork. I think you might be interested in the performance improvements made in my fork because they might make lenient cycle checking obsoloete. See my readme for the specifics of my improvements. I would be interested in your feedback.

I am also open to pull requests and I accept breaking changes as long as I haven't released the gem. I already contacted github support and asked them to turn my fork into a standalone repository.

fsobanski avatar Jan 18 '18 01:01 fsobanski

Thank you for taking over the gem and apologies for the radio silence, I've been busy with our product launch and did not have time to give your changes the attention they deserve. I hope to get to it early next week. Going over your changes, the performance updates look fantastic, I'd be more than happy to abandon my pull request and adopt your version. I will test it as soon as possible.

dtelad11 avatar Feb 05 '18 21:02 dtelad11