Enumeration of the Elementary Circuits of a Directed Graph TeX Export

View FullText article

• ACM, Rent at DeepDyve

Psuedo-code in the paper has some typos and is rather hard to read. Here's my implementation of the algorithm in python. It seems to work.

    def cycleEnumerate(adj_map):
        ''' 
            Takes an adjacency dictionary of nodes.  Test on this figure 8.  
            Dictionary looks like:
             { 1 : [2],
               2 : [3],
               3 : [1,4],
               4 : [5],
               5 : [3]
             }
            Returns a list of elementary cycles.
        '''
        class NullClass:
            pass
        globals = NullClass()
        globals.point_stack = []
        globals.mark_set = Set()
        globals.mark_stack = []
        globals.order = {}
        globals.cycles = []
        globals.adj_map = adj_map
        index = 0
        for node in adj_map.keys():
            globals.order[node] = index
            index += 1
        for node in adj_map.keys():
            globals.start = node
            globals.mark_set = Set()
            globals.mark_stack = []
            cycleEnumerateBacktrack(node, globals)
        return globals.cycles
    
    def cycleEnumerateBacktrack(node, globals):
        f = 0
        globals.point_stack.append(node)
        globals.mark_set.add(node)
        globals.mark_stack.append(node)
        for dnode in globals.adj_map[node]:
            if globals.order[dnode] < globals.order[globals.start]:
                continue
            elif dnode == globals.start:
                cycle = globals.point_stack+[dnode]
                cycle.reverse()
                globals.cycles.append(cycle)
                f = 1
            elif dnode not in globals.mark_set:
                g = cycleEnumerateBacktrack(dnode, globals)
                f = f or g
        if f:
            while globals.mark_stack[-1] != node:
                globals.mark_set.remove(globals.mark_stack.pop())
            globals.mark_set.remove(globals.mark_stack.pop())
        globals.point_stack.pop()
        return f

Reviewed by rblake as - 2008-11-01 05:32:17

• rblake

• graph

An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm uses back-tracking with lookahead to avoid unnecessary work, and it has a time bound of $O ((V+E)(C+1))$ when applied to a graph with $V$ vertices, $E$ edges, and $C$ elementary circuits. Keywords: Algorithm, circuit, cycle, graph