Algorithm for finding minimal cycles in a graph

Question

I'm looking for an algorithm that given a graph it returns all the minimal cycles in it.
To make clear what I want, I need the algorithm to return exactly the following cycles from this graph:
(1,3,6,1), (1,6,4,1), (1,4,2,1), (6,4,7,6), (2,4,7,2), (2,7,5,2)
enter image description here

I've been searching alot and I still can't figure out even the name of this problem. Is it the cycle basis problem or the fundamental cycles problem or are those two the same? I found solutions involving MST or All-Pairs Shortest Paths but I can't understand any of them.
I tried to implement Horton's algorithm which I found here: Horton's Algorithm but I got stuck at the 4th step in page 5 trying to actually find out the cycles.
Can somebody either explain to me what exactly needs to be done in step 4 of Horton's algorithm or give me another algorithm to solve my problem?

If your graph is unweighted, doesn't a DFS do what you need? — Juan Lopes, May 28 '13 at 02:56
No, Horton's Algorithm for the shortest cycle basis is for unweighted graphs. To quote the paper "In this paper, graphs finite, undirected, without loops or multiple edges" — juniper-, Oct 21 '14 at 18:25

score 3 · Answer 1 · answered Aug 14 '13 at 15:39

3

This paper describes algorithm used in geometric tools library (written ic C++ i think). It's basically a modified DFS algorithm with addition of some algebra. The pseudocode is to big to post it here, so here is the link:

http://www.geometrictools.com/Documentation/MinimalCycleBasis.pdf

I'm currently working on javascript implementation. If you're interested you can view it here:

http://jsbin.com/igujuz/8/edit

answered Aug 14 '13 at 15:39

Tomasz Kowalczyk

1,951
2
16
18

there is a JS implementation for this algorithm as JS module: https://github.com/vbichkovsky/min-cycles – rude Jun 13 '19 at 12:57

score 0 · Answer 2 · answered May 28 '13 at 06:02

This Algorithm only works for un-weighted graph:

Example:

INPUT GRAPH: A, B, C, D, E

A: B, C, E
B: A, C
C: A, B, D
D: C, E
E: A, D

Algorithm:

Initialization

[LIST] = { }

LIST[A] = { A }
LIST[B] = { B }
LIST[C] = { C }
LIST[D] = { D }
LIST[E] = { E }

DISTANCE = 0

SOLVED = FALSE

SOLUTION = { }

Search

WHILE NOT SOLVED DO

    DISTANCE = DISTANCE + 1

    FOR EVERY LIST[X] IN [LIST]
        TEMP = LIST[X]
        LIST[X] = { }
        FOR EVERY VERTEX IN TEMP
            LIST[X] += NEIGHBORS(VERTEX)
        END-FOR
    END-FOR

    FOR EVERY LIST[X] IN [LIST]
        FOR EVERY VERTEX IN LIST[X]
            IF VERTEX = X THEN
                SOLUTION = { X, DISTANCE }
                SOLVED = TRUE
            END-IF
        END-FOR
    END-FOR

END-WHILE

What's the source for this algorithm? Does it have proofs? – sehe Nov 16 '17 at 22:40 — sehe, Nov 16 '17 at 22:40

Algorithm for finding minimal cycles in a graph

2 Answers2

Linked