2

I have an undirected adjacency boost graph without weights. I need to find minimum cycles in the graph.

enter image description here

minimum cycle: c1[1 2 3 4 ] , c2[2 3 6 5], ... but for example: [1 2 5 6 3 4] is NOT a minimum cycle because it contains cycle c1 in it.

I went through different posts during my search, but eventually I end up with solutions to get the all cycles in a graph but not minimum cycles. From Finding all cycles in undirected graphs and Cycles in an Undirected Graph I understood the best way is doing a DFS search and look for back_edges. This thread gives some solutions with boost, but it gives all the cycles not the minimum cycle and it doesn't have implementation. Algorithm for finding minimal cycles in a graph discusses also how to get the minimum cycle but there is no solution for it.

I appreciate if someone has a workaround for this (better in boost graph library)?

Update: Minimum cycle here means in the set of vertices of a candidate cycle, there shouldn't be another direct connection between two vertices. For example in c3[1 2 5 6 7 4] there is no backedge between vertices, so it is a minimum. But in c4[1 2 3 6 7 4] there is an edge between [3 4] that can make a cycle [1 2 3 4], so we don't consider c4 as a minimum.

Bruce
  • 415
  • 2
  • 19
  • So `[1 2 5 6 3 4]` is not minimal, because `c1` is in it. How about `[1 2 5 6 7 4]`? It is not minimal for me, but it doesn't contain `c1` or one of the other smaller cycles. Do you want that to be a valid "minimal cycle" or not? – sehe Nov 16 '17 at 17:13
  • You need to associate costs with each edge, simply drawing lines greater and smaller does not make a cycle bigger or smaller – Luai Ghunim Nov 16 '17 at 18:46
  • @LuaiGhunim that's not what defines a minimal cycle here (it's not shortest paths, and shortest paths for constant weights is BFS, still has a useful definition) – sehe Nov 16 '17 at 22:35
  • @sehe in that case i can reform that graph and by placing 6 inside 1 4 2 3 without removing any edge and graph is totally isomorph with the first one ==> Both are equal. – Luai Ghunim Nov 17 '17 at 01:48
  • @LuaiGhunim yes. I can do that too. On first intuition I'd say that makes no difference to the question. – sehe Nov 17 '17 at 02:09
  • @sehe Yes that does. Then you have two cycles inside `1 4 3 2` and `1 4 3 2` becomes the biggest cycle because he defines the cycle as smallest which is contained in another. – Luai Ghunim Nov 17 '17 at 02:14
  • @LuaiGhunim That depends on how "minimum cycle" is defined. Which is what we're trying to ask from OP. – sehe Nov 17 '17 at 02:20
  • @LuaiGhunim I see that you have a valid point here. By rearranging the vertices, in the image we may have another cycle inside the other, but I specifically mentioned that I don't have `weight` on the edges or they have `equal weight`. So `minimum` in this concept is not minimum cost but set of vertices that doesn't contain other set of vertices which could be a cycle. – Bruce Nov 17 '17 at 10:04
  • 1
    @sehe To answer your first question, `[1 2 5 6 7 4]` doesn't have any set of vertices that possibly could make a cycle, so it is a minimum cycle in that sense. – Bruce Nov 17 '17 at 10:06

0 Answers0