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.)

@aioobe has a point. Just find all the cycles and then exclude the non-chordless ones. This may be too inefficient, but the search space can be pruned along the way to reduce the inefficiencies. Here is a general algorithm:

```
void printChordlessCycles( ChordlessCycle path) {
System.out.println( path.toString() );
for( Node n : path.lastNode().neighbors() ) {
if( path.canAdd( n) ) {
path.add( n);
printChordlessCycles( path);
path.remove( n);
}
}
}
Graph g = loadGraph(...);
ChordlessCycle p = new ChordlessCycle();
for( Node n : g.getNodes()) {
p.add(n);
printChordlessCycles( p);
p.remove( n);
}
class ChordlessCycle {
private CountedSet<Node> connected_nodes;
private List<Node> path;
...
public void add( Node n) {
for( Node neighbor : n.getNeighbors() ) {
connected_nodes.increment( neighbor);
}
path.add( n);
}
public void remove( Node n) {
for( Node neighbor : n.getNeighbors() ) {
connected_nodes.decrement( neighbor);
}
path.remove( n);
}
public boolean canAdd( Node n) {
return (connected_nodes.getCount( n) == 0);
}
}
```

Assign numbers to nodes from 1 to n.

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

Enumerate pairs of links coming out of 'A'.

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

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

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.

Repeat steps 3-5 with all pairs.

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);
}
}
}
}
}
```

How about this. First, reduce the problem to finding all chordless cycles that pass through a given vertex A. Once you've found all of those, you can remove A from the graph, and repeat with another point until there's nothing left.

And how to find all the chordless cycles that pass through vertex A? Reduce this to finding all chordless paths from B to A, given a list of permitted vertices, and search either breadth-first or depth-first. Note that when iterating over the vertices reachable (in one step) from B, when you choose one of them you must remove all of the others from the list of permitted vertices (take special care when B=A, so as not to eliminate three-edge paths).

Just a thought:

Let's say you are enumerating cycles on your example graph and you are starting from node 0.

If you do a breadth-first search for each given edge, e.g. 0 - 1, you reach a fork at 1. Then the cycles that reach 0 again first are chordless, and the rest are not and can be eliminated... at least I think this is the case.

Could you use an approach like this? Or is there a counterexample?

Find all cycles.

Definition of a chordless cycle is a set of points in which a subset cycle of those points don't exist. So, once you have all cycles problem is simply to eliminate cycles which do have a subset cycle.

For efficiency, for each cycle you find, loop through all existing cycles and verify that it is not a subset of another cycle or vice versa, and if so, eliminate the larger cycle.

Beyond that, only difficulty is figuring out how to write an algorithm that determines if a set is a subset of another.

Similar Questions

On an undirected and unweighted graph, how is it possible to enumerate all the groups of connected nodes having a length of 1,2,..,n (n is a user defined value)? This question is similar to this one;

I know what is forward and cross edge. But I am finding difficulty in implementing them in program to find all the forward and cross edges in a given graph. Any help in this regard would be appreciate

To expand on the title, I need all simple (non-cyclical) paths between all nodes in a very large undirected graph. The most obvious optimization I can think of is that once I have calculated all the

I'm looking for a way, given a directed graph, to find all nodes that are not reachable from a given starting point. I've got an idea, based on a similar concept to Dijkstra's Algorithm, that goes lik

I want to generate all the Hamiltonian Cycles of a complete undirected graph (permutations of a set where loops and reverses count as duplicates, and are left out). For example, permutations of {1,2,3

Given an undirected graph G=(V,E) with n vertices ( |V| = n ), how do you find if it contains a cycle in O(n) ?

What is the most efficient algorithm for detecting all cycles within a directed graph? I have a directed graph representing a schedule of jobs that need to be executed, a job being a node and a depend

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node? For example, I want something like this: A->B->A A->B->C->A but not: B->C->B

If I would want to find maximum flow in undirected graph, how could I do this? On Wikipedia page http://en.wikipedia.org/wiki/Maximum_flow_problem it says that algorithms require directed graphs (I wo

I am working on a directed graph (actually a bidirectional one) with Boost.Graph. I'd like to use the layout algorithms that exist (either Kamada-Kawai or Fruchterman-Reingold) but they only accept un

The issue is I need to create a random undirected graph to test the benchmark of Dijkstra's algorithm using an array and heap to store vertices. AFAIK heap implementation shall be faster than array wh

I have a problem but I can't figure out a solution. It goes like this: I have a directed graph with N nodes and M links and without cycles. I need to find out the minimum numbers of chains so every no

I'm trying to figure out how to create a new instance of a undirected weighted graph using QuickGraph for C#. My goal is to create a undirected weighted graph populated with a random number of nodes a

I am looking for an efficient algorithm which can help me to list out all the cuts in a graph. The graph is a flow network (directed graph) and has a source and a sink fixed. I want to find out what a

I'm bit stuck trying to solve a simple task of getting all linked issues. This is basically a graph task I guess - I take a jira issue, find all its links and then go to linked issues for their links

Given undirected graph, all edges have weight 1; N, M are about 10^6 I need to find whether the flow between source and sink is bigger than some value X. X is quite small. Using bfs until the flow is

How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?

I know there are a quite some answers existing on this question. However, I found none of them really bringing it to the point. Some argue that a cycle is (almost) the same as a strongly connected com

Instance of the problem: Undirected and unweighted graph G=(V,E). two source nodes a and b, two destination nodes c and d and a constant D(complete positive number).(we can assume that lambda(c,d),lam

Importing the language of graph databases, understand nodes (represented by circles), edges (represented by arrows), and properties (metadata of nodes / edges) The graphic (courtesy of wikipedia) d

I have a really difficult problem to solve and Im just wondering what what algorithm can be used to find the quickest route. The undirected graph consist of positive and negative adjustments, these ad

I have to determine if an undirected graph contains a cycle or not. I shoudn't use set! instructions. I tried using DFS, but I don't know how to mark the visited nodes.

Suppose there are 3 target nodes in a graph. A vertex-disjoint path means there is not any same node except the end nodes during the path. For any one single node, say node i, how to find all vertex

I'm working through previous years ACM Programming Competition problems trying to get better at solving Graph problems. The one I'm working on now is I'm given an arbitrary number of undirected graph

I am having problem to print out all the possible paths. Currently I am only able to print out one path, and if (path-demo J I), the program will shown this error mcdr: expects argument of type &l

We need an algorithm to generate all independent sets of an undirected graph. For example: We tried to use 'Bron-Kerbosch' algorithm, but do not understand how to interpret the result. Input: A = [1

I am interested in computing total number of simple paths(no node repeated) between two nodes in a graph(sparse, directed and contains cycles). The graph is a strongly connected component. I initially

Given a weighted graph (directed or undirected) I need to find the cycle of the graph with the maximum weight. The weight of a cycle being the sum of the weight of the edges of the graph. It can be an

For below given matrix,how it can be represented as undirected weighted graph G(V,E,W) where V is set of vertices,E is set of edges and W is set of weights. 4 2 3 1 4 2 2 3 1 4 2 3 3 1 4 1 2 3 1 4 4

If I have an undirected graph, how can I get a list of all cycles? For example, from the following graph, I would want the cycles: (a,b,d,e,c) (a,b,c) (b,d,e)

I have a finitely-sized 2D vector field. What I want is to find any cycles in this field - that is, if this field represented the flow of a fluid, and you placed an object on one of these cycles, th

Working on an algorithm for a game I am developing with a friend and we got stuck. Currently, we have a cyclic undirected graph, and we are trying to find the quickest path from starting node S that c

I am trying to implement LCA for unrooted tree. I have given a tree (a connected undirected graph without cycles) and a sequence of queries about LCA for some root and two vertices. Every particular q

What is the best algorithm for finding the all pairs shortest path lengths for undirected weighted sparse graph? Specifically, the weights are the distances between the nodes (and therefore positive).

I am trying to find a O(|V | + |E|) time algorithm to check if a connected undirected graph has a cycle of odd length or not. I am considering to do a Breadth First Search on the graph and trying to l

I try to show graphs in JGraphx. Everything is fine as long as I use directed Graphs, but when I try to show an undirected one, its shown with direction. The code is from the demo of jgrapht. packag

I want to find all the cycles in a directed graph. Starting Depth-first search from one node will find some cycles(finding back-edges). So, i applied dfs to all the nodes in the graph(i.e. each time t

I have been trying to implement a parallel Depth First Search in Java for undirected graph. I write this code but it doesn't work properly. It doesn't speed-up. Main method: package dfsearch_v2; impo

I was going through lecture of Minimum Spanning Tree, It says we are supposed to find connected acyclic subgraph graph in a Undirected graphs. My question is that How can a connected undirected graph

I have a disconnected bipartite undirected graph. I want to completely disconnect the graph. Only operation that I can perform is to remove a node. Removing a node will automatically delete its edges.

I'm attempting to, given a graph G with integer values and N levels, sum the values from the root to a leaf node. Find the maximal sum of these path values. Children nodes can have multiple parents, t

So I'm reading Robert Sedgewick's Algorithms 4th ed. book and the methods for finding a cycle in a directed graph is different than the one for finding a cycle in an undirected graph. Here is example

I'm trying to figure out how to find how many of my friends like a particular page and friends' detailed information such as id, name, and picture. For example: for a given page ID, how can I look u

How many clock cycles does these fours instructions take? #Macro Instructions li $t0, 32 # 1 or 2 cycles ? # # Based on MIPS Assembly Language Programming by Robert Britton : # # lui $at, Upper 16-bit

Possible Duplicate: Facebook Pages — Authoritative List of Categories Where I can find the full list of all possible like categories in Facebook Graph API?

To get an object out of S3 using Boto, you have to call something like (at least this is the only documented way I can find): key = bucket.get_key(some_id) data = key.get_contents_as_string() However

Suppose I am given a undirected tree and I need to find a path(the only path) between two nodes. What is the best algorithm to do it.I probably could use a Dijkstra's algorithm but there a probably so

Given is a bipartite graph, and we want to list all maximal complete bipartite sub-graph. For instance, vertex set L = {A, B, C, D} vertex set R = {a, b, c, d, e} edges: A-a, A-b, B-a, B-b, C-c, C-d,

I am using the igraph-python's Graph.Read_Ncol function. Below is my code for reading the data. def loadData(filename): data = None data = ig.Graph.Read_Ncol(filename, directed=False) return data I a

I have an undirected graph with at most 10 000 nodes and 50 000 edges . I need to find the node in which i should start such that passing through some mustpass nodes the distance will be the shortest.