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.