3

It seems I've read through all of the questions about finding cycles in graphs on stackoverflow and more, so I'll try to be as clear as possible:

  1. I am new to all these algorithms, so please try to be as specific as possible in your answers. Thanks!
  2. Complexity and performance does not matter to me
  3. I have a directed graph and a starting vertex
  4. I need only negative-weight cycles starting and ending in that vertex (e.g. A-B-C-A, A-G-M-A etc.)
  5. I need only simple cycles (i.e. A-B-A-B-A will not work for me).
  6. Elementary cycles (i.e. A-B-A) also need to be included
  7. I need to print all of these cycles (not count or just tell if they exist)
  8. I tried Bellman-Ford algorithm, but it seems to find only the most negative cycle. Even changing the starting vertex does not guarantee all cycles.

The only solution I found to that problem is finding all cycles and choosing negative-weight cycles from them. The thing is the solution COUNTS (not prints) ALL (not the ones that start and end in a given vertex). I'm stuck here. Any help would be greatly appreciated. Thanks in advance!

Alexei Sichov
  • 31
  • 3
  • 1
    I think what you are looking for is [here](https://stackoverflow.com/questions/546655/finding-all-cycles-in-a-directed-graph) – SomeDude May 02 '22 at 13:32
  • @SomeDude you are probably right. Johnson's algorithm seems like a good fit here. The thing is I can't find anywhere an implementation in the language I know (JS/TS, C#, Dart). Although it is used to find all cycles, it should be pretty easy to edit it to return only cycles for a given vertex. If you could point me to the implementation in any of these languages (or myabe C++), that would be just wonderful! – Alexei Sichov May 02 '22 at 15:03
  • 1
    See https://stackoverflow.com/questions/5411991/implementation-of-johnsons-algorithm-to-find-elementary-circuits-cycles-in-a – SomeDude May 02 '22 at 15:27
  • @SomeDude thank you! I found a java implementation there. I will probably leave the question open, in case someone comes up with an answer that only uses a given vertex. Since the question you were referencing is pretty old I believe something could change. Thanks again! – Alexei Sichov May 03 '22 at 08:15
  • [This cstheory post](https://cstheory.stackexchange.com/questions/32332/reference-for-mixed-graph-acyclicity-testing-algorithm) lists three algorithms with brief mention of their respective benefit. Johnsons's Algo in the JGraphT library you must have found in the SO post cited in SomeDude's comment; the [Hawick algo](https://jgrapht.org/javadoc-1.4.0/org/jgrapht/alg/cycle/HawickJamesSimpleCycles.html) happens to be implemented there as well. – collapsar May 03 '22 at 09:18
  • @collapsar I've never heard about Hawick algorithm. The post you attached states this algorithm further improves on Johnson's, so thank you! – Alexei Sichov May 03 '22 at 10:09

0 Answers0