Lab 11

In Project 4, you will be required to manipulate graphs using the networkX package. In the in-lab problem, you need to fill in the body of the function replace_scc which replace all the strongly connected components of a graph with single nodes that you read in using import_edge_list(filename). You can use the following sample input. It's suggested that you use the strongly_connected_components function on the graph that you read in, which will return a list of components. Each list of components is a list of nodes. Thus, we suggest you create a new graph, and add the edges that go between components. You can check your graph by using pylab to draw it. Here is a template to start you off.

def replace_scc(G):
    components = strongly_connected_components(G)
 
    c = {}                                      # figure out which 
    for i in xrange(len(components)):           # component each node
        for node in components[i]:                  # belongs to
            c[node] = i + 1
 
    H = networkx.DiGraph()                           # create a new graph
    for u,v in G.edges_iter():                 # replace endpoints with
        H.add_edge(c[u], c[v])                 # new component numbers
 
    return H