Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

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:

Out:

Loaded words_dat.txt containing 5757 five-letter English words.
Two words are connected if they differ in one letter.
Graph has 5757 nodes with 14135 edges
853 connected components
Shortest path between chaos and order is
chaos
choos
shoos
shoes
shoed
shred
sired
sided
aided
odder
order
Shortest path between nodes and graph is
nodes
lodes
lores
lords
grape
graph
Shortest path between pound and marks is
None


import gzip
from string import ascii_lowercase as lowercase

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
)
for word, cand in candgen:
return G

def words_graph():
"""Return the words example graph from the Stanford GraphBase"""
fh = gzip.open("words_dat.txt.gz", "r")
words = set()
line = line.decode()
if line.startswith("*"):
continue
w = str(line[0:5])
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(f"Graph has {nx.number_of_nodes(G)} nodes with {nx.number_of_edges(G)} edges")
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:
sp = nx.shortest_path(G, source, target)
for n in sp:
print(n)
except nx.NetworkXNoPath:
print("None")


Total running time of the script: ( 0 minutes 0.142 seconds)

Gallery generated by Sphinx-Gallery