Parallelize cycle finding

[ZevEisenberg]

Would it be possible to speed up detectCycles and detectCyclesAsEdges by making them run parts of the search in parallel? I don't know whether the algorithm is suitable for parallelization, but it could be worth looking into.

Background: I've been modifying my juggling code to deal with throwing multiple objects at the same time, and the state graphs for this technique are way bigger than for throwing a single object at once. For 3 balls, for a maximum throw height of 6, there are 110,552 cycles in the graph. I don't know how many there are for a maximum throw height of 7 because I haven't been able to run the code for long enough yet to find out.

For graphs this large, memory usage is also a concern. My current test run searching for a max throw height of 7 is up over 1 GB used.

(Much of this is academic. I don't know if I have a real-world use case for searching for cycles on graphs this large, at least not quickly. If my app needs to use them, I'll probably generate them once and bake them into the app.)

[davecom]

Hi @ZevEisenberg, We are currently using an easy to implement cycle-detection algorithm that also allows us to limit detection to cycles of a certain length. However, there are much more performant algorithms out there. We would probably get more bang for the buck operating on large graphs by implementing one of these other algorithms (even if single-threaded) than we would by working on parallelizing the existing implementation. Best, Dave

[dabbott]

Related: https://github.com/davecom/SwiftGraph/pull/79

I think there are some quick improvements that could be made to detectCycles that'd improve speed and memory usage a lot - mainly memoizing the results of neighborsForVertex and indexOfVertex, and using indices instead of vertices where possible.

[davecom]

@dabbott No doubt you're right! Good call.