Table of Contents

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.

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:

>>> 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)
>>> nx.number_connected_components(G2)
>>> nx.number_connected_components(G3)
>>> 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)

In lab problem

Download the skeleton file, 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.


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
            G.add_edge(a, b.rstrip())
    return G
if __name__ == '__main__':
    filename = raw_input('Enter location of the graph: ')
    G = import_graph(filename)
    if nx.is_connected(G):
        print 'Graph is connected'
        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.'
            components = nx.connected_components(G)
            print 'Error: Graph still has', len(components), 'components.'