def expand_liquid_oncotree(onco_tree):
    """
    Expand the _LIQUID_ oncotree node to all of its children

    :param onco_tree: Digraph of the Oncotree
    :returns liquid_children: All liquid tumor types in the Oncotree
             solid_children: All tumor types in the Oncotree minus "liquid_children"
    """

    # build the nodes for liquid.
    node1 = oncotreenx.lookup_text(onco_tree, "Lymph")
    node2 = oncotreenx.lookup_text(onco_tree, "Blood")

    nodes1 = list(nx.dfs_tree(onco_tree, node1))
    nodes2 = list(nx.dfs_tree(onco_tree, node2))
    nodes = list(set(nodes1).union(set(nodes2)))

    primary_tumors = get_primary_tumors()

    liquid_children_codes = []
    for n in nodes:
        liquid_children_codes.extend(list(nx.dfs_tree(onco_tree, n)))

    liquid_children = [onco_tree.node[nn]['text'] for nn in liquid_children_codes
                       if onco_tree.node[nn]['text'].strip() not in primary_tumors]

    # solid nodes are all other nodes
    all_nodes = set(list(onco_tree.nodes()))
    tmp_nodes = all_nodes - set(nodes)
    solid_children_codes = list(tmp_nodes)
    solid_children = [onco_tree.node[nn]['text'] for nn in solid_children_codes
                      if onco_tree.node[nn]['text'].strip() not in primary_tumors]

    return liquid_children, solid_children

 def test_dfs_tree_isolates(self):
     G = nx.Graph()
     G.add_node(1)
     G.add_node(2)
     T = nx.dfs_tree(G, source=1)
     assert_equal(sorted(T.nodes()), [1])
     assert_equal(sorted(T.edges()), [])
     T = nx.dfs_tree(G, source=None)
     assert_equal(sorted(T.nodes()), [1, 2])
     assert_equal(sorted(T.edges()), [])

 def test_dfs_tree(self):
     exp_nodes = sorted(self.G.nodes())
     exp_edges = [(0, 1), (1, 2), (2, 4), (4, 3)]
     # Search from first node
     T = nx.dfs_tree(self.G, source=0)
     assert_equal(sorted(T.nodes()), exp_nodes)
     assert_equal(sorted(T.edges()), exp_edges)
     # Check source=None
     T = nx.dfs_tree(self.G, source=None)
     assert_equal(sorted(T.nodes()), exp_nodes)
     assert_equal(sorted(T.edges()), exp_edges)
     # Check source=None is the default
     T = nx.dfs_tree(self.G)
     assert_equal(sorted(T.nodes()), exp_nodes)
     assert_equal(sorted(T.edges()), exp_edges)

def dfs_edges(G):
    """
    (source,target) for edges in directed spanning tree resulting from depth
    first search
    """
    DG = nx.dfs_tree(G)
    return [(src,targ) for targ in nx.dfs_postorder_nodes(DG) for src in DG.predecessors(targ)]

    def get_independent_components(self):
        components = set()

        for node in self.G.nodes_iter():
            components.add(frozenset(nx.dfs_tree(self.G, node)))

        return components

def _check_for_extreme_cases(G, G_copy, capacity, s, t):
    """
    Pads the missing capacities and checks for infinite capacity paths. 
    """
    sum_capacities = sum([G_copy[u][v][capacity] for u,v in 
                         G_copy.edges_iter() if capacity in 
                         G_copy.get_edge_data(u,v)])
    len_G_copy_edges = len(G_copy.edges())
    if len_G_copy_edges > 1:
        for u, v in G_copy.edges_iter():
            if capacity not in G_copy.get_edge_data(u,v):
                #pad the missing capacities with sum of all capacities
                G_copy[u][v][capacity] = sum_capacities
        # get edges that have no capacity attribute
        H = nx.DiGraph(((u,v) for u, v, eattr in G.edges_iter(data=True)
                        if capacity not in eattr))
        H.add_nodes_from(G_copy)
        for v in nx.dfs_tree(H,s):
            if v is t:
                raise nx.NetworkXUnbounded("Infinite capacity path, \
                                           flow unbounded above.")
    elif len_G_copy_edges == 1:
        for u, v in G_copy.edges_iter():
            if capacity not in G_copy.get_edge_data(u,v):
                # prune infinite capacities path
                raise nx.NetworkXUnbounded(
                    "Infinite capacity path, flow unbounded above.")

def chow_liu(data, mi_estimator=discrete_mutual_information):
    arguments = list(data.columns)
    g = nx.Graph()
    g.add_nodes_from(arguments)
    for src, dst in combinations(arguments, 2):
        g.add_edge(src, dst, weight=-mi_estimator(data[[src]], data[[dst]]))
    return DGM(nx.dfs_tree(nx.minimum_spanning_tree(g), arguments[0]))

def sanity_check_all_connected(tester, genome):
    
    tree = nx.dfs_tree(genome.graph, source=genome.starting_node)
    
    
    if len(tree) > 2:
        tester.assertEqual(len(tree), len(genome.graph))

    def extract_cancer_types(self):
        """
        Returns all cancer types located in the match tree

        :param g: DiGraph match tree
        :return: List of cancer types
        """

        diagnoses = []
        cancer_types_expanded = []
        primary_cancer_types = []
        excluded_cancer_types = []
        onco_tree = oncotreenx.build_oncotree(file_path=TUMOR_TREE)
        liquid_children_txt, solid_children_txt = expand_liquid_oncotree(onco_tree)

        # iterate through the graph
        for node_id in list(nx.dfs_postorder_nodes(self.g, source=1)):
            node = self.g.node[node_id]
            if node['type'] == 'clinical':
                if 'oncotree_primary_diagnosis' in node['value']:

                    diagnosis = node['value']['oncotree_primary_diagnosis']

                    n = oncotreenx.lookup_text(onco_tree, diagnosis.replace('!', ''))
                    children = list(nx.dfs_tree(onco_tree, n))

                    if diagnosis == '_SOLID_':
                        children_txt = solid_children_txt
                        primary_parent = 'All Solid Tumors'
                        parents_txt = ['All Solid Tumors']
                    elif diagnosis == '_LIQUID_':
                        children_txt = liquid_children_txt
                        primary_parent = 'All Liquid Tumors'
                        parents_txt = ['All Liquid Tumors']
                    else:
                        children_txt = [onco_tree.node[nn]['text'] for nn in children]

                        if n is not None:
                            parents, parents_txt, primary_parent = get_parents(onco_tree, n)
                        else:
                            parents_txt = []
                            primary_parent = ''

                    diagnoses.append(diagnosis)
                    if diagnosis.startswith('!'):
                        excluded_cancer_types.append(diagnosis.replace('!', ''))
                        excluded_cancer_types.extend(children_txt)
                    else:
                        primary_tumors = get_primary_tumors()
                        cancer_types_expanded.append(parse_diagnosis(diagnosis))
                        cancer_types_expanded.extend(children_txt)
                        cancer_types_expanded.extend([i for i in parents_txt if i.split()[0] not in primary_tumors])
                        primary_cancer_types.append(primary_parent)

        return {
            'diagnoses': list(set(i for i in diagnoses if i.strip() != 'root')),
            'cancer_types_expanded': list(set(i for i in cancer_types_expanded if i.strip() != 'root')),
            'primary_cancer_types': list(set(i for i in primary_cancer_types if i.strip() != 'root')),
            'excluded_cancer_types': list(set(i for i in excluded_cancer_types if i.strip() != 'root'))
        }

def all_dag_covers(_graph, condenseg, final_sccs, tree_type):
    initial_scc = _graph.node[_graph.graph["initial"]]["scc_index"]
    if tree_type=="bfs":
        condense_tree = networkx.bfs_tree(condenseg, initial_scc)
    elif tree_type=="dfs":
        condense_tree = networkx.dfs_tree(condenseg, initial_scc)
    rest_edges = [edge for edge in condenseg.edges() if edge not in condense_tree.edges()]

    all_tree_branch(_graph, condenseg, final_sccs, tree_type, condense_tree)
    dag_paths = condenseg.graph["condense_paths"]
    for rest_edge in rest_edges:
        path = networkx.shortest_path(condense_tree, initial_scc, rest_edge[0])
        _node = rest_edge[1]
        while True:
            if condense_tree.out_degree(_node)==0 and condense_tree.in_degree(_node)==1:
                if "_final" in str(_node):
                    path.append(_node)
                else:
                    path = path + condense_tree.node[_node]["continue_path"]
                break
            else:
                path.append(_node)
                _node = condense_tree.edge[_node].keys()[0]

        dag_paths.append(path)

    condenseg.graph["condense_paths"] = dag_paths
    return dag_paths

	def DFSCode(self,t):
		vertices=t.nodes()
		tdfs=nx.dfs_tree(t)
		sorted_edges=sorted(tdfs.edges(),key=operator.itemgetter(0), reverse=False)
		dfscode=""
		for s in sorted_edges:
			dfscode = dfscode + "#" + str(s[0]) + "-" + str(s[1])
		return dfscode

def petersenGraph():
    print "petersenGraph()"
    # Sigui G = (Vg,Eg) el graf original
    # Vèrtex inicial d'exploració: v
    # Sigui H = (Vh,Eh) el graf resultant d'aplicar DFS
    # El graf H està buit  
    G=nx.petersen_graph()
    print "number of edges: ",G.number_of_edges()
    print "number of nodes: ",G.number_of_nodes() 
    print "edges: ",G.edges()
    print "nodes: ",G.nodes()
    print "neighbors: ",G.neighbors()      
    H = nx.dfs_tree(G,0)
    Eh = {}
    Vh ={}
    visitats = {}
    explora(v)
    print "number of edges: ",H.number_of_edges()
    print "number of nodes: ",H.number_of_nodes() 
    print "edges: ",H.edges()
    print "nodes: ",H.nodes()
    print "neighbors: ",H.neighbors()   
    H = nx.dfs_tree(G,5)
    print "number of edges: ",H.number_of_edges()
    print "number of nodes: ",H.number_of_nodes() 
    print "edges: ",H.edges()
    print "nodes: ",H.nodes()
    print "neighbors: ",H.neighbors() 
    G.add_edge(1000,1001)
    print "number of edges: ",G.number_of_edges()
    print "number of nodes: ",G.number_of_nodes() 
    print "edges: ",G.edges()
    print "nodes: ",G.nodes()
    print "neighbors: ",G.neighbors()    
    H = nx.dfs_tree(G,0)
    print "number of edges: ",H.number_of_edges()
    print "number of nodes: ",H.number_of_nodes() 
    print "edges: ",H.edges()
    print "nodes: ",H.nodes()
    print "neighbors: ",H.neighbors() 
    H = nx.dfs_tree(G,1000)
    print "number of edges: ",H.number_of_edges()
    print "number of nodes: ",H.number_of_nodes() 
    print "edges: ",H.edges()
    print "nodes: ",H.nodes()
    print "neighbors: ",H.neighbors()    

def mincut(G,RG,s,t):
    dtree = nx.dfs_tree(RG,s)
    cut = []
    for u in dtree.nodes_iter():
        for v in G.edge[u].keys():
            if v not in dtree.node:
                cut.append((u,v))
    return cut

    def get(self, request, **kwargs):   #kwargs字典中包含url中路径的参数
        pk = kwargs['pk']

        NodeObj = ipran_node.objects.get(pk=pk)
        NodeName = NodeObj.NeName
        Ring = NodeObj.Ring

        linkList = ipran_link.objects.filter(Q(ring=Ring)&Q(isDelete=False)).values_list("source", "dest")
        linkList = list(linkList)
        nodeTuple = reduce(lambda x,y:x+y, linkList)     #[(1,2),(2,3)]-->(1,2,2,3)
        nodeTuple = tuple(set(nodeTuple))  #(1,2,2,3)-->{1,2,3}-->(1,2,3)
        rootNodeTuple = tuple(a for a in nodeTuple if re.match(r'^(HJ)|(HX)',a)) # 以HJ，HX开头的就是ASG
        rootLinkList = zip(*[iter(rootNodeTuple[i:]) for i in range(2)])   #(1,2,3,4)-->[(1,2),(2,3),(3,4)]    (1,)-->[]   ()-->[]
        print u"ASG:"
        for i in rootNodeTuple:
            print i

        linkList.extend(rootLinkList)

        G = nx.Graph()
        G.add_edges_from(linkList)
        
        try:
            CycleNode = nx.cycle_basis(G)[0]    #根据图生成环
        except:
            CycleNode = []    #无法生成环，则设环为空列表

        # print u"环路节点："
        # for i in CycleNode:
            # print i
        
        if NodeName in CycleNode:    #如果想要查询的节点为环上节点，则移除其它环节点(不包括支链节点)
            CycleNode.remove(NodeName)
            G.remove_nodes_from(CycleNode)
        else:    #如果想要查询的节点不为环上节点，则计算带环节点至该节点的最短路径经过的节点，并移除。
            ShortestNode = nx.dijkstra_path(G,rootNodeTuple[0],NodeName) 
            ShortestNode.remove(NodeName)
            G.remove_nodes_from(ShortestNode)
            
        # print u"剔除后余下的节点："
        # for i in G.node:
            # print i
        H = nx.dfs_tree(G,NodeName) #最后即可通过生成树协议获得节点所下带的节点
        Nnode = H.number_of_nodes()

        #接下来得分析下带的业务数及业务名称
        BusinessDictList = {'ring': Ring, '2G':[], '3G':[], 'LTE':[]}

        for node in H.nodes():
            print node
            NodeObj = ipran_node.objects.get(NeName=node)
            BusinessQuerySet = NodeObj.ipran_business_set.all()
            for BusinessObj in BusinessQuerySet:
                BusinessDictList.setdefault(BusinessObj.BusinessType, []).append(BusinessObj.TransStationName)
        
        return JsonResponse(BusinessDictList, safe=False)

def mutation(tree, graph):
    v1 = choice(tree.nodes())
    v2 = choice(tree.neighbors(v1)) # choice could be made to be proportional to weight of removed edge (the bigger the weight the more probably to be removed)
    #removal of an edge splits tree into 2 subtrees
    tree.remove_edge(v1,v2)

    # we obtain nodes accesible from each vertex
    n1 = nx.dfs_tree(tree, v1).nodes()
    n2 = nx.dfs_tree(tree, v2).nodes()

    # we list possible candidates for new connection
    possible_connections = [(u,v) for u in n1 for v in n2 if graph.has_edge(u, v)]

    if possible_connections == []:
        tree.add_edge(v1, v2) # no changes
    else:
        possible_connections.remove((v1,v2)) # remove previous connection
        edge = choice(possible_connections)
        tree.add_edge(edge[0], edge[1]) # new node

def prune(G, min_weight, source):
    for vertex in G.nodes():
        if sum(G.get_edge_data(*edge)['weight'] for edge in G.edges(vertex)) < min_weight:
            G.remove_node(vertex)
    tree = nx.dfs_tree(G, source)
    connected_vertices = {node for node in tree.nodes()}
    # Remove any orphaned vertexes.
    for vertex in G.nodes():
        if vertex not in connected_vertices:
            G.remove_node(vertex)

def new_simple_paths(graph):
    
    nodes = graph.in_degree_iter()
    for node, in_degree in nodes:
        if in_degree == 0:
            tmp_tree = nx.dfs_tree(graph, node)
            out_degree = tmp_tree.out_degree()
            for tree_node in tmp_tree.nodes_iter():
                if out_degree[tree_node] == 0:
                    path = nx.shortest_path(graph, node, tree_node)
                    if len(path) > 2:
                        yield path

def induce_tree(graph, node):
    """
    Given an undirected, acyclic graph, returns the tree induced by taking
    'node' as the root node. Preserves edge and node metadata.
    """
    tree = nx.dfs_tree(graph, node)
    # preserve node metadata
    for u in tree.nodes_iter():
        tree.node[u] = graph.node[u]
    # preserve edge metadata
    for s in tree.edges_iter():
        tree.edge[s[0]][s[1]] = graph.edge[s[0]][s[1]]
    return tree

def _sample_four_node_system(pzero_transition, pzero_other, fn_sample_data):
    nstates = 3
    G = nx.Graph()
    G.add_edge('a', 'b')
    G.add_edge('a', 'c')
    G.add_edge('a', 'd')
    nodes = set(G)
    root = random.choice(list(nodes))
    T = nx.dfs_tree(G, root)
    root_prior_distn = sample_distn1d(nstates, pzero_other)
    edge_to_P = {}
    for edge in T.edges():
        edge_to_P[edge] = sample_P(nstates, pzero_transition)
    node_to_data = fn_sample_data(nodes, nstates, pzero_other)
    return (T, edge_to_P, root, root_prior_distn, node_to_data)

def unilaterally_connected_components(G):
    graphs =sorted(nx.weakly_connected_component_subgraphs(G), key = len, reverse=True)
    weakly_connected_component_subgraphs_nodes=[]
    weakly_connected_component_subgraphs_edges=[]
    for gr in range(len(graphs)):
        graph='G' + str(gr+1)
        if len(graphs[gr].nodes()) >1 and len(graphs[gr].edges())>0:
            weakly_connected_component_subgraphs_nodes.append(graphs[gr].nodes())
            weakly_connected_component_subgraphs_edges.append(graphs[gr].edges())
    ucc=[]
    ucce=[]
    for i in range(len(weakly_connected_component_subgraphs_nodes)):
        j= weakly_connected_component_subgraphs_nodes[i]
        max_ccsn=[]
        max_ccse=[]
        for ki in j:
            Tki = nx.dfs_tree(G,ki)
            if len(Tki.nodes()) > len(max_ccsn):
                max_ccsn=Tki.nodes()
                max_ccse=Tki.edges()
                max_ki=ki
        rkwcc=list(set(j)-set(max_ccsn))
        if len(rkwcc)==0:
            ucc.append(max_ccsn)
            ucce.append(max_ccse)
        else:
            ucc.append(max_ccsn)
            ucce.append(max_ccse)
            ccsn=set()
            ccse=set()
            for kki in rkwcc:
                Tkki = nx.dfs_tree(G,kki)
                if Tkki.nodes() not in ucc:
                    ucc.append(Tkki.nodes())
                    ucce.append(Tkki.edges())
    return ucc, ucce