Table of Contents

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.add_edge(1, 2) >>> 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> >>> nx.draw(nx.ladder_graph(3)) >>> 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.add_node(11) >>> 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

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.

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

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:

- Determine the degree of every node in the graph and make a histogram of the node degrees
- Determine whether the graph is connected.
- 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.
- 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:

`graph1.txt`

is 10 disjoint nodes (none of them are connected)`graph2.txt`

is a ladder graph of length`4`

`graph3.txt`

is several disjoint complete graphs.

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(): G.add_node(s[0].rstrip()) elif len(s) == 2: a, b = s G.add_edge(a, b.rstrip()) 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)): G.add_edge(components[0][0], components[i][0]) if nx.is_connected(G): print 'Graph is now connected.' else: components = nx.connected_components(G) print 'Error: Graph still has', len(components), 'components.' nx.draw(G) pylab.show()