Sharedsupport / 2018-07-12-hamilton-path.sagewsOpen in CoCalc
Author: William A. Stein
License: GNU General Public License v3.0
Description: 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]