# Differences

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

 cs190c:lab11_09 [2009/04/03 11:24]tang cs190c:lab11_09 [2009/04/06 09:38] (current)tang Both sides previous revision Previous revision 2009/04/06 09:38 tang 2009/04/03 11:24 tang 2009/04/01 16:06 seh created 2009/04/06 09:38 tang 2009/04/03 11:24 tang 2009/04/01 16:06 seh created Line 111: Line 111: - ''​graph2.txt''​ is a ladder graph of length ''​4''​ - ''​graph2.txt''​ is a ladder graph of length ''​4''​ - ''​graph3.txt''​ is several disjoint complete graphs. - ''​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()