1

Is there any implementation of an algorithm finding all the cycles in a directed multigraph with self edges in Golang ? I found out that the Johnson's algo is the best solution for directed graphs and an implementation is given in gonum but it works only on directed graphs (not multigraphs) and it does not support self edges (actually directed graphs in gonum don't support self edges). Is there any short/clever hack that I can do in gonum to make johnson's work for directed multigraphs with self edges ? Or is there any other implementation in Golang ?

One thing that can be done is to create a dummy node between self edges and the duplicate edges between same pair of nodes. This will remove all self edges and graph will be a directed one and I can use the Johnson's here. But is there any better way ?

Salman Azmat
  • 298
  • 6
  • 18

1 Answers1

1

  • self edges : you just have to scan each node of your graph and check if there is a self edge. If there is : add X -> X to the list of cycles

  • multi graph : the first algorithm will produce paths as a sequence of vertices X1 -> X2 -> X3 -> .... When you have this list, iterate over all the possible edges going from X1 to X2, then all the possible edges going from X2 to X3, etc ...

  • "clever" hack : from your multigraph G, create a new graph G2, where the edges of G also appear as vertices :
# if A and B are connected     # create the following 3 vertices and
# by a single edge in G :      # 2 edges in G2 :

   A ---w--> B                     A -> w -> B


# if A and B are connected     # create the following 4 vertices and
# by two edges in G :          # 4 edges in G2 :

     /--x--\                           /-> x --\
    A       B                        A          B
     \--y--/                           \-> y --/

# etc ...

then run your cycle enumeration on G2, and adapt the output as needed.

LeGEC
  • 46,477
  • 5
  • 57
  • 104