1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
"""
==================
Words/Ladder Graph
==================
Generate an undirected graph over the 5757 5-letter words in the datafile
`words_dat.txt.gz`. Two words are connected by an edge if they differ in one
letter, resulting in 14,135 edges. This example is described in Section 1.1 of
Donald E. Knuth, "The Stanford GraphBase: A Platform for Combinatorial
Computing", ACM Press, New York, 1993.
http://www-cs-faculty.stanford.edu/~knuth/sgb.html
The data file can be found at:
- https://github.com/networkx/networkx/blob/main/examples/graph/words_dat.txt.gz
"""
import gzip
from string import ascii_lowercase as lowercase
import matplotlib.pyplot as plt
import networkx as nx
def generate_graph(words):
G = nx.Graph(name="words")
lookup = {c: lowercase.index(c) for c in lowercase}
def edit_distance_one(word):
for i in range(len(word)):
left, c, right = word[0:i], word[i], word[i + 1 :]
j = lookup[c] # lowercase.index(c)
for cc in lowercase[j + 1 :]:
yield left + cc + right
candgen = (
(word, cand)
for word in sorted(words)
for cand in edit_distance_one(word)
if cand in words
)
G.add_nodes_from(words)
for word, cand in candgen:
G.add_edge(word, cand)
return G
def words_graph():
"""Return the words example graph from the Stanford GraphBase"""
fh = gzip.open("words_dat.txt.gz", "r")
words = set()
for line in fh.readlines():
line = line.decode()
if line.startswith("*"):
continue
w = str(line[0:5])
words.add(w)
return generate_graph(words)
G = words_graph()
print("Loaded words_dat.txt containing 5757 five-letter English words.")
print("Two words are connected if they differ in one letter.")
print(G)
print(f"{nx.number_connected_components(G)} connected components")
for source, target in [("chaos", "order"), ("nodes", "graph"), ("pound", "marks")]:
print(f"Shortest path between {source} and {target} is")
try:
shortest_path = nx.shortest_path(G, source, target)
for n in shortest_path:
print(n)
except nx.NetworkXNoPath:
print("None")
# draw a subset of the graph
boundary = list(nx.node_boundary(G, shortest_path))
G.add_nodes_from(shortest_path, color="red")
G.add_nodes_from(boundary, color="blue")
H = G.subgraph(shortest_path + boundary)
colors = nx.get_node_attributes(H, "color")
options = {"node_size": 1500, "alpha": 0.3, "node_color": colors.values()}
pos = nx.kamada_kawai_layout(H)
nx.draw(H, pos, **options)
nx.draw_networkx_labels(H, pos, font_weight="bold")
plt.show()
|
