Skip to content

Instantly share code, notes, and snippets.

@cognivore

cognivore/loopy-graph.md

Created July 16, 2021 18:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cognivore/4aae73fca9b7705fba88900ff684d89b to your computer and use it in GitHub Desktop.
Save cognivore/4aae73fca9b7705fba88900ff684d89b to your computer and use it in GitHub Desktop.
Download ZIP
Stupid algorithm to enumerate loops in a graph
Raw
loopy-graph.md
  1. Pick random vertex q
  2. Traverse the graph breadth-first until a loop is detected, then stop traversing that branch entirely
    1. If loops that have the same paths are detected on the same level, count only one of those
  3. Delete vertex q and go to 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment