0

I'm trying to generate all the cycles contained in a directed graph using Golang (or at least a few).
I currently have two structs : 

Node : { ID (string), resolved (bool), edges ([]Edge) }  
Edge : { ID (string), start (Node), end (Node), weight (Float64)}

The cycle weight is not an issue (for the moment). I've found some answers regarding how to detect cycles, or find shortest path etc. but i didn't find an algorithm that can quite help me.
How shall I proceed? (any suggestion is welcome)

hering
  • 1,956
  • 4
  • 28
  • 43
Nour saadallah
  • 11
  • 1
  • 2

2 Answers2

2

There are two parts to the question.

Regarding algorithms to detect all cycles in a graph, take a look at this related question (since this is not go-specific), there are useful explanations and pseudo-code that you can use to implement your solution.

Finding all cycles in a directed graph

As per specific go code, there are several libraries out there that work with graphs, you can take a look at their documentation and source code (they might even provide functionality that you can use out-of-the-box to solve your problem).

For example: https://godoc.org/github.com/twmb/algoimpl/go/graph

Community
  • 1
  • 1
eugenioy
  • 11,825
  • 28
  • 35
  • Okay thank you, i found that question previously but since i'm new and couldn't comment i'm gonna ask it here : How does this DFS algorithm keep the cycle in memory (i can't seem to know how to return the cycle once it's found)? dfs(adj,node,visited): if (visited[node]): if (node == start): "found a path" return; visited[node]=YES; for child in adj[node]: dfs(adj,child,visited) visited[node]=NO; – Nour saadallah May 16 '17 at 13:42
  • A cycle can be represented as a path, an ordered sequence of edges, such that `edges[0].start == edges[len(edges)].end` – nothingmuch May 16 '17 at 18:24
1

I would suggest starting with defining what a cycle is - for example let's suppose it is a traversal through the graph that starts and ends in the same node.

To enumerate all cycles with this definition, you'll need to consider all paths starting from all nodes, and check if any of those paths go back to their start point.

However, observe that this definition can actually count each cyclical subgraph many times - any node along a cyclical path - is that one cycle or several? And things get even more complicated if the paths of several cycles intersect, the number of cyclical paths increases drastically, and it's not very clear which cycles are "the same".

I hope it's easy to see that a brute force approach is intractable for anything but very small and simple graphs, and that something concerned with say minimal cycles or even just identifying cyclic subgraphs is enough for your purposes.

As already mentioned by @eugenioy, this has been asked before and you can probably narrow down your question by looking at the answers in that thread.

So, depending on what you mean by "all" and what you mean by "cycles", you can probably find an algorithm that defines cycles in the same way that you are interested in, and, and ask a more focused question if you're having trouble translating it to Go, which I don't think your question is really about at the moment.

Community
  • 1
  • 1
nothingmuch
  • 1,456
  • 9
  • 10