Algorithms For Dummies

 Exploring the World of Graphs

Counting the degrees of separation

The  term  degrees  of  separation  defines  the  distance  between  nodes  in  a  graph. 

When  working  with  an  undirected  graph  without  weighted  edges,  each  edge 

counts for a value of one degree of separation. However, when working with other 

sorts of graphs, such as maps, where each edge can represent a distance or time 

value,  the  degrees  of  separation  can  become  quite  different.  The  point  is  that 

degrees of separation indicate some sort of distance. The example in this section 

(and the one that follows) relies on the following graph data. (You can find this 

code in the 

A4D; 10; Graph Navigation.ipynb

 file on the Dummies site as part 

of the downloadable code; see the Introduction for details.)

import networkx as nx

import matplotlib.pyplot as plt

%matplotlib inline

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

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

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

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

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

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

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

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

graph = nx.DiGraph(data)

pos=nx.spring_layout(graph)

nx.draw_networkx_labels(graph, pos)

nx.draw_networkx_nodes(graph, pos)

nx.draw_networkx_edges(graph, pos)

plt.show()

This is an expansion of the graph used in Chapter 6. Figure 10-3 shows how this 

graph appears so that you can visualize what the function call is doing. Note that 

this is a directed graph (

networkx

 

DiGraph

) because using a directed graph has 

certain  advantages  when  determining  degrees  of  separation  (and  performing  a 

wealth of other calculations).

To discover the degrees of separation between two items, you must have a starting 

point. For the purpose of this example, you can use node ’A’. The following code 

shows the required 

networkx

 package function call and output:

nx.shortest_path_length(graph, 'A')

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

 'H': 1}

---

CHAPTER 10