Algorithms For Dummies

  Reconnecting the Dots 

     175

Creating the graph

To see how traversing a graph might work, you need a graph. The examples in this 

section rely on a common graph so that you can see how the two techniques work. 

The following code shows the adjacency list found at the end of Chapter 8. (You 

can find this code in the 

A4D; 09; Graph Traversing.ipynb

 file on the Dummies 

site as part of the downloadable code; see the Introduction for details.)

graph = {'A': ['B', 'C'],

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

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

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

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

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

The graph features a bidirectional path that goes from A, B, D, and F on one side 

(starting at the root) and A, C, E, and F along the second side (again, starting at 

the root). There are also connections (that act as possible shortcuts) going from B 

to  C,  from  C  to  D,  and  from  D  to  E.  Using  the  NetworkX  package  presented  in 

 Chapter 8 lets you display the adjacency as a picture so that you can see how the 

vertexes and edges appear (see Figure 9-1) by using the following code:

import numpy as np

import networkx as nx

import matplotlib.pyplot as plt

%matplotlib inline

Graph = nx.Graph()

for node in graph:

    Graph.add_nodes_from(node)

    for edge in graph[node]:

        Graph.add_edge(node,edge)

pos = { 'A': [0.00, 0.50], 'B': [0.25, 0.75],

        'C': [0.25, 0.25], 'D': [0.75, 0.75],

        'E': [0.75, 0.25], 'F': [1.00, 0.50]}

nx.draw(Graph, pos, with_labels=True)

nx.draw_networkx(Graph, pos)

plt.show()

---

176