search

kevinrutherford / dag

Directed acyclic graphs for Ruby
43 stars 7 forks source link

Lenient cycle checking #11

Open dtelad11 opened 6 years ago

dtelad11 commented 6 years ago

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.

fsobanski commented 6 years ago

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.

dtelad11 commented 6 years ago

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.