def convertir_en_conexo(grafo):
    nodos = grafo.nodes()
    nodos_conectados = nx.node_connected_component(grafo, 0)
    nodos.sort()
    nodos_conectados.sort()

    conectar = []
    while nodos != nodos_conectados:
        nodo_en_esta_componente = -1
        nodo_en_otra_componente = -1
        # elijo nodo de una y otra componente
        for v in nodos:
            if v not in nodos_conectados:
                nodo_en_otra_componente = v
            else:
                nodo_en_esta_componente = v
            if nodo_en_esta_componente != -1 and nodo_en_otra_componente != -1:
                break

        #recuerdo que conectar
        conectar.append((nodo_en_otra_componente, nodo_en_esta_componente))

        # actualizo nodos y nodos_conectados
        for v in nodos_conectados:
            nodos.remove(v)
        if len(nodos) > 0:
            nodos_conectados = nx.node_connected_component(grafo, nodo_en_otra_componente)
            nodos_conectados.sort()

    #conecto las componentes conexas
    for u, v in conectar:
        grafo.add_edge(u, v)

def segment(segment_graph, sorted_edges):
  for u,v,d in sorted_edges:
    connected1 = nx.node_connected_component(segment_graph, u)
    connected2 = nx.node_connected_component(segment_graph, v)
    if d['weight'] <= min_internal_diff(connected1, connected2, segment_graph):
      segment_graph.add_edge(u,v,weight=d['weight'])
  return segment_graph

def get_path_two_residues(hbfile, sourceRes, targetRes, pathCutoff, edgeCutoff, middleRes="ARGA0082"):
    '''Get all the pathways between two residues.
    
    The weight of each edge should be larger than or equal to the threshold,
    and the length of the pathway should be equal to or less than the number specified by lenLessThan.
    
    '''
    g = nx.Graph()
    for eachLine in open(hbfile):
        fields = eachLine.split()
        if len(fields) == 3 and float(fields[2]) < edgeCutoff:
            continue
        g.add_edge(fields[0], fields[1])
    if (sourceRes in g.nodes()) and (targetRes in g.nodes()) and (nx.has_path(g, sourceRes, targetRes)):
        for eachPath in sorted(nx.all_simple_paths(g, sourceRes, targetRes, pathCutoff), key=lambda p: len(p)):
            print eachPath
    else:
        print "No path"
        
        if (sourceRes in g.nodes()) and (targetRes in g.nodes()):
            print "Both %s and %s in the network but are not connected" % (sourceRes, targetRes)
            
        if sourceRes in g.nodes():
            print "%s in: " % sourceRes, nx.node_connected_component(g, sourceRes)
            if middleRes in nx.node_connected_component(g, sourceRes):
                print "%s connecting with %s" % (middleRes, sourceRes)
                
        if targetRes in g.nodes():
            print "%s in: " % targetRes, nx.node_connected_component(g, targetRes) 
            if middleRes in nx.node_connected_component(g, targetRes):
                print "%s connecting with %s" % (middleRes, targetRes)
                
        if middleRes in g.nodes():
            print "%s in: " % middleRes, nx.node_connected_component(g, middleRes) 

def find_nearest_neighbors2(db, a, nmax=10, rates=None, Peq=None):
    if rates is None:
        edges = [ (ts.minimum1, ts.minimum2, ts.energy) for ts in 
                 db.transition_states(order_energy=True)]
    else:
        edges = [((u,v), k*Peq[u]) for (u,v), k in 
                 rates.iteritems() if u<v]
        edges.sort(key=lambda uvk: -uvk[1])
        assert edges[0][1] > edges[1][1]
        edges = [uv for uv, k in edges]

    subtrees = nx.utils.UnionFind()
    subtrees[a]
    graph = nx.Graph()
    graph.add_node(a)
    for u,v, e in edges:
        uroot = subtrees[u]
        vroot = subtrees[v]
        if uroot != vroot:
            subtrees.union(u,v)
            graph.add_edge(u,v)
#            graph.add_edge(u,v)
            if subtrees[u] == subtrees[a]:
                print "energy", e, u._id, v._id
                cc = nx.node_connected_component(graph, a)
                if len(cc) >= nmax:
                    print "found a tree of sufficient size"
                    return cc
    print "finishing without having found a tree of sufficient size"
    cc = nx.node_connected_component(graph, a)
    return cc

def test_inversion_option(c1,c2,join_options,ograph,linked):
    a=c1
    b=linked[c1]
    c=c2
    d=linked[c2]

    #k=linked[internal_node]
    ograph.remove_edge(a,b)
    ograph.remove_edge(c,d)
                                                    ##                                                                        ---b a-------c d----
    if a in nx.node_connected_component(ograph,c):  ## exchance labels of a,b if necessary, so the nodes are in this config:  ---a b-------c d------ 
        x=b
        b=a
        a=x
     
                                                    ##                                                                        ---b a-------d c----
    if a in nx.node_connected_component(ograph,d):  ## exchance labels of a,b if necessary, so the nodes are in this config:  ---a b-------c d------ 
        x=b
        b=a
        a=x

        x=d
        d=c
        c=x

                                                    ##                                                                        ---a b-------d c----
    if b in nx.node_connected_component(ograph,d):  ## exchance labels of c,d if necessary, so the nodes are in this config:  ---a b-------c d------ 
        x=d
        d=c
        c=x

    n_scaffold = old_div(len(nx.node_connected_component(ograph,b)),2)
    print("inversion n nodes",n_scaffold)


    total_i_len = sum( ograph[i][j]['length'] for i,j in nx.bfs_edges(ograph,b) )
    print("inv len",total_i_len)
    if total_i_len < 10000.0 or n_scaffold<2:
        print("inversion length",total_i_len,n_scaffold,"too short")
        join_options.append( (0.0,(),() ) )                                                                                              
        ograph.add_edge(a,b,length=default_gapsize,contig=False)
        ograph.add_edge(c,d,length=default_gapsize,contig=False)

        return

    interc_score0 = intercalation_score_raw(a,b,d,ograph) 
    interc_score1 = intercalation_score_raw(a,c,d,ograph) 
    print("inversion0", interc_score0)
    print("inversion", interc_score1)
    join_options.append( (interc_score0,(),() ) )
    join_options.append( (interc_score1,((a,c),(b,d)),((a,b),(c,d)) ) )
    ograph.add_edge(a,b,length=default_gapsize,contig=False)
    ograph.add_edge(c,d,length=default_gapsize,contig=False)

    return

 def _calculate_groups_size_function(self, T):
     G = T.copy()
     for edge in T.edges():
         u, v = edge
         G.remove_edge(u, v)
         Nu = nx.node_connected_component(G, u)
         Nu = len(Nu)
         Nv = nx.node_connected_component(G, v)
         Nv = len(Nv)
         T[u][v]["group_size"] = T[u][v]["weight"] * min(Nu, Nv)
         G.add_edge(u, v)
         G[u][v] = T[u][v]

def testFun(filePath):
    import networkx as nx
    cmd.delete("all")
    
    cmd.fetch("1C3W")
    cmd.hide("lines", "all")
    cmd.show("cartoon", "1C3W")
    cmd.color("green", "all")
    
    #------------------------------ cmd.color("yellow", "resi 194 and resn GLU")
    #------------------------------- cmd.show("sticks", "resi 194 and resn GLU")
    highlightRes("GLUA0194", color="yellow")
    highlightRes("GLUA0204", color="yellow")
    
        
    g = loadHbTxt(filePath)
    allNodes = nx.node_connected_component(g, "GLUA0194")
    #===========================================================================
    # print allNodes
    #===========================================================================
    
    accRes = {}
    for line in open("/Users/xzhu/sibyl/BR/1C3W/hydro/def/raw/acc.res"):
        fields = line.split()
        resString = fields[1] + fields[2]
        acc = float(fields[4])
        accRes[resString] = acc
    
    colorThreshold = 0.02
    for eachResidue in accRes.keys():
        if accRes[eachResidue] > colorThreshold:
            if eachResidue in allNodes:
                print eachResidue
                highlightRes(eachResidue)

    def connected_paths(self, path_id, include_self=False):
        """
        Given an index of self.paths find other paths which
        overlap with that path.

        Parameters
        -----------
        path_id : int
          Index of self.paths
        include_self : bool
          Should the result include path_id or not

        Returns
        -----------
        path_ids :  (n, ) int
          Indexes of self.paths that overlap input path_id
        """
        if len(self.root) == 1:
            path_ids = np.arange(len(self.polygons_closed))
        else:
            path_ids = list(nx.node_connected_component(
                self.enclosure,
                path_id))
        if include_self:
            return np.array(path_ids)
        return np.setdiff1d(path_ids, [path_id])

    def toggleComponentSuspicious(self, state):
        if not self.selectedDomain:
            return

        graphComponent=nx.node_connected_component(self.suspiciousGraph,
                self.selectedDomain)
        for domain in graphComponent:
            node=self.suspiciousGraph.node[domain]

            if state==Qt.Checked:
                node['isMalicious']=True
                self.componentsTableModel.setComponentMalicious(domain, True)
            elif state==Qt.Unchecked:
                node['isMalicious']=False
                self.componentsTableModel.setComponentMalicious(domain, False)

        """
        update table data
        """
        if self.toggleHideNotMaliciousDomains.isChecked():
            self.toggleHideNonMalicious(Qt.Checked)
        else:
            self.toggleHideNonMalicious(Qt.Unchecked)

        self.updateStatusBar()

def get_connected_components_jaccard_similarity(documents, jaccard_threshold=.2, field_type="text"):
    """
        Find the connected components of documents sharing the same n-gram based on a threshold for Jaccard similarity.
    """
    document_text = {}
    for k,v in documents.items():
        try:
            document_text[k] = v[field_type]
        except:
            pass
    G = nx.Graph()
    similarity = {}
    ads = list(document_text)
    G.add_nodes_from(ads)

    for i in range(0,len(ads)-1):
        a = []
        for j in range(i+1,len(ads)):
            similarity[(ads[i],ads[j])] =  round(distance.jaccard(document_text[ads[i]], document_text[ads[j]]),3)

    for k, v in similarity.items():
        if v <= jaccard_threshold:
            G.add_edge(k[0],k[1])

    connected_components = set()

    for i in G.nodes():
        connected_components.add(str(sorted(nx.node_connected_component(G, i))))

    return connected_components

def sdg_min_cut(G, u, v):
    """
    Computes minimum u, v cut using Ford-Fulkerson Algorithm, from
    "Computing the minimum cut and maximum flow of undirected graphs" by
    Schroeder, Jonatan and Guedes, ALP and Duarte Jr, Elias P.
    :param G: graph
    :param u: source vertex
    :param v: sink vertex
    :return: partition of vertices of G, S1 and S2, as well as the corresponding max flow.
    """
    D = G.to_directed()
    max_flow = 0
    path_queue, flow = breadth_first_search_path(D, u, v)
    while flow != -1:
        max_flow += flow
        predecessor = path_queue.popleft()
        while len(path_queue) != 0:
            successor = path_queue.popleft()
            if D[predecessor][successor]['weight'] == flow:
                D.remove_edge(predecessor, successor)
                D.remove_edge(successor, predecessor)
            else:
                D[predecessor][successor]['weight'] -= flow
                D[successor][predecessor]['weight'] += flow
            predecessor = successor
        path_queue, flow = breadth_first_search_path(D, u, v)
    S1 = nx.node_connected_component(D.to_undirected(), u)
    S2 = {v for v in G.nodes_iter() if v not in S1}
    return S1, S2, max_flow

def test_endInversion_option(free_end,internal_node,join_options,ograph,linked):
    if free_end in linked:
        x=free_end
        free_end = internal_node
        internal_node = x
    print("end inversion",free_end,linked.get(free_end),internal_node,linked[internal_node])

    k=linked[internal_node]
    ograph.remove_edge(internal_node,k)

    if free_end in nx.node_connected_component(ograph,internal_node): 
        x=k
        k=internal_node
        internal_node=x

    sc = link_test(ograph,k,internal_node)
    join_options.append( (sc,(),()))
    print("end inversion existing:",sc)

    sc = link_test(ograph,free_end,internal_node)
    join_options.append( (sc ,((free_end,internal_node),),((internal_node,k),) ) ) 
    print("end inversion:",sc)

    ograph.add_edge(internal_node,k,length=default_gapsize, contig=False) 
    return

    def _reduce_graph(self, graph, min0list):
        """determine how much of the graph to include in the disconnectivity graph
        """
        used_nodes = []
        # make sure we include the subgraph containing min0
        if len(min0list) > 0:
            for min0 in min0list:
                nodes = nx.node_connected_component(graph, min0)
                if len(nodes) > 2:
                    used_nodes += nodes
                else:
                    print("dgraph: too few nodes connected to", min0)  
        if len(used_nodes) == 0: 
            # use the biggest connected cluster
            cc = sorted(nx.connected_components(graph), key=len, reverse=True)
            used_nodes += cc[0]  # list is ordered by size of cluster

        if self.subgraph_size is not None:
            node_lists = nx.connected_components(graph)
            for nodes in node_lists:
                if len(nodes) >= self.subgraph_size:
                    used_nodes += nodes

        newgraph = graph.subgraph(used_nodes).copy()
        return newgraph

def find_attractor(decStateTransMap):

    '''
        Arguments:
            -- 1. decStateTransMap
        Return:
            -- attractor
    '''
    attractor_list = nx.simple_cycles(decStateTransMap) #in case of deterministic system, any cycle without considering edge direction will be directed cycle.
    attractors = {}
    #attractors['fixed'] = []
    #attractors['cycle'] = []

    undirectedMap = nx.DiGraph.to_undirected(decStateTransMap)

    for u in attractor_list:
        attractors[u[0]] = {}
        if len(u) == 1:
            attractors[u[0]]['type'] = 'fixed'
        else:
            attractors[u[0]]['type'] = 'cycle'

    for v in attractors.iterkeys():
        basin = nx.node_connected_component(undirectedMap, v)
        attractors[v]['basin'] = basin
        attractors[v]['basin-size'] = len(basin)

    sorted_attractors = OrderedDict(sorted(attractors.items(), key=lambda kv: kv[1]['basin-size'], reverse=True))
    return sorted_attractors

def reduce_rates(rates, B, A=None):
    B = set(B)
    if A is not None:
        A = set(A)
        if A.intersection(B):
            raise Exception("A and B share", len(A.intersection(B)), "nodes")
    graph = nx.Graph()
    graph.add_edges_from(rates.iterkeys())

    # remove nodes not connected to B
    # TODO: this only works if B is fully connected
    connected_nodes = nx.node_connected_component(graph, iter(B).next())
    connected_nodes = set(connected_nodes)
    all_nodes = set(graph.nodes())
    if len(connected_nodes) != len(all_nodes):
        print "removing", len(all_nodes) - len(connected_nodes), "nodes that are not connected to B"

        rates = dict((uv, rate) for uv, rate in rates.iteritems() if uv[0] in connected_nodes)

        if B - connected_nodes:
            raise Exception("the nodes in B are not all connected")

        if A is not None:
            if A - connected_nodes:
                raise Exception("the A nodes are not all connected to the B nodes")

    return rates

def far_end(g,n):
    if not g.degree(n)==1:
        print("wtf: this should be a leaf")
        exit(0)
    for m in nx.node_connected_component(g,n):
        if (not m==n) and g.degree(m)==1:
            return m

def build_beatles_cluster():
    nodes = nx.node_connected_component(G, "303")
    print 'beatles nodes', len(nodes)
    p = r.pipeline()
    for node in nodes:
        p.sadd('BEATLES-SET', node)
    p.execute()

def generic_product_rule(g, op):
    sel1 = random.sample(g.nodes(), 2)
    if nx.has_path(g, *sel1):
        g.add_edge(*sel1)
        return sel1
    sel2 = random.sample(g.nodes(), 2)
    if nx.has_path(g, *sel2):
        g.add_edge(*sel2)
        return sel2
    elif op( len(nx.node_connected_component(g, sel2[0])) * len(nx.node_connected_component(g, sel2[1])), \
             len(nx.node_connected_component(g, sel1[0])) * len(nx.node_connected_component(g, sel1[1])) ):
        g.add_edge(*sel2)
        return sel2
    else:
        g.add_edge(*sel1)
        return sel1

 def connected_paths(self, path_id, include_self = False):
     if len(self.root) == 1:
         path_ids = np.arange(len(self.polygons_closed))
     else:
         path_ids = list(nx.node_connected_component(self.enclosure, path_id))
     if include_self: 
         return np.array(path_ids)
     return np.setdiff1d(path_ids, [path_id])

def wordrank(node):
    response = my_localRtr.get_Rel_one(node,"Fw", len(nx.node_connected_component(my_localRtr.G, node)) )
    nodesandpaths=[]
    for n,p in response.iteritems():
        path=p[1]
        nodesandpaths.append([n,path])
    response=json.dumps(nodesandpaths)
    return make_response(response)