4

I have found a simple algorithm to find all cycles in a graph here. I need to print out the cycles too, is it possible with this algorithm. Please find the code below.

I'm getting the number of cycles correctly!

node1, node2 are integers. visited is a dictionary

def dfs(self,node1, node2):
    if self.visited[node2]:
        if(node1 == node2):
            self.count += 1
            print node2
        return

    self.visited[node2] = True

    for x in self.adj_lst[node2-1]:
        self.dfs(node1, x)

    self.visited[node2] = False

def allCycles(self):
    self.count = 0
    for x in self.VList:
        self.dfs(x.num, x.num)
        self.visited[x.num] = True

    print "Number of cycles: "+str(self.count)
Community
  • 1
  • 1
Kalyan Chavali
  • 131
  • 1
  • 1
  • 13

2 Answers2

12

Yes of course you can construct the path, now you can do it recursively but I'm not a great fan of managing temporary state in the class.

Here's a simple implementations using a stack:

def dfs(graph, start, end):
    fringe = [(start, [])]
    while fringe:
        state, path = fringe.pop()
        if path and state == end:
            yield path
            continue
        for next_state in graph[state]:
            if next_state in path:
                continue
            fringe.append((next_state, path+[next_state]))

>>> graph = { 1: [2, 3, 5], 2: [1], 3: [1], 4: [2], 5: [2] }
>>> cycles = [[node]+path  for node in graph for path in dfs(graph, node, node)]
>>> len(cycles)
7
>>> cycles
[[1, 5, 2, 1], [1, 3, 1], [1, 2, 1], [2, 1, 5, 2], [2, 1, 2], [3, 1, 3], [5, 2, 1, 5]]

Note: 4 cannot get back to itself.

AChampion
  • 29,683
  • 4
  • 59
  • 75
  • How would i call this function ? – Oscar Dolloway Apr 18 '18 at 12:51
  • how would i add the cycles to the function and call it so it prints all the cycles each time? – Oscar Dolloway Apr 18 '18 at 13:54
  • You would call it `dfs(graph, node1, node2)`, this is a generator useful in a loop, e.g. `for path in dfs(graph, node1, node2)` - if you want a list of paths from `node1` to `node2` you can simply `paths = list(dfs(graph, node1, node2)`. – AChampion Apr 19 '18 at 01:57
  • I tried graph = {2: [4, 1], 3: [2], 1: [4, 3]} but it always come out KeyError: 4 – nosense Dec 17 '19 at 03:36
  • 1
    Your graph doesn't describe the complete graph (i.e. it misses a definition for node `4`). You can either add `4: []` to your graph definition, or you can replace `for next_state in graph[state]:` with `for next_state in graph.get(state, []):`. – AChampion Dec 17 '19 at 22:53
  • Thanks for the explanation. I fixed that problem by judging if one number is in the dictionary keys. I found out this method runs very slow when dealing with graph with at most 1000 vertices (http://rosalind.info/problems/cte/). Do you know any faster algorithms? I also tried networkx built-in simple_cycles function, still very slow. – nosense Dec 18 '19 at 23:14
  • It is overkill to find all cycles when you just need to find one through a given edge. Having a given edge seriously reduces the search space. Start at the end of the edge and end a the beginning of the edge, e.g. going through edge `(2, 3)` `max(len(p)+1 for p in dfs(graph, 3, 2))` – AChampion Dec 19 '19 at 12:34
  • How can I call the function so I only get the cycles starting from a specific **node**? – Shahriar Jun 08 '23 at 19:01
  • The function already has a start and end argument, just call the function with the specific node as the start and end. – AChampion Jun 13 '23 at 01:12
0

Yes, it's possible. You can just store the parent of each vertex and then iterate over the array of parents (until you reach the start vertex) to print the cycle when you find one.

kraskevich
  • 18,368
  • 4
  • 33
  • 45
  • I'm not doing the parent-children thing here for vertices. They are just integers. All the edges are stored as tuples in EList. Is it still possible? – Kalyan Chavali Nov 27 '16 at 21:05
  • Oh and I have adjacency list for each vertex. How can I use that one for printing? – Kalyan Chavali Nov 27 '16 at 21:11
  • 1
    @KalyanChavali You can create an additional array (list, map) `parent` and assign parent[u] = v when you go from v to u by an edge in the dfs. – kraskevich Nov 27 '16 at 21:11
  • I tried this approach, but it would be stuck in an infinite loop. Please find the code here [link]https://github.com/kalyan-ch/graphs/graph.py – Kalyan Chavali Nov 27 '16 at 21:53