CoCalc -- Collaborative Calculation in the Cloud
Sharedsupport / 2018-07-12-hamilton-path.sagewsOpen in CoCalc

Examples for support purposes...

There's a function below that converts a Hamiltonian path to a list of vertices.

set_random_seed(0)
g = graphs.RandomGNP(10,.7)
show(g)
d3-based renderer not yet implemented
h = g.hamiltonian_path()
show(h)
d3-based renderer not yet implemented
h
Hamiltonian path from RandomGNP(10,0.700000000000000): Graph on 10 vertices
def hamiltonian_path_to_vertices(h):
    path = []
    seen = set(path)
    for v in h.vertices():
        if len(h.edges_incident(v)) == 1:
            path.append(v)
            seen.add(v)
            break

    while len(path) < len(h):
        i = path[-1]
        done = False
        for e in h.edges_incident(i):
            if done: continue
            for n in e[:2]:
                if n != i and n not in seen:
                    path.append(n)
                    seen.add(n)
                    done = True
                    continue

    return path
hamiltonian_path_to_vertices(h)
[6, 7, 5, 4, 3, 2, 0, 1, 8, 9]