`NetworkX`

.

Recall that a graph consists of a collection of nodes and a collection of edges between them. Graphs typically come in two flavors: undirected and directed, each having their own purpose. Here are a few model problems where each type of graph may occur.

Our first problem deals with an internet service provider who would like to expand its services and provide fiber optic internet to a town. Of course, they want to do this at the lowest cost.

In order to figure out the best way to do this, we'll model the locations we must connect as nodes in a graph and potential lines of cable to run as (undirected) edges. In addition, these edges are weighted by a cost due to things such as the cost of cable or the labor that goes into digging trenches for the cable. How should we solve this problem?

Of course, this is a rather simplified version of a more realistic problem, as we're focused on a narrow sense of connectivity. A more reasonable requirement would build in some redundency. For example, if a cable were damaged, the entire network wouldn't go down.

Our second problem deals with scheduling. What we've got is a bunch a tasks which must be completed; the catch is that some of the tasks can't be started until other ones are complete. For example, if you are building a house, you must excavate the ground before laying the foundation. On the other hand, determining the kind of lights or wallpaper you would like is completely independent and someone else can do this simultaneously.

We'll model this problem as a directed graph where the tasks are the nodes and the directed edges encode dependencies between tasks. So, maybe there is an edge "Task A -> Task B" if "Task B" requires "Task A" to be completed first. We'll see that there is a nice algorithm called topological sorting which gives us an ordered list of tasks which ensures that all dependencies are met as we complete the list.

`networkx`

for most of our graph related work and start with creating various types of graphs and drawing them.

*NetworkX is NOT meant for fancy graph drawing although with some effort it can be made to.*

*Graph Theory* by Frank Harary. The first two graphs to appear in the book are in the dedication to Kuratowski who proved a seminal theorem about graph planarity. These two graphs, the complete graph $K_5$ with 5 vertices and the complete bipartite graph $K_{3,3}$ play a leading role in that theorem.

Create and draw $K_5$:

In [1]:

```
%matplotlib inline
```

In [42]:

```
import networkx as nx
import matplotlib.pyplot as plt
K5 = nx.complete_graph(5)
nx.draw(K5)
plt.show()
```

`networkx`

using `matplotlib`

. So some things are controlled by `networkx`

and some by manipulating `matplotlib`

. For example, the circular layout produces a pentagonal shape:

In [3]:

```
nx.draw_circular(K5)
plt.show()
```

`matplotlib`

you can do this, for example, as follows:

In [4]:

```
nx.draw_circular(K5)
ax = plt.gca()
ax.set_aspect('equal')
```

`draw()`

or `draw_networkx()`

function. Computing the nodes is possible but we will leave the plot as is. Perhaps there is also a way to rotate the figure by $\pi/2$ counterclockwise, but if so then that is left to the reader.

Let us now repeat the above exercise with $K_{3,3}$.

In [5]:

```
K33 = nx.complete_bipartite_graph(3,3)
nx.draw(K33)
plt.show()
```

`networkx.draw_networkx`

gives more control on the drawing and also draws the node numbers by default.

In [6]:

```
nx.draw_networkx(K33)
```

In [7]:

```
positions = {0:[-1,1], 1:[0,1], 2:[1,1], 3:[-1,-1], 4:[0,-1], 5:[1,-1]}
nx.draw_networkx(K33, positions)
plt.show()
```

`matplotlib`

axis is drawn by default when using `draw_networkx()`

. To get rid of it we have to get a handle to the axis and turn off the drawing of axis and pass that axis to `draw_networkx()`

. The following code achieves this.

In [8]:

```
ax = plt.figure().gca()
ax.set_axis_off()
nx.draw_networkx(K33, positions)
plt.show()
```

`draw_networkx()`

. Lets draw $K_5$ and $K_{3,3}$ in the classic graph theory textbook style with nodes drawn as solid filled small circles without numbering.

In [9]:

```
ax = plt.figure().gca()
ax.set_axis_off()
options = {'node_size' : 100, 'node_color' : 'k'}
nx.draw_networkx(K33, positions, with_labels=False, **options)
plt.show()
```

There is a function in Networkx to create this graph. Let's create and draw the dodecahedral graph.

In [10]:

```
H = nx.dodecahedral_graph()
nx.draw_networkx(H)
plt.gca().set_aspect('equal')
```

In [11]:

```
front_face = [0, 10, 11, 18, 19]
back_face = [5, 6, 7, 14, 15]
middle = list(set(range(20)).difference(front_face + back_face))
shells = [front_face] + [middle] + [back_face]
positions = nx.shell_layout(H, shells)
nx.draw_networkx(H, positions)
ax = plt.gca()
ax.set_aspect('equal')
ax.set_axis_off()
```

`shell_layout()`

. It may be easier to just fix the positions of all vertices by hand rather than using `shell_layout()`

. But we will leave this as an exercise and move on.

In [12]:

```
G = nx.Graph()
G.add_node('A')
G.add_node('B')
G.add_node('C')
G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('A', 'C')
plt.figure()
nx.draw(G, with_labels=True)
plt.show()
```

This can be done with fewer commands by giving lists of nodes and edges.

In [13]:

```
G = nx.Graph()
G.add_nodes_from(['A', 'B', 'C'])
G.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'A')])
plt.figure()
nx.draw(G, with_labels=True)
plt.show()
```

*undirected* in that the direction of the edges doesn't matter. If the direction is important we can use `DiGraph`

object which gives us instances of *directed graphs*.

Lets recreate the previous graph as a directed graph.

In [14]:

```
G = nx.DiGraph()
G.add_nodes_from(['A', 'B', 'C'])
G.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'A')])
plt.figure()
nx.draw(G, with_labels=True)
plt.show()
```

In [15]:

```
G = nx.DiGraph()
G.add_edges_from([('A', 'B')])
plt.figure()
nx.draw(G, with_labels=True)
plt.show()
G = nx.DiGraph()
G.add_edges_from([('B', 'A')])
plt.figure()
nx.draw(G, with_labels=True)
plt.show()
```

*multigraph* of the KÃ¶nigsberg bridge problem. This was the problem that led to the creation of the field of graph theory in the hands of Euler. Through the city of KÃ¶nigsberg flowed the river Pregel. (The city is now known as Kaliningrad and is in Russia. The river is known as Pregloya.) There are 2 large islands that are part of the city. These were connected to each other and the mainland by 7 bridges. You can see a recent sattelite view on Google maps. The number and locations of the bridges are now different from Euler's times.

In [16]:

```
import networkx as nx
K = nx.MultiGraph()
K.add_nodes_from(['north', 'south', 'east', 'west'])
K.add_edges_from([('west', 'north'), ('west', 'north'),
('west', 'south'), ('west', 'south')])
K.add_edges_from([('east', 'north'), ('east', 'south')])
K.add_edge('east', 'west')
```

Let's explore the multigraph just made.

In [17]:

```
K.degree()
```

Out[17]:

In [18]:

```
K.edges()
```

Out[18]:

In [19]:

```
K.neighbors('west')
```

Out[19]:

In [20]:

```
K.neighbors('south')
```

Out[20]:

`pygraphviz`

to access Graphviz. It is easy to install. But we will not use it here and move on to the next example.

`Graph`

object. In general an electrical network can have elements in parallel and so a `MultiGraph`

would be more suitable in general. Let us label the 3 nodes in the top row as 0, 1, 2 and the nodes on the bottom row as 3, 4, 5.

In [21]:

```
import networkx as nx
import matplotlib.pyplot as plt
N = nx.Graph()
resistors = [(0,1), (1,2), (3,4), (4,5)]
capacitors = [(0,2)]
inductors = [(0,3), (1,4), (2,5)]
N.add_edges_from(resistors + capacitors + inductors)
```

In [22]:

```
N.nodes()
```

Out[22]:

In [23]:

```
N.edges()
```

Out[23]:

`draw_networkx()`

.

In [24]:

```
positions = {0:(-1,0.5), 1:(0,0.5), 2:(1,0.5), 3:(-1,0), 4:(0,0), 5:(1,0)}
ax = plt.figure().gca()
ax.set_axis_off(); ax.set_aspect('equal')
options = {'node_size':50, 'node_color':'k', 'with_labels':False}
nx.draw_networkx(N, pos=positions, ax=ax, **options)
```

In [25]:

```
ax = plt.figure().gca()
ax.set_axis_off()
options = {'node_size':50, 'node_color':'k', 'with_labels':False}
nx.draw_networkx(N, ax=ax, **options)
```

`draw()`

function and with the node numbering turned on but node color matching the white background.

In [26]:

```
nx.draw(N, node_color=(1,1,1))
```

`draw()`

function again.

In [27]:

```
nx.draw(N, node_color=(1,1,1))
```

`erdos_renyi_graph()`

, `watts_strogatz_graph()`

, and `barabasi_albert_graph()`

. There are several other functions for random graph generation.

- Create a circle graph and draw it.
- Create a lollipop graph and draw it.
- In one version of the ErdÅ‘sâ€“RÃ©nyi model for a random graph $G(n,p)$ there are $n$ vertices and each possible edge is included with a probability $p$ independent of the other edges. Create such graphs for a fixed value of the paramater $p$ for increasing values of $n$ and check if the number of edges is reasonable according to the model.

See details in the Graph Generators section of the documentation.

Graph traversal provides us with a way to explore a graph starting from a starting node. One example you can think about is, if we're stuck in a maze, graph traversal would allow us to explore until we found an exit. (But in a principled way...not just randomly wandering around.)

We saw this in an earlier project when we implemented depth-first search for a graph represented by a list. Let's see how we can leverage NetworkX to do this for us. We'll also see how to easily change to an alternative search strategy known as breadth-first search.

We'll start with a "double diamond" graph this time:

In [28]:

```
G = nx.DiGraph()
G.add_nodes_from([0, 1, 2, 3, 4, 5, 6])
G.add_edges_from([
(0, 1),
(0, 2),
(1, 3),
(2, 3),
(3, 4),
(3, 5),
(4, 6),
(5, 6),
])
plt.figure()
nx.draw(G, with_labels=True)
plt.show()
```

In [29]:

```
T = nx.depth_first_search.dfs_tree(G, 0)
plt.figure()
nx.draw(T, with_labels=True)
plt.show()
```

In [30]:

```
T = nx.depth_first_search.dfs_tree(G, 1)
plt.figure()
plt.subplot(121)
nx.draw(T, with_labels=True)
plt.subplot(122)
nx.draw(G, with_labels=True)
plt.show()
```

By changing one line of code, we can also employ a different search method:

In [31]:

```
T = nx.breadth_first_search.bfs_tree(G, 0)
plt.figure()
plt.subplot(121)
nx.draw(T, with_labels=True)
plt.subplot(122)
nx.draw(G, with_labels=True)
plt.show()
```

*single source* and *all pairs* shortest path.

We will use a weighted graph example from the Dijkstra's algorithm Wikipedia page.

In [32]:

```
G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5, 6])
G.add_weighted_edges_from([
(1, 2, 7),
(2, 4, 15),
(4, 5, 6),
(5, 6, 9),
(6, 1, 14),
(1, 3, 9),
(2, 3, 10),
(3, 4, 11),
(3, 6, 2),
], weight='distance') # call the weight values 'distance'
```

In [33]:

```
S = nx.shortest_path_length(G, 1, weight='distance')
S
```

Out[33]:

In [34]:

```
P = nx.shortest_path(G, 2)
P
```

Out[34]:

This says that the shortest path from 1 to 5 goes through 1 -> 2 -> 4 -> 5.

One of our motivating examples regarded an internet service provider who was laying down fiber optic cable to expand its services. We'll look a litte more carefully at how they may solve this problem.

Let's construct a simple "crossed-box" graph with weighted edges and try to compute a spanning tree of minimum weight in order to connect the network.

First we'll suppose that the weights come purely from the geometry of the box.One of our motivating examples regarded an internet service provider who was laying down fiber optic cable to expand its services. We'll look a litte more carefully at how they may solve this problem.

Let's construct a simple complete graph with 4 nodes whose geometry we will take to be that of a square. This graph will have weighted edges and we will try to compute a spanning tree of minimum weight in order to connect the network.

First we'll suppose that the weights come purely from the geometry of the graph in which the nodes are at the vertices of a square.

In [35]:

```
G = nx.Graph()
G.add_nodes_from([0, 1, 2, 3])
G.add_weighted_edges_from([
(0, 1, 1.0),
(1, 2, 1.0),
(2, 3, 1.0),
(3, 0, 1.0),
(0, 2, 2.0**.5),
(1, 3, 2.0**.5),
])
T = nx.minimum_spanning_tree(G)
plt.figure()
nx.draw(G, with_labels=True)
plt.show()
plt.figure()
nx.draw(T, with_labels=True)
plt.show()
```

In [37]:

```
G.edge[0][2]['weight'] = 0.4 # update the weight to take into account
# availible infrastructure
T = nx.minimum_spanning_tree(G) # recompute minimal spanning tree
plt.figure()
nx.draw(T, with_labels=True)
plt.show()
```

This time, we'll change terminology a little bit. We'll consider a graph which has certain capacities on its edges. For example, a road network may only be able to support a maximum amount of traffic. Or, a computer network may have limited bandwidth.

The goal is, we have two specials nodes called the source and the sink and we want to compute the maximum amount of "stuff" we can transport from the source to the sink. The constraint is, we cannot exceed the capacities of the edges and any node we use along the way must have the same amount of incoming "stuff" and outgoing "stuff".

If you'd like a more formal reference, take a look at this.

Let's try this on the simplest example: Just a single path.

In [38]:

```
G = nx.DiGraph()
G.add_nodes_from([0, 1, 2, 3])
G.add_weighted_edges_from([
(0, 1, 4),
(1, 2, 3),
(2, 3, 6),
], weight='capacity')
plt.figure()
nx.draw(G, with_labels=True)
plt.show()
```

In [39]:

```
nx.maximum_flow_value(G, 0, 3)
```

Out[39]:

This algorithm is quite broad in its application. We'll see one easy example in today's projects.