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)

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?

Wife

If your graph is unweighted, doesn't a DFS do what you need? – Pilar

I think Horton's Algorithm is on weighted grapths – Veil

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" – Angioma

Hi, link is dead, do you have another source ? – Saury

Answer 1

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

Hemia

there is a JS implementation for this algorithm as JS module: github.com/vbichkovsky/min-cycles – Quiteris

Answer 2

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

Herald

What's the source for this algorithm? Does it have proofs? – Marjoriemarjory