Revision history [back]

Removing a given vertex v and searching for a simple path connecting two vertices from the neighborhood of v should do the job:

def FindCycle(G, v, cycle_len):
    H = G.copy()
    H.delete_vertex(v)
    try:
        return [v] + next(p for p in H.all_paths_iterator(starting_vertices=G.neighbors(v), ending_vertices=G.neighbors(v), simple=True, max_length=cycle_len-2) if len(p)==cycle_len-1)
    except StopIteration:
        return None

For example, FindCycle(graphs.CompleteGraph(4), 0, 3) produces the cycle (as a list of vertices) [0, 3, 1].