Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
cs190c:lab11 [2008/03/28 11:29]
alint
cs190c:lab11 [2008/04/01 21:40] (current)
alint
Line 1: Line 1:
 ====== Lab 11 ====== ====== Lab 11 ======
 +
  
 ===== First Hour ===== ===== First Hour =====
   * Return and go over exam 2.   * Return and go over exam 2.
   * In-Lab problem   * In-Lab problem
-     * 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 {{cs190c:​testgraph.txt|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 {{cs190c:​lab11.py|a template}} to start you off.+     * 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 {{cs190c:​testgraph.txt|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 {{cs190c:​lab11.py|a template}} to start you off. <code python>​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</​code>​
  
 ===== Second Hour ===== ===== Second Hour =====
 
cs190c/lab11.txt · Last modified: 2008/04/01 21:40 by alint
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki