Find all chordless cycles in an undirected graph

Question

How to find all chordless cycles in an undirected graph?

For example, given the graph

0 --- 1 |     | \ |     |  \ 4 --- 3 - 2 

the algorithm should return 1-2-3 and 0-1-3-4, but never 0-1-2-3-4.

---

(Note: [1] This question is not the same as small cycle finding in a planar graph because the graph is not necessarily planar. [2] I have read the paper Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion but I don't understand what they're doing :). [3] I have tried CYPATH but the program only gives the count, algorithm EnumChordlessPath in readme.txt has significant typos, and the C code is a mess. [4] I am not trying to find an arbitrary set of fundametal cycles. Cycle basis can have chords.)

Answer 1

Assign numbers to nodes from 1 to n.

1. Pick the node number 1. Call it 'A'.

2. Enumerate pairs of links coming out of 'A'.

3. Pick one. Let's call the adjacent nodes 'B' and 'C' with B less than C.

4. If B and C are connected, then output the cycle ABC, return to step 3 and pick a different pair.

5. If B and C are not connected:

   • Enumerate all nodes connected to B. Suppose it's connected to D, E, and F. Create a list of vectors CABD, CABE, CABF. For each of these:
   • if the last node is connected to any internal node except C and B, discard the vector
   • if the last node is connected to C, output and discard
   • if it's not connected to either, create a new list of vectors, appending all nodes to which the last node is connected.

   Repeat until you run out of vectors.

6. Repeat steps 3-5 with all pairs.

7. Remove node 1 and all links that lead to it. Pick the next node and go back to step 2.

Edit: and you can do away with one nested loop.

This seems to work at the first sight, there may be bugs, but you should get the idea:

void chordless_cycles(int* adjacency, int dim) {     for(int i=0; i<dim-2; i++)     {         for(int j=i+1; j<dim-1; j++)         {             if(!adjacency[i+j*dim])                 continue;             list<vector<int> > candidates;             for(int k=j+1; k<dim; k++)             {                 if(!adjacency[i+k*dim])                     continue;                 if(adjacency[j+k*dim])                 {                     cout << i+1 << " " << j+1 << " " << k+1 << endl;                     continue;                 }                 vector<int> v;                 v.resize(3);                 v[0]=j;                 v[1]=i;                 v[2]=k;                 candidates.push_back(v);             }             while(!candidates.empty())             {                 vector<int> v = candidates.front();                 candidates.pop_front();                 int k = v.back();                 for(int m=i+1; m<dim; m++)                 {                     if(find(v.begin(), v.end(), m) != v.end())                         continue;                     if(!adjacency[m+k*dim])                         continue;                     bool chord = false;                     int n;                     for(n=1; n<v.size()-1; n++)                         if(adjacency[m+v[n]*dim])                             chord = true;                     if(chord)                         continue;                     if(adjacency[m+j*dim])                     {                         for(n=0; n<v.size(); n++)                             cout<<v[n]+1<<" ";                         cout<<m+1<<endl;                         continue;                     }                     vector<int> w = v;                     w.push_back(m);                     candidates.push_back(w);                 }             }         }     } }