Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

I felt a little bit uncomfortable with 'cycle_basis' since it gives me a basis for all sets of disjoint cycles, but I actually want a set of all simple cycles (disjoint vertices).

A non optimal solution i came up with (using the implemented path function):

def simple_cycles(Gamma):
    """
    Returns a list of all simple cycles in the given graph Gamma as lists of vertices.
    """
    G = Graph(Gamma)    #make copy of given graph
    edges = G.edges()
    cycleList =[]
    for edge in edges:
        G.delete_edge(edge)        #delete starting edge to avoid duplicates
        if edge[0]==edge[1]:         #if its loop
            cycleList.append([edge[0], edge[1]])        
        for path in G.all_paths(edge[1], edge[0]):
            if(len(path)>1):
                cycleList.append([edge[0]]+path)
    return cycleList;

Optimizations or corrections will be appreciated (e.g. the description right now is horrible).

I felt a little bit uncomfortable with 'cycle_basis' since it gives me a basis for all sets of disjoint cycles, but I actually want a set of all simple cycles (disjoint vertices).

A non optimal solution i came up with (using the implemented path function):

def simple_cycles(Gamma):
    """
    Returns a list of all simple cycles in the given graph Gamma as lists of vertices.
    """
    G = Graph(Gamma)    #make copy of given graph
    edges = G.edges()
    cycleList =[]
    for edge in edges:
        G.delete_edge(edge)        #delete starting edge to avoid duplicates
        if edge[0]==edge[1]:         #if its loop
            cycleList.append([edge[0], edge[1]])        
        for path in G.all_paths(edge[1], edge[0]):
            if(len(path)>1):
                cycleList.append([edge[0]]+path)
    return cycleList;

Optimizations or corrections will be appreciated (e.g. the description right now is horrible).horrible). Also I am not sure how well this behaves with multiedges.