Hamiltonian path that visits all 59 US states and possessions by two-letter code, changing one letter each time.

state-code-graph.py

#!/usr/bin/env python

# Construct a graph whose nodes are labeled with the two-letter abbreviations
# for all 59 states and possessions of the United States. Two nodes are joined
# by an edge if and only if they differ by a single letter (i.e. they share
# the same first letter or the same second letter). For example, MN is
# adjacent to MI and TN, but not to NM.

# The output file can be read by GraphViz to produce a graphic file in a
# variety of formats. For example, the following command will produce a
# PDF file, once GraphViz has been installed.
#
#       neato -Tpdf state-code-graph.dot -o state-code-graph.pdf

# The graph also shows a Hamiltonian path (in blue) which visits every
# state without repeated visits. The Hamiltonian path was found using
# Mathematica.

# The graph can be viewed at http://www.pinterest.com/pin/423127327463525568/

# Written by David Radcliffe ([email protected])

states = ['AL', 'AK', 'AS', 'AZ', 'AR', 'CA', 'CO', 'CT', 'DE', 'DC', 
          'FM', 'FL', 'GA', 'GU', 'HI', 'ID', 'IL', 'IN', 'IA', 'KS', 
          'KY', 'LA', 'ME', 'MH', 'MD', 'MA', 'MI', 'MN', 'MS', 'MO', 
          'MT', 'NE', 'NV', 'NH', 'NJ', 'NM', 'NY', 'NC', 'ND', 'MP', 
          'OH', 'OK', 'OR', 'PW', 'PA', 'PR', 'RI', 'SC', 'SD', 'TN', 
          'TX', 'UT', 'VT', 'VI', 'VA', 'WA', 'WV', 'WI', 'WY'] 

ham_path = [50, 49, 17, 18, 15, 48, 24, 23, 39, 27, 25, 30, 26, 22, 31,
            8, 9, 47, 37, 35, 10, 11, 16, 0, 1, 3, 2, 19, 28, 29, 6, 7,
            51, 52, 54, 53, 14, 46, 57, 56, 55, 58, 20, 36, 34, 32, 38,
            33, 40, 41, 42, 4, 45, 43, 44, 21, 5, 12, 13]

edges = [[] for i in xrange(len(states))]
output = ['graph {',
          '    overlap=false;',
          '    splines=true;',
          '    node [shape=circle, label="", color="blue", style=filled,width=0.05, height=0.05]']

for i in xrange(59):
    output.append('    %s [xlabel="%s"]' % (states[i], states[i]))

for i in xrange(58):
    for j in xrange(i+1, 59):
        if states[i][0] == states[j][0] or states[i][1] == states[j][1]:
            edges[i].append(j)
            edges[j].append(i)
            if abs(ham_path.index(i)-ham_path.index(j)) == 1:
                attr = '[color=blue,style=bold]'
            else:
                attr = '[color=gray]'
            output.append('    %s -- %s %s;' % (states[i], states[j], attr))

output.append("}")

outfile = "./state-graph.dot"
with open(outfile, "w") as f:
    f.writelines('\n'.join(output))