A blog about programming and more programming.

Number of Cycles in a Graph

with 2 comments

Question : Find the number of simple cycles in a simple graph.

Simple Graph – An undirected graph that has no loops and no more than one edge between any two different vertices.
Simple Cycle – A closed (simple) path, with no other repeated vertices or edges other than the starting and ending vertices.

Given a graph of N vertices and M edges, we will look at an algorithm with time complexity O(2NN2). We will use dynamic programming to do so. Let there be a matrix map, such that map[i][j] is equal to 1 if there is a edge between i and j and 0 otherwise. Let there be another array f[1<<N][N] which denotes the number of simple paths.

i denote a subset S of our vertices
k be the smallest set bit of i
then f[i][j] is the number of simple paths from j to k that 
contains vertices only from the set S. 

In our algorithm first we will find f[i][j] and then check if there is a edge between k and j, if yes, we can complete every simple path from j to k into a simple cycle and hence we add f[i][j] to our result of total number of simple cycles.Now how to find f[i][j].

For very subset i we iterate through all edges j. Once we have set k, we look for all vertices 'l' that can be neighbors of j in our subset S. So if l is a vertex in subset S and there is edge from j to l then f[i][j] = f[i][j] + the number of simple paths from l to i in the subset {S – j}. Since a simple graph is undirected or bidirectional, we have counted every cycle twice and so we divide our result by 2. Here's a sample C++ code which takes N, M and the edges as input.

using namespace std;

#define SIZE 20

bool map[SIZE][SIZE],F;
long long f[1<<SIZE][SIZE],res=0;

int main()
    int n,m,i,j,k,l,x,y;
    for (i=0;i<m;i++)
        if (x>y)
    for (i=7;i<(1<<n);i++)
        for (j=0;j<n;j++)
            if (i&(1<<j) && f[i][j]==0)
               if (F)
               for (l=k+1;l<n;l++)
                   if (i&(1<<l) && map[j][l])
               if (map[k][j])



Written by fR0DDY

June 7, 2010 at 1:14 PM

2 Responses

Subscribe to comments with RSS.

  1. Hey froddy!
    Nice articles on the blog! Helps when practicing on SPOJ and TC. Btw, have u graduated or in the senior year?

    Nitin Gangahar

    Nitin Gangahar

    June 29, 2010 at 12:41 AM

    • Thanks. I have graduated.


      July 3, 2010 at 5:17 PM

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: