<s> """<STR_LIT>""" <EOL> import networkx as nx <EOL> def generate_graph ( words ) : <EOL> from string import ascii_lowercase as lowercase <EOL> G = nx . Graph ( name = "<STR_LIT>" ) <EOL> lookup = dict ( ( c , lowercase . index ( c ) ) for c in lowercase ) <EOL> def edit_distance_one ( word ) : <EOL> for i in range ( len ( word ) ) : <EOL> left , c , right = word [ <NUM_LIT:0> : i ] , word [ i ] , word [ i + <NUM_LIT:1> : ] <EOL> j = lookup [ c ] <EOL> for cc in lowercase [ j + <NUM_LIT:1> : ] : <EOL> yield left + cc + right <EOL> candgen = ( ( word , cand ) for word in sorted ( words ) <EOL> for cand in edit_distance_one ( word ) if cand in words ) <EOL> G . add_nodes_from ( words ) <EOL> for word , cand in candgen : <EOL> G . add_edge ( word , cand ) <EOL> return G <EOL> def words_graph ( ) : <EOL> """<STR_LIT>""" <EOL> import gzip <EOL> fh = gzip . open ( '<STR_LIT>' , '<STR_LIT:r>' ) <EOL> words = set ( ) <EOL> for line in fh . readlines ( ) : <EOL> line = line . decode ( ) <EOL> if line . startswith ( '<STR_LIT:*>' ) : <EOL> continue <EOL> w = str ( line [ <NUM_LIT:0> : <NUM_LIT:5> ] ) <EOL> words . add ( w ) <EOL> return generate_graph ( words ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> from networkx import * <EOL> G = words_graph ( ) <EOL> print ( "<STR_LIT>" ) <EOL> print ( "<STR_LIT>" ) <EOL> print ( "<STR_LIT>" <EOL> % ( number_of_nodes ( G ) , number_of_edges ( G ) ) ) <EOL> print ( "<STR_LIT>" % number_connected_components ( G ) ) <EOL> for ( source , target ) in [ ( '<STR_LIT>' , '<STR_LIT>' ) , <EOL> ( '<STR_LIT>' , '<STR_LIT>' ) , <EOL> ( '<STR_LIT>' , '<STR_LIT>' ) ] : <EOL> print ( "<STR_LIT>" % ( source , target ) ) <EOL> try : <EOL> sp = shortest_path ( G , source , target ) <EOL> for n in sp : <EOL> print ( n ) <EOL> except nx . NetworkXNoPath : <EOL> print ( "<STR_LIT:None>" ) </s>
