Revision history [back]

To get longest cycle, you can run longest_path using each edge edndpoints as starting/ending vertices, and selecting the longest one among them:

def longest_cycle(G):
    def adde(H,e):
        H.add_edge(e)
        return H
    return max((adde(G.longest_path(*e),e) for e in G.edges(labels=False)), key=lambda H: H.size())

To get a longest induced cycle, one can remove all vertices of degree $\ne 2$, and in the remaining graph pick a largest connected component and construct an eulerian cycle there:

def longest_induced_cycle(H):
    G = H.copy()
    while (V := [v for v in G.vertices() if G.degree(v)!=2]):
        G.delete_vertices(V)
    return Graph(max(G.connected_components_subgraphs(),key=lambda t: t.size()).eulerian_circuit(labels=False)) if G.size() else Graph()

To get longest cycle, you can run longest_path using each edge edndpoints as starting/ending vertices, and selecting the longest one among them:

def longest_cycle(G):
    def adde(H,e):
        H.add_edge(e)
        return H
    return max((adde(G.longest_path(*e),e) for e in G.edges(labels=False)), key=lambda H: H.size())

To get a longest induced cycle, one can remove all vertices of degree $\ne 2$, and in the remaining graph pick a largest connected component and construct an eulerian cycle there:

def longest_induced_cycle(H):
    G = H.copy()
    while (V := [v for v in G.vertices() if G.degree(v)!=2]):
        G.delete_vertices(V)
    return Graph(max(G.connected_components_subgraphs(),key=lambda Graph(max(G.connected_components_subgraphs(), key=lambda t: t.size()).eulerian_circuit(labels=False)) if G.size() else Graph()
t.size(), default=Graph()).eulerian_circuit())

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

def longest_cycle(G):
    def adde(H,e):
        H.add_edge(e)
    longest_cycle(H):
    G = H.copy()
    C = Graph()
    while G.size() > C.size():
        e = G.edges(labels=False)[0]
        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 H
    return max((adde(G.longest_path(*e),e) for e in G.edges(labels=False)), key=lambda H: H.size())

To get a longest induced cycle, one can remove all vertices perform search for cycles of degree $\ne 2$, and in the remaining graph pick a largest connected component and construct an eulerian cycle there:decreasing size as induced subgraphs:

def longest_induced_cycle(H):
    G = H.copy()
    while (V := [v longest_induced_cycle(G):
    for v n in G.vertices() range(G.order(),2,-1):
        H = G.subgraph_search(graphs.CycleGraph(n),induced=True)
        if G.degree(v)!=2]):
        G.delete_vertices(V)
H is not None:
            return Graph(max(G.connected_components_subgraphs(), key=lambda t: t.size(), default=Graph()).eulerian_circuit())
H
    return Graph()

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 = G.edges(labels=False)[0] 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()

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 = G.edges(labels=False)[0]
        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
C

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()

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 = G.edges(labels=False)[0]
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()