Open benswift opened 2 years ago
Since is_cyclic/1
is basically just a negation of is_acyclic/1
implementing something like get_cycles/1
would probably be a pretty big lift. I might take a stab at it. Leaving these references here to remind myself:
https://en.wikipedia.org/wiki/Rocha%E2%80%93Thatte_cycle_detection_algorithm
https://docs.tigergraph.com/graph-ml/current/pathfinding-algorithms/cycle-detection#:~:text=The%20Rocha%E2%80%94%E2%80%8BThatte%20algorithm,lengths%20up%20to%20k%20edges.
I might take a stab at it.
Oh that'd be great, thanks. For my use-case my graphs will only have hundreds of nodes, so a less efficient algo would be fine for me, but I understand if you don't wanna add things to the library which have serious performance footguns.
My graph theory's a little rusty, so it might be easy to do using the provided API, but is there an easy way to get a list of all the cycles (either as new
Graph
s, or as edgelists) in a directed graph?is_cyclic/1
can tell me if there is a cycle, but I want to know what the actual cycles are (I realise this is computationally expensive, that's fine because I only care about small graphs).