{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Words/Ladder Graph\n\nGenerate an undirected graph over the 5757 5-letter words in the datafile\n`words_dat.txt.gz`. Two words are connected by an edge if they differ in one\nletter, resulting in 14,135 edges. This example is described in Section 1.1 of\n\n Donald E. Knuth, \"The Stanford GraphBase: A Platform for Combinatorial\n Computing\", ACM Press, New York, 1993.\n http://www-cs-faculty.stanford.edu/~knuth/sgb.html\n\nThe data file can be found at:\n\n- https://github.com/networkx/networkx/blob/main/examples/graph/words_dat.txt.gz\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import gzip\nfrom string import ascii_lowercase as lowercase\n\nimport matplotlib.pyplot as plt\nimport networkx as nx\n\n\ndef generate_graph(words):\n G = nx.Graph(name=\"words\")\n lookup = {c: lowercase.index(c) for c in lowercase}\n\n def edit_distance_one(word):\n for i in range(len(word)):\n left, c, right = word[0:i], word[i], word[i + 1 :]\n j = lookup[c] # lowercase.index(c)\n for cc in lowercase[j + 1 :]:\n yield left + cc + right\n\n candgen = (\n (word, cand)\n for word in sorted(words)\n for cand in edit_distance_one(word)\n if cand in words\n )\n G.add_nodes_from(words)\n for word, cand in candgen:\n G.add_edge(word, cand)\n return G\n\n\ndef words_graph():\n \"\"\"Return the words example graph from the Stanford GraphBase\"\"\"\n fh = gzip.open(\"words_dat.txt.gz\", \"r\")\n words = set()\n for line in fh.readlines():\n line = line.decode()\n if line.startswith(\"*\"):\n continue\n w = str(line[0:5])\n words.add(w)\n return generate_graph(words)\n\n\nG = words_graph()\nprint(\"Loaded words_dat.txt containing 5757 five-letter English words.\")\nprint(\"Two words are connected if they differ in one letter.\")\nprint(G)\nprint(f\"{nx.number_connected_components(G)} connected components\")\n\nfor source, target in [(\"chaos\", \"order\"), (\"nodes\", \"graph\"), (\"pound\", \"marks\")]:\n print(f\"Shortest path between {source} and {target} is\")\n try:\n shortest_path = nx.shortest_path(G, source, target)\n for n in shortest_path:\n print(n)\n except nx.NetworkXNoPath:\n print(\"None\")\n\n\n# draw a subset of the graph\nboundary = list(nx.node_boundary(G, shortest_path))\nG.add_nodes_from(shortest_path, color=\"red\")\nG.add_nodes_from(boundary, color=\"blue\")\nH = G.subgraph(shortest_path + boundary)\ncolors = nx.get_node_attributes(H, \"color\")\noptions = {\"node_size\": 1500, \"alpha\": 0.3, \"node_color\": colors.values()}\npos = nx.kamada_kawai_layout(H)\nnx.draw(H, pos, **options)\nnx.draw_networkx_labels(H, pos, font_weight=\"bold\")\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.7"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Generated by dwww version 1.16 on Wed Apr 8 12:10:54 CEST 2026.