def communitySplits(self, graph):
		"""
		Compute the splits for the formation of communities. 

		Arguments:
			graph -  A networkx graph of digraph. 

		Returns:
			The graph with weak edges removed. 	
		"""

		nConnComp = nx.number_connected_components(graph)
		nComm = nConnComp

		while (nComm <= nConnComp):
			betweenness = nx.edge_betweenness_centrality(graph)
			if (len(betweenness.values()) != 0 ):
				max_betweenness = max(betweenness.values())
			else:
				break	
			for u,v in betweenness.iteritems():
				if float(v) == max_betweenness:
					graph.remove_edge(u[0], u[1])
			nComm = nx.number_connected_components(graph)			
		return graph		

def general_fiedler(G, k, trials, plotname):
    '''Number of components when you apply the threshold cut on a random vector in the span of 1st k'''
    v = keigenvectors(G, k)
    print v
    flag = 1
    x_data = []
    y_data = []
    for i in range(trials):
        z = randomvector(v)
        (y1, y2) = thresholdcut(z, 0)
        H1 = G.subgraph(y1)
        n1 = nx.number_connected_components(H1)
        H2 = G.subgraph(y2)
        n2 = nx.number_connected_components(H2)
        if n1 < n2:
            n = n1
        else:
            n = n2
        x_data.append(i)
        y_data.append(n)
        if n > k-1:
            flag = 0
            print 'Number of components: ' + str(n)
            print 'z = ' + str(z)
    if flag:
        print 'Not found, number of components: ' + str(n)
    k_data = [k-1 for x in x_data]
    plt.plot(x_data, y_data, 'ro')
    plt.plot(x_data, k_data, linewidth=2)
    plt.axis([0, trials, 0, k+10])
    plt.savefig(plotname)

def detectBetweenness(G, numClusters, sites, bipartite):
	Gnew = copy.deepcopy(G)
	numComponents = nx.number_connected_components(G)

	betweenness = nx.edge_betweenness_centrality(Gnew,  weight='capacity')
	pickle.dump(betweenness, open("betweennessUnipartite.p", "wb"))
	#betweenness = pickle.load("betweenessUnipartite.p", "rb")
	
	while (numComponents < numClusters):
		print "num components is now ",  numComponents ### REMEMBER TO DELETE THIS ###

		# calculate betweenness of each edge
		betweenness = nx.edge_betweenness_centrality(Gnew,  weight='capacity')

		## identify and remove the edge with highest betweenness
		max_ = max(betweenness.values())
		for k, v in betweenness.iteritems():
			if float(v) == max_:
				G.remove_edge(k[0], k[1])
		numComponents = nx.number_connected_components(G)

	clusters = {}
	i=0
	j = 0
	for component in list(nx.connected_components(Gnew)):
		for node in component:
			if node in sites:
				clusters[node] = i
				j +=1
		print j, "Nodes in cluster ", i
		j = 0
		i += 1

	return clusters

def deleteExtraEdges(cg, b,VERBOSE=False):            
    ndist = {}
    numConnected = nx.number_connected_components(cg)
    if( VERBOSE ):
        print("number of nodes is ",cg.number_of_nodes())
    for n in cg.neighbors(b):   
        # test whether deleting the edge between n and b increases
        # the number of connected components
        cg.remove_edge(b,n)
        newNumConnected = nx.number_connected_components(cg)
        if( newNumConnected == numConnected ): # then this could be a valid deletion
            # compute the step distance from n to its neighbor b
            if( VERBOSE ):
                print("the edge between %s and %s can be cut without changing the topology of the graph"%(b,n))
            ndist[(b,n)] = math.sqrt((n[0]-b[0])**2+(n[1]-b[1])**2+(n[2]-b[2])**2)
        cg.add_edge(b,n)
    if( ndist ):
        items = list(ndist.items())
        #rearrange node,distance pairing so we can sort on distance
        k,v = list(zip(*items))
        items = list(zip(v,k))
        maxNeighbor = max(items)
        # cut the maximum step length edge that is valid to cut
        if( VERBOSE ):
            print("removing edge",maxNeighbor[1][0],maxNeighbor[1][1])
        cg.remove_edge(maxNeighbor[1][0],maxNeighbor[1][1])
        cg = deleteExtraEdges(cg,b)
    return cg

	def communities(self, nCommunities, weight=None):
		"""
		Compute communities.

		Parameters
		----------
		nCommunities - number of communities to be returned.
			This is added to simplify the process, the original GN algorithm doesn't 
			need predecided number of communities. 
			Other measures like a threshold on betweenness centrality can be used instead.
		
		weight (string) - If None, all edge weights are considered equal. 
			Otherwise holds the name of the edge attribute used as weight. 


		Returns
		--------
		A list of communities where each community is a list of the nodes in the community.	 
		"""
		gr = self.g
		n = nx.number_connected_components(gr)
		components = nx.connected_components(gr)

		while (n < nCommunities):
			gr = self.communitySplits(gr, weight=weight)
			components = nx.connected_components(gr)
			n = nx.number_connected_components(gr)
			if gr.number_of_edges() == 0:
				break
		return components

def get_bridges(graph):
    all_edges = graph.edges(keys=True,data=True)
    for e in all_edges:
        graph.remove_edge(*e[:-1])
        removed_comps = nx.number_connected_components(graph)
        graph.add_edge(*e) # Will maintain the original key associated with this edge
        if nx.number_connected_components(graph) < removed_comps:
            yield e

def Girvannewman(G):
    initialcomp = nx.number_connected_components(G)
    '''totalnumcomp = initialcomp
    while totalnumcomp <= initialcomp:'''
    bw = nx.edge_betweenness_centrality(G)
    maximum_value = max(bw.values())
    for key, value in bw.iteritems():
        if float(value) == maximum_value:
            G.remove_edge(key[0],key[1])
    totalnumcomp = nx.number_connected_components(G)

def get_number_of_components(filename):
  import networkx as nx
  threshold = 0
  f = open(filename[:-4]+'_components.dat','w')
  for i in range(0,101):
    threshold = float(i)/100
    G = get_threshold_matrix(filename, threshold)
    print 'number of connected components:', nx.number_connected_components(G)
    f.write("%f\t%d\n" % (threshold, nx.number_connected_components(G)))
  f.close()

def convert_to_lineage():
	inf_modes = ['incidence_p', 'incidence_c']
	exits = ['c_to_death', 'remove_s', 'remove_p', 'remove_c']
	
	parent = "/home/ethan/Dropbox/pkl/"
	index = 0
	
	for file in os.listdir(parent):
		print file
		infile = open(parent + file, 'r')
		
		lineage = nx.DiGraph(weighted=True)		
		abm = cPickle.load(infile)
		tree = abm.tree
		history = abm.agent_history
		infected = sorted(tree.nodes(), key=lambda x: x.i_time)
		terminal_map = {}
		
		for i in infected:
			try: 
				a = history[i]
			except KeyError:
				infected.remove(i)
	
		for i in infected:
			out = []
			out.append(i)
			nei = sorted(tree.neighbors(i), key=lambda x: x.i_time)
			for n in nei:
				if n.i_time > i.i_time:
					out.append(n)
			
			end_time = 5000
			
			terminus = Agent()
			terminus.i_time = end_time 
			terminus.ID = i.ID
			
			for event in history[i]:
					if event[0] in exits:
						terminus.i_time = event[1]
		
			out.append(terminus)
			terminal_map[i] = terminus 
			
			for x in range(len(out) - 1):
				lineage.add_edge(out[x], out[x + 1], data=abs(out[x].i_time - out[x + 1].i_time))
		
		dic = {'lineage' : lineage, 'history' : history, 'terminal map' : terminal_map}
		out = open(parent + 'lin' + str(index) + '.pkl', 'w')
		cPickle.dump(dic, out)
		print nx.number_connected_components(lineage.to_undirected()), nx.number_connected_components(tree)
		infile.close()
		out.close()		
		index += 1

 def info(self):
     print "============================"
     print nx.info(self.G)
     print "============================"
     #print "degree distribution: "
     #print nx.degree_histogram(self.G)
     print "============================"
     print "number of connected components:"
     if self.directed_graph == False:
         print nx.number_connected_components(self.G)
     print "============================"

def getTrafficConnectedComponentGraph(G):
    H = G.copy()
    to_remove = []
    for (s,d) in H.edges(): 
       if H[s][d]['weight'] <= 2:
           to_remove.extend([(s,d)])
    H.remove_edges_from(to_remove)
    #print list(networkx.connected_components(H))
    print networkx.number_connected_components(H)
    Gc = max(networkx.connected_component_subgraphs(H), key=len)
    #drawGraph(Gc, connected=True)
    return Gc

def CmtyGirvanNewmanStep(G):
    init_ncomp = nx.number_connected_components(G)    #no of components
    ncomp = init_ncomp
    while ncomp <= init_ncomp:
        bw = nx.edge_betweenness_centrality(G, weight='weight')    #edge betweenness for G
        #find the edge with max centrality
        max_ = max(bw.values())
        #find the edge with the highest centrality and remove all of them if there is more than one!
        for k, v in bw.iteritems():
            if float(v) == max_:
                G.remove_edge(k[0],k[1])    #remove the central edge
        ncomp = nx.number_connected_components(G)    #recalculate the no of components

 def IsDivided(fragment):
     nodes = set()
     for ring in fragment:
         nodes |= set(_rings[ring])
     G2 = _G.copy()
     ebunch = []
     for i in nodes:
         for j in _G.neighbors(i):
             ebunch.append((i,j))
     #G2.remove_edges_from(ebunch)
     G2.remove_nodes_from(nodes)
     logging.debug("NCOMPO: {0} {1}".format(nx.number_connected_components(G2),_ncompo))
     return nx.number_connected_components(G2) > _ncompo

    def plot_additional(self, home_nodes, levels=0):
        """Add nodes to existing plot.  Prompt to include link to existing
        if possible.  home_nodes are the nodes to add to the graph"""

        new_nodes = self._neighbors(home_nodes, levels=levels)
        new_nodes = home_nodes.union(new_nodes)

        displayed_data_nodes = set([ v['dataG_id']
                            for k,v in self.dispG.node.items() ])

        # It is possible the new nodes create a connection with the existing
        #  nodes; in such a case, we don't need to try to find the shortest
        #  path between the two blocks
        current_num_islands = nx.number_connected_components(self.dispG)
        new_num_islands = nx.number_connected_components(
            self.dataG.subgraph(displayed_data_nodes.union(new_nodes)))
        if new_num_islands > current_num_islands:
            # Find shortest path between two blocks graph and, if it exists,
            #  ask the user if they'd like to include those nodes in the
            #  display as well.
            # First, create a block model of our data graph where what is
            #  current displayed is a block, the new nodes are a a block
            all_nodes = set(self.dataG.nodes())
            singleton_nodes = all_nodes - displayed_data_nodes - new_nodes
            singleton_nodes = map(lambda x: [x], singleton_nodes)
            partitions = [displayed_data_nodes, new_nodes] + \
                         list(singleton_nodes)
            B = nx.blockmodel(self.dataG, partitions, multigraph=True)

            # Find shortest path between existing display (node 0) and
            #  new display island (node 1)
            try:
                path = nx.shortest_path(B, 0, 1)
            except nx.NetworkXNoPath:
                pass
            else:
                ans = tkm.askyesno("Plot path?", "A path exists between the "
                  "currently graph and the nodes you've asked to be added "
                  "to the display.  Would you like to plot that path?")
                if ans: # Yes to prompt
                    # Add the nodes from the source graph which are part of
                    #  the path to the new_nodes set
                    # Don't include end points because they are the two islands
                    for u in path[1:-1]:
                        Gu = B.node[u]['graph'].nodes()
                        assert len(Gu) == 1; Gu = Gu[0]
                        new_nodes.add(Gu)

        # Plot the new nodes
        self._plot_additional(new_nodes)

def _remove_max_edge(G, weight=None):
    """
    Removes edge with the highest value on betweenness centrality.
    Repeat this step until more connected components than the connected
    components of the original graph are detected.
    """
    number_components = nx.number_connected_components(G)
    while nx.number_connected_components(G) <= number_components and G.number_of_edges():
        betweenness = nx.edge_betweenness_centrality(G, weight=weight)
        max_value = max(betweenness.values())
        # Use a list of edges because G is changed in the loop
        for edge in list(G.edges()):
            if betweenness[edge] == max_value:
                G.remove_edge(*edge)

def girvan_newman_step(G):
    '''
    INPUT: Graph G
    OUTPUT: None

    Run one step of the Girvan-Newman community detection algorithm.
    Afterwards, the graph will have one more connected component.
    '''
    init_ncomp = nx.number_connected_components(G)
    ncomp = init_ncomp
    while ncomp == init_ncomp:
        bw = Counter(nx.edge_betweenness_centrality(G))
        a, b = bw.most_common(1)[0][0]
        G.remove_edge(a, b)
        ncomp = nx.number_connected_components(G)

def sensi_diameter(G):
    import networkx as nx
    
    """
    Compute graph sensitivity to node removal, in terms of
    the difference in graph diameter on the removal of each
    node in turn.
     
    This uses local function x_diameter(G), which is modified
    from networkx.diamter(G) to work on XGraphs.
    
    DL Urban (9 Feb 2007)
    """
    
    # Starting diameter for full graph:
    
    if nx.is_connected(G):
        d0 = x_diameter(G)
    else:
        G0 = nx.connected_component_subgraphs(G) [0] # the largest subgraph
        d0 = x_diameter(G0)
        nc = nx.number_connected_components(G)	     # how many are there?
    
    sensi = {}
    
    for node in G.nodes():
        ex = G.edges(node) 		# a set of edges adjacent to node; 
        G.delete_edges_from(ex)		# remove all of these,
        G.delete_node(node)		# and then kill the node, too
        if nx.is_connected(G):
            dx = x_diameter(G)
            cuts = 0
        else:
            Gx = nx.connected_component_subgraphs(G) [0]	# the biggest
            ncx = nx.number_connected_components(G)
            if nc == ncx:
                cuts = 0
            else:
                cuts = 1
            dx = x_diameter(Gx)
        delta = d0 - dx
        G.add_node(node)		# put the node and edges back again
        G.add_edges_from(ex)
        sensi[node] = (cuts, delta)
 

    # create and return a tuple (cuts, delta)
    return sensi

def genMutants(G, params):
    """ 
    Returns a list of mutant networks obtained from the given network G, 
    using mutation parameters in params.
    """
    Vcount = len(G)
    Ecount = len(G.edges())
    mutants = []
    for i in range(params["mutantsPerEpoch"]):
        mutantG = G.copy()
        rewirings = 0
        while rewirings <= params["rewiringsPerMutant"]:
            u, v = mutantG.edges()[random.randrange(Ecount)]
            uNew = random.choice([u, v])
            vNew = random.randrange(Vcount)
            if uNew == vNew or mutantG.has_edge(uNew, vNew):
                continue
            mutantG.remove_edge(u, v)
            mutantG.add_edge(uNew, vNew)
            if networkx.number_connected_components(mutantG) > 1:
                mutantG.remove_edge(uNew, vNew)
                mutantG.add_edge(u, v)
            else:
                rewirings += 1
        mutants.append(mutantG)
    return mutants

    def __init__(self, fname, interactive=True):
        self.fname = fname
        self.graph = nx.read_gpickle(fname)
        
        #apply_workaround(self.graph, thr=1e-3)
        #remove_intersecting_edges(self.graph)

        print "Number of connected components:", \
                nx.number_connected_components(self.graph)

        self.selected_path_verts = []
        
        if interactive:
            self.fig = plt.figure()
            self.path_patch = None
            
            G_p = nx.connected_component_subgraphs(self.graph)[0]
            #G_p = nx.connected_component_subgraphs(prune_graph(self.graph))[0]

            plot.draw_leaf(G_p, fixed_width=True)

            plt.ion()
            plt.show()

            self.edit_loop()    

def get_characteristics(G, filename):
  import networkx as nx
  print 'calculating characteristics'
    
  n_nodes = nx.number_of_nodes(G)
  n_edges = nx.number_of_edges(G)
  n_components = nx.number_connected_components(G)
  print 'number of nodes:', n_nodes
  print 'number of edges:', n_edges
  print 'number of components:', n_components
 
  print 'degree histogram'
  check_sum = 0.
  degree_hist = {}
  for node in G:
    if G.degree(node) not in degree_hist:
      degree_hist[G.degree(node)] = 1
    else:
      degree_hist[G.degree(node)] += 1
    
  keys = degree_hist.keys()
  keys.sort()
  for item in keys:
    print item, degree_hist[item]
    check_sum += float(degree_hist[item])/float(n_nodes)
    
  print "check sum: %f" % check_sum
            
  #print 'clustering coefficient'
  print 'clustering coefficient of full network', nx.average_clustering(G)
  return 0