# Find simple cycles pass through a vertex in drected graph

I want to find all the simple cycles with bounded length that pass through a vertex in a directed graph. Enumerating all the cycles in large graph takes exponential time. Since I need to find only the cycles that passes through a given vertex and I can save the running time. But I am not getting any proper algorithm to do this sub-problem.

In my problem I can limit the length of cycles as 20 irrespective of the size of the graph. My graph contains 5569 vertices and 29782 directed edges.

I have modified the implementation of tarjan's algorithm presented here.

The modified code is as follows,

import sys
import nltk
from copy import deepcopy

class Cycles:
def __init__(self,graph):
self.A=graph
self.point_stack = list()
self.marked = dict()
self.marked_stack = list()
self.cycles =list()

def backtrack(self,v,s):
f = False
self.point_stack.append(v)
self.marked[v] = True
self.marked_stack.append(v)
if v not in self.A:
return f
for w in self.A[v]:
if w not in self.marked:
self.marked[w]=False
if w==s:
self.cycles.append(deepcopy(self.point_stack))
f = True
elif not self.marked[w] and len(self.point_stack)<20: # to bound the cycle length
f = self.backtrack(w,s) or f
if f:
while self.marked_stack[-1] != v:
u = self.marked_stack.pop()
self.marked[u] = False
self.marked_stack.pop()
self.marked[v] = False
self.point_stack.pop()
return f

def getCycles(self,word):
for i in self.A:
self.marked[i] = False
self.backtrack(word,word)
return self.cycles


This runs very fastly. But many simple cycles are missing.

• It will still take exponential time, at most you're going to save a linear factor off the running time... What do you need specifically? – Tom van der Zanden Jul 11 '15 at 12:03
• Specifically I want to analyse the bounded length cycles(say cycles with length less than 20) that passes through a given vertex. My graph contains 5569 vertices and 29782 directed edges – wiki Jul 11 '15 at 12:20
• The number of such cycles could still be as large as $5567^{20} \approx 10^{74}$ or so, which is enormous and far too large to enumerate within your lifetime. What exactly are you going to do with the list of all such cycles? Perhaps there's a better way to achieve whatever your ultimate goal is. – D.W. Jul 12 '15 at 4:32