state_path.py

#/usr/bin/python
import networkx as nx
from nltk.corpus import wordnet as wn
import re
import itertools

#%%
# Get words and phrases from Wordnet between 8 and 10 characters long
words = set()
for l in wn.all_lemma_names():
    if re.match(r'^[A-Za-z\.\-\_]+$',l):
        alpha_l = re.sub('[^A-Z]+','',l.upper())
        if len(alpha_l) in (8,9,10):
            words.add(alpha_l)

#%%
# Create a graph of state borders
G = nx.Graph()
states = set()
state_borders = [['AL', 'FL'], ['AL', 'GA'], ['AL', 'MS'], ['AL', 'TN'], ['AR', 'LA'], ['AR', 'MO'], ['AR', 'MS'], ['AR', 'OK'], ['AR', 'TN'], ['AR', 'TX'], ['AZ', 'CA'], ['AZ', 'NM'], ['AZ', 'NV'], ['AZ', 'UT'], ['CA', 'NV'], ['CA', 'OR'], ['CO', 'KS'], ['CO', 'NE'], ['CO', 'NM'], ['CO', 'OK'], ['CO', 'UT'], ['CO', 'WY'], ['CT', 'MA'], ['CT', 'NY'], ['CT', 'RI'], ['DE', 'MD'], ['DE', 'NJ'], ['DE', 'PA'], ['FL', 'GA'], ['GA', 'NC'], ['GA', 'SC'], ['GA', 'TN'], ['IA', 'IL'], ['IA', 'MN'], ['IA', 'MO'], ['IA', 'NE'], ['IA', 'SD'], ['IA', 'WI'], ['ID', 'MT'], ['ID', 'NV'], ['ID', 'OR'], ['ID', 'UT'], ['ID', 'WA'], ['ID', 'WY'], ['IL', 'IN'], ['IL', 'KY'], ['IL', 'MO'], ['IL', 'WI'], ['IN', 'KY'], ['IN', 'MI'], ['IN', 'OH'], ['KS', 'MO'], ['KS', 'NE'], ['KS', 'OK'], ['KY', 'MO'], ['KY', 'OH'], ['KY', 'TN'], ['KY', 'VA'], ['KY', 'WV'], ['LA', 'MS'], ['LA', 'TX'], ['MA', 'NH'], ['MA', 'NY'], ['MA', 'RI'], ['MA', 'VT'], ['MD', 'PA'], ['MD', 'VA'], ['MD', 'WV'], ['ME', 'NH'], ['MI', 'OH'], ['MI', 'WI'], ['MN', 'ND'], ['MN', 'SD'], ['MN', 'WI'], ['MO', 'NE'], ['MO', 'OK'], ['MO', 'TN'], ['MS', 'TN'], ['MT', 'ND'], ['MT', 'SD'], ['MT', 'WY'], ['NC', 'SC'], ['NC', 'TN'], ['NC', 'VA'], ['ND', 'SD'], ['NE', 'SD'], ['NE', 'WY'], ['NH', 'VT'], ['NJ', 'NY'], ['NJ', 'PA'], ['NM', 'OK'], ['NM', 'TX'], ['NV', 'OR'], ['NV', 'UT'], ['NY', 'PA'], ['NY', 'VT'], ['OH', 'PA'], ['OH', 'WV'], ['OK', 'TX'], ['OR', 'WA'], ['PA', 'WV'], ['SD', 'WY'], ['TN', 'VA'], ['UT', 'WY'], ['VA', 'WV']]
for st1,st2 in state_borders:
    states.add(st1); states.add(st2)
    G.add_node(st1); G.add_node(st2)
    G.add_edge(st1,st2)

#%%
# Loop through simple paths and look for words
for st1, st2 in itertools.permutations(states,2):
    for path in nx.all_simple_paths(G,st1,st2,cutoff=10):
        word = ''.join(x[0] for x in path)
        if word in words:
            print word, path

# Results:
"""
MINKCOAT ['MO', 'IA', 'NE', 'KS', 'CO', 'OK', 'AR', 'TX']
MINKCOAT ['MO', 'IA', 'NE', 'KS', 'CO', 'OK', 'AR', 'TN']
MINKCOAT ['MN', 'IA', 'NE', 'KS', 'CO', 'OK', 'AR', 'TX']
MINKCOAT ['MN', 'IA', 'NE', 'KS', 'CO', 'OK', 'AR', 'TN']
"""