Algorithms For Dummies

  Discovering Graph Secrets 

     205

The distance between node A and node A is 0, of course. The greatest degree of 

separation comes from node A to node D, which is 3. You can use this kind of infor-

mation to determine which route to take or to perform an analysis of the cost in 

gas versus the cost in time of various paths. The point is that knowing the short-

 est distance between two points can be quite important. The 

networkx

 package 

used for this example comes in a wide array of distance-measuring algorithms,  

as  described  at 

https://networkx.github.io/documentation/development/

reference/algorithms.shortest_paths.html

.

To see how using a directed graph can make a big difference when performing 

degrees-of-separation calculations, try removing the connection between nodes 

A and F. Change the data so that it looks like this:

data  = {'A': ['B', 'H'],

         'B': ['A', 'C'],

         'C': ['B', 'D'],

         'D': ['C', 'E'],

         'E': ['D', 'F', 'G'],

         'F': ['E', 'A'],

         'G': ['E', 'H'],

         'H': ['G', 'A']}

When  you  perform  the  call  to 

nx.shortest_path_length

  this  time,  the  output 

becomes quite different because you can no longer go from A to F directly. Here’s 

the new output from the call:

{'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 3, 'F': 4, 'G': 2,

 'H': 1}

FIGURE 10-3: 

A sample graph 

used for 

navigation 

purposes.

---

206

 

   

  PART 3