Algorithms For Dummies

 Exploring the World of Graphs

Notice that the loss of the path has changed some of the degrees of separation. 

The distance to node F is now the longest at 4.

Walking a graph randomly

You might find a need to walk a graph randomly. The act of walking the graph 

randomly,  rather  than  look  for  a  specific  path,  can  simulate  natural  activities, 

such as an animal foraging for food. It also plays in to all sorts of other interesting 

activities, such as playing games. However, random graph walking can have prac-

tical aspects. For example, a car is held up in traffic because of an accident, so the 

shortest path is no longer available. In some cases, choosing a random alternative 

might work best because traffic along the second shortest route could be heavy as 

a result of the traffic jam along the shortest route.

The 

networkx

 package doesn’t provide the means for obtaining a random path 

directly. However, it does provide the means for finding all available paths, after 

which you can select a path from the list randomly. The following code shows how 

this process might work using the graph from the previous section.

import random

random.seed(0)

paths = nx.all_simple_paths(graph, 'A', 'H')

path_list = []

for path in paths:

    path_list.append(path)

    print("Path Candidate: ", path)

sel_path = random.randint(0, len(path_list) - 1)

print("The selected path is: ", path_list[sel_path])

Path Candidate:  ['A', 'B', 'C', 'D', 'E', 'G', 'H']

Path Candidate:  ['A', 'H']

Path Candidate:  ['A', 'F', 'E', 'G', 'H']

The selected path is:  ['A', 'H']

The code sets the seed to a specific value to ensure that you get the same result 

every time. However, by changing the seed value, you can see different results 

from  the  example  code.  The  point  is  that  even  the  simple  graph  shown  in 

 Figure 10-3 offers three ways to get from node A to node H (two of which are 

 definitely longer than the selected path in this case). Choosing just one of them 

ensures that you get from one node to the other, albeit by a potentially round-

about way.

---

CHAPTER 11