Which algorithms are there to find the Smallest Set of Smallest Rings?

Question

I have an unweighted undirected connected graph. Generally, it's a chemical compound with lots of cycles side by side. The problem is common in this field and is called like the title says. Good algorithm is Horton's one. However, I don't seem to find any exact information about the algorithm, step by step.

Clearly speaking my problem is this, Algorithm for finding minimal cycles in a graph , but unfortunately the link to the site is disabled. I only found python code of Figueras algorithm but Figuearas does not work in every case. Sometimes it doesn't find all rings. The problem is similar to this, Find all chordless cycles in an undirected graph , I tried it but didn't work for more complex graphs like mine. I found 4-5 sources of needed information, but the algorithm is not fully explained at all.

I don't seem to find any algorithm for SSSR although it seems a common problem, mainly in the chemistry field.

Wootan

did you google? have a look at this survey - there's even an open doctoral thesis on the topic in the first results... – Overhand

You may also want to reevaluate your use case. Since SSSR is not unique, it is often not really what you want. See discussion here: ics.uci.edu/~dock/manuals/oechem/cplusprog/node127.html – Cracksman

Answer 1

Horton's algorithm is pretty simple. I'll describe it for your use case.

1. For each vertex v, compute a breadth-first search tree rooted at v. For each edge wx such that v, w, x are pairwise distinct and such that the least common ancestor of w and x is v, add a cycle consisting of the path from v to w, the edge wx, and the path from x back to v.

2. Sort these cycles by size nondecreasing and consider them in order. If the current cycle can be expressed as the "exclusive OR" of cycles considered before it, then it is not part of the basis.

The test in Step 2 is the most complicated part of this algorithm. What you need to do, basically, is write out the accepted cycle and the candidate cycle as a 0-1 incidence matrix whose rows are indexed by cycle and whose columns are indexed by edge, then run Gaussian elimination on this matrix to see whether it makes an all-zero row (if so, discard the candidate cycle).

With some effort, it's possible to save the cost of re-eliminating the accepted cycles every time, but that's an optimization.

For example, if we have a graph

a---b
|  /|
| / |
|/  |
c---d

then we have a matrix like

      ab  ac  bc  bd  cd
abca   1   1   1   0   0
bcdb   0   0   1   1   1
abdca  1   1   0   1   1

where I'm cheating a bit because abdca is not actually one of the cycles generated in Step 1.

Elimination proceeds as follows:

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 1   1   0   1   1

row[2] ^= row[0];

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 0   0   1   1   1

row[2] ^= row[1];

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 0   0   0   0   0

so that set of cycles is dependent (don't keep the last row).

Maintop

Thank you for your response! Can you explain furthermore the 0-1 matrix? Are rows supposed to be the accepted cycle's nodes? And how are columns indexed by edge? Which edge, and what part of it? – Wootan

@MarinGeorgiev Gave you a small example of the matrix. – Maintop