# CS 190C LAB 11: Friday, April 3, 2009

## Basic graph manipulations in NetworkX

Remember, when working with NetworkX, you want this import:

`import networkx as nx`

This lets you use the NetworkX module with `nx.<function>` rather than `networkx.<function>`. When working with visualization, you must also `import pylab`.

• generate a graph by adding and deleting edges
```>>> G = nx.Graph()
>>> G.delete_edge(1, 2)
>>> G.nodes()
[1, 2]
>>> G.edges()
[]
>>> nx.draw(G)```
• generate graphs using a NetworX graph generators (grid, ladder, random)
```>>> pylab.figure()
<matplotlib.figure.Figure object at 0x175bd6f0>
>>> pylab.figure()
<matplotlib.figure.Figure object at 0x179c9070>
>>> nx.draw(nx.grid_graph([3, 4]))
>>> pylab.figure()
<matplotlib.figure.Figure object at 0x1f964b0>
>>> nx.draw_spectral(nx.erdos_renyi_graph(30, .3, seed=None))```
• read graph from a file (`import_graph` function in skeleton)
• non-mutating graph methods (informational)
```>>> G = nx.star_graph(10)
>>> len(G)
11
>>> G.nodes()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> G.edges()
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10)]
>>> G.number_of_edges()
10
>>> G.degree()
[10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]```
• mutating graph methods (such as `add_edge` and `delete_edge` from above)
```>>> G = nx.star_graph(10)
>>> G.remove_node(0)
>>> G.edges()
[]
>>> G.add_star([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
>>> G.edges()
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (0, 11)]
>>> G.add_path([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1])
>>> pylab.figure()
<matplotlib.figure.Figure object at 0x179ddfb0>
>>> nx.draw(G)
>>> G.clear()
>>> G.nodes()
[]
>>> G.edges()
[]```
• iterate over edges
```>>> G = nx.star_graph(10)
>>> for n1, n2 in G.edges_iter():
...     print n1, 'is connected to', n2
...
0 is connected to 1
0 is connected to 2
0 is connected to 3
0 is connected to 4
0 is connected to 5
0 is connected to 6
0 is connected to 7
0 is connected to 8
0 is connected to 9
0 is connected to 10```

## Visualizing graphs on NetworkX

As previously mentioned, we use matplotlib to visualize graphs. Unfortunately, IDLE has an issue where trying to draw multiple graphs on a single figure will cause it to freeze. Therefore, before drawing each graph, you should create a new figure (ie, `pylab.figure()`) to prevent this problem. There are several drawing methods in addition to simply `nx.draw`. They are listed in full here.

## Connected components algorithms

A graph has n connected components if there are n sets of nodes where in each set of nodes, each node has a path to every other node through edges that go with this set of nodes. In addition, there are no edges between these n sets of nodes (otherwise there are less than n connected components). There are several interesting functions:

• `nx.is_connected(G)` tells you if `G` is connected (aka has one connected component).
• `nx.number_connected_components(G)` tells you how many connected components are in `G`.
• `nx.connected_components(G)` returns a list of lists where each list in the other list is the list of all nodes in a connected component in `G`.
```>>> G1 = nx.complete_graph(5)
>>> G2 = nx.erdos_renyi_graph(100, 0.15)
>>> G3 = nx.tetrahedral_graph()
>>> G1.nodes()
[0, 1, 2, 3, 4]
>>> G2.nodes()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> nx.number_connected_components(G1)
1
>>> nx.number_connected_components(G2)
1
>>> nx.number_connected_components(G3)
1
>>> G4 = nx.disjoint_union(nx.disjoint_union(G1, G2), G3)
>>> G4.nodes()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
>>> nx.number_connected_components(G4)
3```

## In lab problem

Download the skeleton file, lab11sp09.py and example graphs: graph1sp09.txt graph2sp09.txt graph3sp09.txt

Code is provided for loading a graph in function `import_graph`. The main section requests a file and loads a graph for you, stored in variable `G`. Your task is as follows:

1. Determine the degree of every node in the graph and make a histogram of the node degrees
2. Determine whether the graph is connected.
3. If the graph is not connected, output a summary of its connected components (how many, how many nodes in each connected component). Assume there are k connected components. Add k-1 arbitrary edges that make the graph connected. Test that the graph is connected after the addition of the k-1 edges.
4. Visualize the graph.

You may generate your own graphs for testing as well (remove the file input if you do). Here are descriptions of the provided graphs:

1. `graph1.txt` is 10 disjoint nodes (none of them are connected)
2. `graph2.txt` is a ladder graph of length `4`
3. `graph3.txt` is several disjoint complete graphs.

## Solution

```import networkx as nx
import pylab

def import_graph(filename):
G = nx.Graph()
f = open(filename)
for edge in f:
s = edge.split('\t')
if len(s) == 1 and s[0].rstrip():
elif len(s) == 2:
a, b = s
f.close()
return G

if __name__ == '__main__':
filename = raw_input('Enter location of the graph: ')
G = import_graph(filename)
pylab.hist(G.degree())
pylab.figure()
if nx.is_connected(G):
print 'Graph is connected'
else:
print 'Graph is NOT connected'
components = nx.connected_components(G)
print 'There are', len(components), 'connected components.'
print 'Adding', len(components) - 1, 'edges to connect the graph.'
for i in range(1, len(components)):