0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Tom van der Zanden Jul 11 '15 at 12:03
  • $\begingroup$ 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 $\endgroup$ – wiki Jul 11 '15 at 12:20
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 12 '15 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.