def test_already_branching(self):
        """Tests that a directed acyclic graph that is already a
        branching produces an isomorphic branching as output.

        """
        T1 = nx.balanced_tree(2, 2, create_using=nx.DiGraph())
        T2 = nx.balanced_tree(2, 2, create_using=nx.DiGraph())
        G = nx.disjoint_union(T1, T2)
        B = nx.dag_to_branching(G)
        assert_true(nx.is_isomorphic(G, B))

def gen_data():
    """
    generates test metrics and network, where the network is a 
    balanced graph of height 2 and branch factor 2
    """
    network = nx.balanced_tree(2, 2)

    metrics = DataFrame()

    metrics['Demand'] =     [100, 50, 25, 12, 6, 3]
    metrics['Population'] = [100, 50, 25, 12, 6, 3]
    #level 0 
    base_coord = np.array([125, 10])
    coord_dict = {0: np.array([125, 10])}
    coord_dict[1] = coord_dict[0] + [-.5, -.25]
    coord_dict[2] = coord_dict[0] + [+.5, -.25]
    coord_dict[3] = coord_dict[1] + [-.25, -.25]
    coord_dict[4] = coord_dict[1] + [+.25, -.25]
    coord_dict[5] = coord_dict[2] + [-.25, -.25]
    coord_dict[6] = coord_dict[2] + [+.25, -.25]
                                   
    # assign x, y
    metrics['X'] = [coord_dict[i][0] for i in range(1, 7)]
    metrics['Y'] = [coord_dict[i][1] for i in range(1, 7)]
    nx.set_node_attributes(network, 'coords', coord_dict)
    #nx.draw(network, nx.get_node_attributes(network, 'coords'))
    
    return metrics, network.to_directed()

    def test_get_geoff_digraph(self):
        truth = [{'body': {}, 'id': 0, 'method': 'POST', 'to': '/node'},
                 {'body': {}, 'id': 1, 'method': 'POST', 'to': '/node'},
                 {'body': {'debug': 'test'}, 'id': 2, 'method': 'POST',
                  'to': '/node'},
                 {'body': "ITEM", 'method': 'POST', 'to': '{0}/labels'},
                 {'body': "ITEM", 'method': 'POST', 'to': '{1}/labels'},
                 {'body': "ITEM", 'method': 'POST', 'to': '{2}/labels'},
                 {'body': {'data': {'debug': False}, 'to': '{1}',
                  'type': 'LINK_TO'},
                  'method': 'POST', 'to': '{0}/relationships'},
                 {'body': {'data': {}, 'to': '{2}', 'type': 'LINK_TO'},
                  'method': 'POST',
                  'to': '{0}/relationships'}]

        graph = nx.balanced_tree(2, 1, create_using=nx.DiGraph())
        graph.node[2]['debug'] = 'test'
        graph[0][1]['debug'] = False
        result = generate_data(graph, "LINK_TO", "ITEM", json.JSONEncoder())
        self.assertEqual(json.loads(result), truth)

        httpretty.register_uri(httpretty.GET,
                               "http://localhost:7474/db/data/",
                               body=BATCH_URL)

        httpretty.register_uri(httpretty.POST,
                               "http://localhost:7474/db/data/batch",
                               body='["Dummy"]')

        result = write_to_neo("http://localhost:7474/db/data/", graph,
                              "LINKS_TO", "ITEM")

        self.assertEqual(result, ["Dummy"])

def create_tree(r, h=None, num_nodes=None):
    #need to have either height or num_nodes
    assert xor(bool(h),bool(num_nodes))
    to_remove=0
    if num_nodes != None:
        if r==1:
            h=num_nodes
        else:
            h=ceil(log(num_nodes*(r-1)+1, r)-1)
            init_size=(r**(h+1)-1)/(r-1)
            to_remove=int(init_size-num_nodes)
        
    #branching factor of 1 does not seem to work for nx.balanced_tree
    result_graph = semGODiGraph(None, Aspects.BP)
    if r ==1:
        for u in range(0,h):
            v=u+1
            result_graph.add_edge(GN(nodetype=GN.TERM_TYPE,dbid=v),GN(nodetype=GN.TERM_TYPE,dbid=u))
    else:	
        internal_graph=nx.balanced_tree(r=r,h=h,create_using=nx.DiGraph()) #gnp_random_graph(10,0.5,directed=True)
        current=internal_graph.number_of_nodes()
        remove_nodes=range(current-to_remove,current)
        for r in remove_nodes:
            internal_graph.remove_node(r)
        if num_nodes != None:
            assert num_nodes == internal_graph.number_of_nodes()
        for u,v in internal_graph.edges_iter():
            result_graph.add_edge(GN(nodetype=GN.TERM_TYPE,dbid=u),GN(nodetype=GN.TERM_TYPE,dbid=v))
        nx.reverse(result_graph, copy=False) #make the edges point up not down
        root_list=[n for n,d in result_graph.out_degree().items() if d==0]
        result_graph.root=root_list[0]
    result_graph.semMakeGraph()
    return result_graph

def balanced_tree_N(r,N):
	h = math.ceil( np.log(r*N-N+1)/np.log(r) -1 )
	Nbis = int((r**(h+1)-1)/(r-1))
	G = nx.balanced_tree(r,h)
	for n in range(N,Nbis):
		G.remove_node(n)
	return G

    def generate_topology(self, topo_type, node_count, branches = None):
        if topo_type == TopologyType.LADDER:
            total_nodes = node_count/2
            graph = networkx.ladder_graph(total_nodes)

        elif topo_type == TopologyType.LINEAR:
            graph = networkx.path_graph(node_count)

        elif topo_type == TopologyType.MESH:
            graph = networkx.complete_graph(node_count)

        elif topo_type == TopologyType.TREE:
            h = math.log(node_count + 1)/math.log(2) - 1
            graph = networkx.balanced_tree(2, h)

        elif topo_type == TopologyType.STAR:
            graph = networkx.Graph()
            graph.add_node(0)

            nodesinbranch = (node_count - 1)/ BRANCHES
            c = 1

            for i in xrange(BRANCHES):
                prev = 0
                for n in xrange(1, nodesinbranch + 1):
                    graph.add_node(c)
                    graph.add_edge(prev, c)
                    prev = c
                    c += 1

        return graph

 def test_tree(self):
     for sz in range(1,5):
         G = nx.balanced_tree(2,sz,nx.DiGraph()).reverse()
         G = nx.relabel_nodes(G,dict(zip(G.nodes(),reversed(G.nodes()))),True)
         G.name = 'Complete binary tree of height {}'.format(sz)
         F = PebblingFormula(G)
         self.checkFormula(sys.stdin,F, ["cnfgen","-q","peb", "--tree", sz])

def gen_data():
    """
    generates test metrics and network, where the network is a 
    balanced graph of height 2 and branch factor 2
    """
    network = nx.balanced_tree(2, 2)

    metrics = DataFrame(network.node).T

    metrics['Demand'] =     [np.nan, 100, 50, 25, 12, 6, 3]
    metrics['Population'] = [np.nan, 100, 50, 25, 12, 6, 3]
    #level 0 
    metrics['coords'] = [np.array([125,10]) for x in  metrics.index]
    #level 2
    metrics['coords'].ix[1] = metrics['coords'].ix[0] + [-.5, -.25]
    metrics['coords'].ix[2] = metrics['coords'].ix[0] + [+.5, -.25]
    #level 3
    metrics['coords'].ix[3] = metrics['coords'].ix[1] + [-.25, -.25]
    metrics['coords'].ix[4] = metrics['coords'].ix[1] + [+.25, -.25]
    metrics['coords'].ix[5] = metrics['coords'].ix[2] + [-.25, -.25]
    metrics['coords'].ix[6] = metrics['coords'].ix[2] + [+.25, -.25]
    metrics['coords'] = metrics['coords'].apply(tuple)

    nx.set_node_attributes(network, 'coords', metrics.coords.to_dict())
    #nx.draw(network, nx.get_node_attributes(network, 'coords'))
    
    return metrics, network.to_directed()

    def setUp(self):

        G=nx.Graph();
        G.add_edge(0,1,weight=3)
        G.add_edge(0,2,weight=2)
        G.add_edge(0,3,weight=6)
        G.add_edge(0,4,weight=4)
        G.add_edge(1,3,weight=5)
        G.add_edge(1,5,weight=5)
        G.add_edge(2,4,weight=1)
        G.add_edge(3,4,weight=2)
        G.add_edge(3,5,weight=1)
        G.add_edge(4,5,weight=4)
        self.G=G
        self.exact_weighted={0: 4.0, 1: 0.0, 2: 8.0, 3: 6.0, 4: 8.0, 5: 0.0}

        self.K = nx.krackhardt_kite_graph()
        self.P3 = nx.path_graph(3)
        self.P4 = nx.path_graph(4)
        self.K5 = nx.complete_graph(5)

        self.C4=nx.cycle_graph(4)
        self.T=nx.balanced_tree(r=2, h=2)
        self.Gb = nx.Graph()
        self.Gb.add_edges_from([(0,1), (0,2), (1,3), (2,3), 
                                (2,4), (4,5), (3,5)])


        F = nx.florentine_families_graph()
        self.F = F

 def test_balanced_tree(self):
     """Edge betweenness centrality: balanced tree"""
     G = nx.balanced_tree(r=2, h=2)
     b = nx.edge_betweenness_centrality(G, weight="weight", normalized=False)
     b_answer = {(0, 1): 12, (0, 2): 12, (1, 3): 6, (1, 4): 6, (2, 5): 6, (2, 6): 6}
     for n in sorted(G.edges()):
         assert_almost_equal(b[n], b_answer[n])

def create_tree(r, h):
    G = nx.balanced_tree(r, h)

    return G


    
    #nx.draw_networkx(G, pos = nx.spring_layout(G))
    #nx.draw_spring(G)

    for i in range(7):
        G.node[i]['color'] = 'white'

    

    #######  Visualization with graphviz  ########

    #write_dot(G,'test.dot')

    # same layout using matplotlib with no labels
    #plt.title("draw_networkx")
    pos=graphviz_layout(G,prog='dot')
    nx.draw(G,pos,with_labels=True,arrows=False, node_color = 'lightgray')


    plt.show()
    return G

def main():
    simconfig.branching_factor = 4
    simconfig.depth_factor = 4
    stats = analysis.BalancedTreeAutomorphismStatistics(simconfig)

    g2 = nx.balanced_tree(simconfig.branching_factor, simconfig.depth_factor)
    r2 = stats.calculate_graph_symmetries(g2)
    log.info("results: %s", r2)

 def generate_graph(self):
     #nodes
     n = int(self.lineEdit_2.text())
     self.graph = nx.balanced_tree(2, n)
     self.graph = nx.bfs_tree(self.graph, 0)
     #self.pos = nx.circular_layout(self.graph)
     self.pos = nx.graphviz_layout(self.graph, prog='dot')
     self.draw_graph()

    def _getGraph(self, values):
        r = values['Branching']
        h = values['Height']

        G = nx.balanced_tree(r ,h, create_using=nx.DiGraph())
        nodes = layout.circularTree(h, r, 25)

        return G, nodes

    def test_already_arborescence(self):
        """Tests that a directed acyclic graph that is already an
        arborescence produces an isomorphic arborescence as output.

        """
        A = nx.balanced_tree(2, 2, create_using=nx.DiGraph())
        B = nx.dag_to_branching(A)
        assert_true(nx.is_isomorphic(A, B))

    def test_get_geoff_digraph(self):
        today = datetime.date(2012, 1, 1)

        graph = nx.balanced_tree(2, 1, create_using=nx.DiGraph())
        graph.node[2]["debug"] = 'test"'
        graph[0][1]["debug"] = today

        self.assertRaises(TypeError, get_geoff, (graph, "LINK_TO"))

def comparison():
    r"""
    CommandLine:
        python -m utool.experimental.dynamic_connectivity comparison --profile
        python -m utool.experimental.dynamic_connectivity comparison
    """
    n = 12
    a, b = 9, 20
    num = 3

    import utool
    for timer in utool.Timerit(num, 'old bst version (PY)'):
        g = nx.balanced_tree(2, n)
        self = TestETT.from_tree(g, version='bst', fast=False)
        with timer:
            self.delete_edge_bst_version(a, b, bstjoin=False)

    import utool
    for timer in utool.Timerit(num, 'new bst version (PY) (with join)'):
        g = nx.balanced_tree(2, n)
        self = TestETT.from_tree(g, version='bst', fast=False)
        with timer:
            self.delete_edge_bst_version(a, b, bstjoin=True)

    import utool
    for timer in utool.Timerit(num, 'old bst version (C)'):
        g = nx.balanced_tree(2, n)
        self = TestETT.from_tree(g, version='bst', fast=True)
        with timer:
            self.delete_edge_bst_version(a, b, bstjoin=False)

    import utool
    for timer in utool.Timerit(num, 'new bst version (C) (with join)'):
        g = nx.balanced_tree(2, n)
        self = TestETT.from_tree(g, version='bst', fast=True)
        with timer:
            self.delete_edge_bst_version(a, b, bstjoin=True)

    import utool
    for timer in utool.Timerit(num, 'list version'):
        g = nx.balanced_tree(2, n)
        self = TestETT.from_tree(g, version='list')
        with timer:
            self.delete_edge_list_version(a, b)
    pass

def test_graph2geoff_digraph_fail():
    today = datetime.date(2012, 1, 1)

    graph = nx.balanced_tree(2, 1, create_using=nx.DiGraph())
    graph.node[2]['debug'] = 'test"'
    graph[0][1]['debug'] = today

    with pytest.raises(TypeError) as excinfo:
        graph2geoff(graph, 'LINK_TO')

 def __init__(self, **kwargs):
     # super
     super(BalancedTree, self).__init__()
     r = kwargs.get('r', 2)
     h = kwargs.get('h', 2)
     # mn_nx's topology view of the network
     self.ref_g = nx.balanced_tree(r,h)
     # nx topology definition
     self.build_nx_topo(self.ref_g)

def test_graph2geoff_digraph():
    result = """(0)
(1)
(2 {"debug": "test\\""})
(0)-[:LINK_TO {"debug": false}]->(1)
(0)-[:LINK_TO]->(2)"""
    graph = nx.balanced_tree(2, 1, create_using=nx.DiGraph())
    graph.node[2]['debug'] = 'test"'
    graph[0][1]['debug'] = False
    assert graph2geoff(graph, 'LINK_TO') == result