def test_disconnected_graph():
    # https://github.com/networkx/networkx/issues/1144
    G = nx.Graph()
    G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4)])
    assert_false(nx.is_tree(G))

    G = nx.DiGraph()
    G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4)])
    assert_false(nx.is_tree(G))

def euler_tour(G, node=None, seen=None, visited=None):
    """
    definition from
    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.8615&rep=rep1&type=pdf

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> edges = [
        >>>     ('R', 'A'), ('R', 'B'),
        >>>     ('B', 'C'), ('C', 'D'), ('C', 'E'),
        >>>     ('B', 'F'), ('B', 'G'),
        >>> ]
        >>> G = nx.Graph(edges)
        >>> node = list(G.nodes())[0]
        >>> et1 = euler_tour(G, node)
        >>> et2 = euler_tour_dfs(G, node)
    """
    if node is None:
        node = next(G.nodes())
    if visited is None:
        assert nx.is_tree(G)
        visited = []
    if seen is None:
        seen = set([])
    visited.append(node)
    for c in G.neighbors(node):
        if c in seen:
            continue
        seen.add(c)
        euler_tour(G, c, seen, visited)
        visited.append(node)
    return visited

 def add_edge(self, u, v):
     print('[euler_tour_forest] add_edge(%r, %r)' % (u, v))
     if self.has_edge(u, v):
         return
     ru = self.find_root(u)
     rv = self.find_root(v)
     if ru is None:
         self.add_node(u)
         ru = u
     if rv is None:
         self.add_node(v)
         rv = v
     assert ru is not rv, (
         'u=%r, v=%r not disjoint, can only join disjoint edges' % (u, v))
     assert ru in self.trees, 'ru must be a root node'
     assert rv in self.trees, 'rv must be a root node'
     subtree1 = self.trees[ru]
     subtree2 = self.trees[rv]
     del self.trees[rv]
     new_tree = nx.compose(subtree1, subtree2)
     new_tree.add_edge(u, v)
     self.trees[ru] = new_tree
     print(list(new_tree.nodes()))
     assert nx.is_connected(new_tree)
     assert nx.is_tree(new_tree)

def question4(T, node1, node2):
    BSTG=nx.from_numpy_matrix(np.matrix(T))
    if (nx.is_tree(BSTG) & check_sum(T)):
        path = nx.all_simple_paths(BSTG, node1,  node2)
        return min(list(path)[0])
    else:
        print ("This graph is not a binary search tree")
        return None 

def inspectlabels(milestone,sent):
    for h,d in sent.edges():
        if type(sent[h][d]['deprel']) == str:
            pass
        else:
            print(milestone,"ARLAMA",sent)
    if not nx.is_tree(sent):
        print("not tree")

 def test_default_flow_function_karate_club_graph(self):
     G = nx.karate_club_graph()
     nx.set_edge_attributes(G, 1, 'capacity')
     T = nx.gomory_hu_tree(G)
     assert_true(nx.is_tree(T))
     for u, v in combinations(G, 2):
         cut_value, edge = self.minimum_edge_weight(T, u, v)
         assert_equal(nx.minimum_cut_value(G, u, v),
                      cut_value)

 def test_karate_club_graph_cutset(self):
     G = nx.karate_club_graph()
     nx.set_edge_attributes(G, 1, 'capacity')
     T = nx.gomory_hu_tree(G)
     assert_true(nx.is_tree(T))
     u, v = 0, 33
     cut_value, edge = self.minimum_edge_weight(T, u, v)
     cutset = self.compute_cutset(G, T, edge)
     assert_equal(cut_value, len(cutset))

 def span_makes_subtree(self, initidx, endidx):
     G = nx.DiGraph()
     span_nodes = list(range(initidx,endidx+1))
     span_words = [self.node[x]["form"] for x in span_nodes]
     G.add_nodes_from(span_nodes)
     for h,d in self.edges():
         if h in span_nodes and d in span_nodes:
             G.add_edge(h,d)
     return nx.is_tree(G)

 def test_davis_southern_women_graph(self):
     G = nx.davis_southern_women_graph()
     nx.set_edge_attributes(G, 'capacity', 1)
     for flow_func in flow_funcs:
         T = nx.gomory_hu_tree(G, flow_func=flow_func)
         assert_true(nx.is_tree(T))
         for u, v in combinations(G, 2):
             cut_value, edge = self.minimum_edge_weight(T, u, v)
             assert_equal(nx.minimum_cut_value(G, u, v),
                          cut_value)

 def test_florentine_families_graph(self):
     G = nx.florentine_families_graph()
     nx.set_edge_attributes(G, 1, 'capacity')
     for flow_func in flow_funcs:
         T = nx.gomory_hu_tree(G, flow_func=flow_func)
         assert_true(nx.is_tree(T))
         for u, v in combinations(G, 2):
             cut_value, edge = self.minimum_edge_weight(T, u, v)
             assert_equal(nx.minimum_cut_value(G, u, v),
                          cut_value)

def _graphml2nx(fname):
	g=nx.DiGraph()
	def _attrdict(node):
		attrs=node.attributes()
		return {key:attrs[key].value for key in attrs if key not in attr_blacklist}
	parser=GraphMLParser()
	imported_graph=parser.parse(fname)
	edges=[(edge.node1.id, edge.node2.id) for edge in imported_graph.edges()]
	nodes=[(node.id, _attrdict(node)) for node in imported_graph.nodes()]
	g.add_edges_from(edges)
	g.add_nodes_from(nodes)
	assert(nx.is_tree(g))
	assert(nx.is_directed(g))
	return g

 def default(self, obj):
     if isinstance(obj, np.ndarray):
         return obj.tolist()
     elif isinstance(obj, np.generic):
         return obj.item()
     elif isinstance(obj, nx.Graph) or isinstance(obj, nx.DiGraph):
         if nx.is_tree(obj):
             # NOTE: the root must be the first node added. otherwise it won't work
             return json_graph.tree_data(obj, obj.nodes_iter().next())
         else:
             return json_graph.node_link_data(obj)
     elif isinstance(obj, pd.DataFrame):
         return obj.to_dict(orient='records')
     return json.JSONEncoder.default(self, obj)

 def default(self, obj):
     if isinstance(obj, np.ndarray):
         return obj.tolist()
     elif isinstance(obj, np.generic):
         return obj.item()
     elif isinstance(obj, nx.Graph) or isinstance(obj, nx.DiGraph):
         if nx.is_tree(obj) and 'root' in obj.graph:
             # NOTE: there must be a root graph attribute, or the root must be the first node added.
             # otherwise it won't work
             return json_graph.tree_data(obj, obj.graph['root'])
         else:
             return json_graph.node_link_data(obj)
     elif isinstance(obj, pd.DataFrame):
         return obj.to_dict(orient='records')
     return json.JSONEncoder.default(self, obj)

 def test_wikipedia_example(self):
     # Example from https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree
     G = nx.Graph()
     G.add_weighted_edges_from((
         (0, 1, 1), (0, 2, 7), (1, 2, 1),
         (1, 3, 3), (1, 4, 2), (2, 4, 4),
         (3, 4, 1), (3, 5, 6), (4, 5, 2),
     ))
     for flow_func in flow_funcs:
         T = nx.gomory_hu_tree(G, capacity='weight', flow_func=flow_func)
         assert_true(nx.is_tree(T))
         for u, v in combinations(G, 2):
             cut_value, edge = self.minimum_edge_weight(T, u, v)
             assert_equal(nx.minimum_cut_value(G, u, v, capacity='weight'),
                          cut_value)

def check_spanning_tree(tree):
    '''Check that a graph is a spanning tree.
    Parameters
    ----------
    tree : networkx graph
    '''
    nodes = np.array(tree.nodes())
    n_nodes = len(nodes)
    edges = np.array(tree.edges())
    n_edges = len(edges)
    # check number of edges
    if not n_nodes - 1 == n_edges:
        raise ValueError('Incorrect number of edes in graph.')
    # check that graph is a tree
    if not nx.is_tree(tree):
        raise TypeError('Must input a tree.')    

def to_dict_tree(digraph, root):
    import networkx as nx
    """
    Convert a networkx.DiGraph to a tree.
    (king, (governor,(editor,)), (state,(collapse,),(head,)(lord,)))
    """
    assert nx.is_tree(digraph)
    str2node = {root: []}
    for parent, child in nx.traversal.dfs_edges(digraph, root):
        score = digraph.edge[parent][child]['score']
        childnode = {child: [], 'score': score}
        children = str2node[parent]
        children.append(childnode)
        str2node[child] = childnode[child]

    return {root: str2node[root]}

def modif_free_mwe_labels(sent,most_common_label_filler):
    for h,d in sent.edges():
        if sent[h][d]["deprel"] in freemwes:
            head_over_mwe = sent.head_of(h)
            overall_mwe_function = sent[head_over_mwe][h]['deprel']
            if type(overall_mwe_function) == str:
                if "_" in overall_mwe_function or overall_mwe_function.startswith("mwe"):
                    pass
                else:
                    sent[h][d]["deprel"] = sent[h][d]["deprel"]+"_rmwe_"+most_common_label_filler[overall_mwe_function]
            else:
                #pass
                print("MUCHO WRONG",h,d,overall_mwe_function)
                print(sent, sent.edges(),nx.is_tree(sent))

    return sent

def optimal_placement(tree, budget):
    """
    Place `budget` sensors on a tree in an optimal way.

    Parameters
    ----------
    tree : networkx.Graph
        A tree (undirected) on which to place the sensors.
    budget : int
        The sensor budget, i.e. the number of nodes that can be chosen as
        sensors

    Returns
    -------
    (perr, obs) : tuple
        `perr` is the error probability, and `obs` a tuple containing the
        sensors.
    """ 
    
    #one single sensor is useless
    assert budget >= 2

    assert nx.is_tree(tree)

    leaves = utilities.find_leaves(tree)
    if budget >= len(leaves):
        return (0, tuple(leaves))

    #define a non-leaf root arbitrarily
    root = random.choice(filter(lambda x: x not in leaves, tree.nodes()))
    directed = nx.dfs_tree(tree, source=root) #dir DFS tree from source

    #compute the subtree sizes
    for x in directed:
        directed.node[x]['size'] = utilities.size_subtree(directed, x)
    utilities.size_subtree.cache_clear()
    
    #add the budget and the root to the tree as an attribute
    directed.graph['root'] = root
    directed.graph['budget'] = budget
    
    #place the sensors using the DP algorithm
    err, obs = _opt(directed, root, budget)
    _optc.cache_clear()
    _opt.cache_clear()
    
    return (float(err) / len(tree), obs)

def is_forest(G):
    """Return True if the input graph is a forest

    Parameters
    ----------
    G : NetworkX Graph
       An undirected graph.

    Returns
    -------
    True if the input graph is a forest

    Notes
    -----
    For undirected graphs only.
    """
    for graph in nx.connected_component_subgraphs(G):
        if not nx.is_tree(graph):
            return False
    return True

def find_root(G):
    """Returns root node ID for the Graph."""
    if not nx.is_tree(G):
        return None
    return nx.topological_sort(G)[0]