Strict Standards: Declaration of Doku_Renderer_metadata::table_open() should be compatible with Doku_Renderer::table_open($maxcols = NULL, $numrows = NULL, $pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 480

Strict Standards: Declaration of Doku_Renderer_metadata::table_close() should be compatible with Doku_Renderer::table_close($pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 480

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.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

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():
            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()
 
cs190c/lab11_09.txt · Last modified: 2009/04/06 09:38 by tang
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki