root/hodgestar/PythonCode/Graphs/cycles.py

import networkx
import networkx.search

class CycleFinder(object):
    def find_cycles(self,oG):
        pass

    @classmethod
    def count_cycles(cls,oG):
        """Return the number of cycles in graph oG."""
        aBackEdges = cls._find_back_edges(oG)

        oCopyOfG = oG.copy()

        iCycles = 0
        for tEdge in aBackEdges:
            oCopyOfG.delete_edge(tEdge)
            iCycles += cls._count_cycles_for_back_edge(tEdge,oCopyOfG)

        return iCycles

    @staticmethod
    def _find_back_edges(oG):
        if not oG.order():
            return {}

        oN = oG.nodes()[0]

        aBackEdges = set()
        aNodeStack = [oN]
        dParents = { oN: None }
        aPath = set()

        while aNodeStack:
            oN = aNodeStack.pop()

            for oChild in oG[oN]:
                if oChild is dParents[oN]:
                    continue

                if oChild in dParents:
                    if (oChild,oN) not in aBackEdges:
                        aBackEdges.add((oN,oChild))
                else:
                    aNodeStack.append(oChild)
                    dParents[oChild] = oN

        return aBackEdges

    @staticmethod
    def _count_cycles_for_back_edge(tEdge,oG):
        oFirst = tEdge[0]
        oSecond = tEdge[1]

        iCycles = 0
        aNodeStack = [(oSecond, set())]

        while aNodeStack:
            oN, aPath = aNodeStack.pop()

            for oChild in oG[oN]:
                if oChild in aPath:
                    continue

                if oChild is oFirst:
                    iCycles += 1
                    continue

                aChildPath = aPath.copy()
                aChildPath.add(oN)
                aNodeStack.append((oChild,aChildPath))

        print tEdge, iCycles
        return iCycles

count_cycles = CycleFinder.count_cycles