How to find a longest cycle and a longest induced cycle in a graph?

savecancel

To get longest cycle, you can run longest_path using each edge edndpoints as starting/ending vertices, and selecting the longest one among them. Once edge is processed it can be removed from the graph.

def longest_cycle(H):
    G = H.copy()
    C = Graph()
    while G.size() > C.size():
        e = next(G.edge_iterator(labels=False))
        P = G.longest_path(*e)
        if P.size() > 1:
            P.add_edge(e)
            if P.size() > C.size():
                C = P
        G.delete_edge(e)
    return C

To get a longest induced cycle, one can perform search for cycles of decreasing size as induced subgraphs:

def longest_induced_cycle(G):
    for n in range(G.order(),2,-1):
        H = G.subgraph_search(graphs.CycleGraph(n),induced=True)
        if H is not None:
            return H
    return Graph()

This approach can also be used to search non-induced cycles (by setting induced=False), but it will be slower than the one given above.