def AlmostTree(n,m):
	t=m-n+1
	vertices_in_triangles=3*t
	edges_in_triangles=3*t
	
	if vertices_in_triangles<=n:
		G=nx.star_graph(n-2*t-1)
		vertex_index=n-2*t
		for triangle_index in range(t):
			G.add_edge((triangle_index+1)%(n-2*t),vertex_index)
			G.add_edge((triangle_index+1)%(n-2*t),vertex_index+1)
			G.add_edge(vertex_index,vertex_index+1)
			vertex_index=vertex_index+2
		return G
		
	if vertices_in_triangles>n:
		g=3*t-n+1   #Number of merged triangles
		f=t-g		#Number of free triangles
		G=nx.star_graph(f+2*g)
		star_index=0
		for merged_index in range(g):
			star_index=star_index+2
			G.add_edge(star_index,star_index-1)
		
		vertex_index=f+2*g+1
		for triangle_index in range(f):
			star_index=star_index+1
			G.add_edge(star_index,vertex_index)
			G.add_edge(star_index,vertex_index+1)
			G.add_edge(vertex_index,vertex_index+1)
			vertex_index=vertex_index+2
		return G

def test_star():
    G = nx.star_graph(3)
    _check_augmentations(G)

    G = nx.star_graph(5)
    _check_augmentations(G)

    G = nx.star_graph(10)
    _check_augmentations(G)

def instance7_2000():
    """
    Returns a 3-element tuple (G,T,leaves) where G is the graph
    T is the optimal solution and leaves is the number of leaves
    in the optimal solution.
    
    The graph is constructed by creating 4 stars with 90 nodes and
    adding 10 random nodes.
    """
    
    #create a star of 4 stars
    starList = []
    
    starList.append(nx.star_graph(22))
    starList.append(nx.star_graph(21))
    starList.append(nx.star_graph(21))
    starList.append(nx.star_graph(21))
    
    T = nx.Graph()
    for star in starList:
        T = nx.disjoint_union(T,star)
        
    T.add_node(89)
    T.add_edges_from([(89,0),(89,23),(89,67),(89,45)])
    
    #add 10 more nodes with random edges
    T.add_nodes_from(range(90,101))
    for i in range(90,101):
        x = int(random()*5371)%90
        T.add_edge(i,x)
        
    #count the number of leaves
    leaves = list(T.degree(T.nodes()).values()).count(1)
    
    #randomize the label of nodes
    for n in T.nodes():
        new = n + int(random()*2000)
        while(new in T.nodes()):
            new = n + int(random()*2000)
        T = nx.relabel_nodes(T,{n:new})
        
    G = nx.Graph()
    G.add_nodes_from(T.nodes())
    G.add_edges_from(T.edges())

    #code for 2000 edges
    #add random edges
    while(G.number_of_edges() < 2000):
        x = int(random()*15897)%100
        y = int(random()*17691)%100
        
        G.add_edge(G.nodes()[x],G.nodes()[y])
    T = one_edge_swap(G)

    return (G,T)

 def test_ego(self):
     G=nx.star_graph(3)
     H=nx.ego_graph(G,0)
     assert_true(nx.is_isomorphic(G,H))
     G.add_edge(1,11)
     G.add_edge(2,22)
     G.add_edge(3,33)
     H=nx.ego_graph(G,0)
     assert_true(nx.is_isomorphic(nx.star_graph(3),H))
     G=nx.path_graph(3)
     H=nx.ego_graph(G,0)
     assert_equal(H.edges(), [(0, 1)])

    def test_star_like(self):
        # star-like

        G=nx.star_graph(2)
        G.add_edge(1,2)
        assert_almost_equal(sb(G),0.843,places=3)

        G=nx.star_graph(3)
        G.add_edge(1,2)
        assert_almost_equal(sb(G),0.871,places=3)

        G=nx.star_graph(4)
        G.add_edge(1,2)
        assert_almost_equal(sb(G),0.890,places=3)

    def calc_star_uptime(self, n, link_fail):
        '''Calc star uptime.

        NOTE: n is the number of nodes.'''
        # Correct for NetworkX, which adds one to n.
        g = nx.star_graph(n - 1)
        # Node 0 is the center of the star.
        edges = g.number_of_edges()
        nodes = g.number_of_nodes()
        paths = nx.single_source_shortest_path(g, g.nodes()[1])
        used = flatten(paths)
        sssp_edges = used.number_of_edges()
        if sssp_edges != g.number_of_edges():
            raise Exception("edge not on sssp for star graph")

        # consider those times when a link failed:
        # first, consider failure on outside of graph
        exp_uptime_outer = link_fail * edges * ((float(edges - 1) / edges) * float(edges) / nodes + \
                                                (float(1) / edges) * float(1) / nodes)
        exp_uptime_outer += (1.0 - (link_fail * sssp_edges)) * 1.0

        # consider only the hub as a controller:
        exp_uptime_inner = link_fail * edges * ((float(edges) / edges) * float(edges) / nodes)
        exp_uptime_inner += (1.0 - (link_fail * edges)) * 1.0

        # merge:
        exp_uptime_weighted = float(edges * exp_uptime_outer + 1 * exp_uptime_inner) / nodes
        return exp_uptime_weighted

def test_star_graph():
    G = nx.star_graph(3)
    # all modes are the same
    answer = {0: 0, 1: 1, 2: 1, 3: 1}
    assert_equal(nx.bipartite_clustering(G, mode="dot"), answer)
    assert_equal(nx.bipartite_clustering(G, mode="min"), answer)
    assert_equal(nx.bipartite_clustering(G, mode="max"), answer)

    def test_min_vertex_cover(self):
        # create a simple star graph
        size = 50
        sg = nx.star_graph(size)
        cover = a.min_weighted_vertex_cover(sg)
        assert_equals(2, len(cover))
        for u, v in sg.edges():
            ok_((u in cover or v in cover), "Node node covered!")

        wg = nx.Graph()
        wg.add_node(0, weight=10)
        wg.add_node(1, weight=1)
        wg.add_node(2, weight=1)
        wg.add_node(3, weight=1)
        wg.add_node(4, weight=1)

        wg.add_edge(0, 1)
        wg.add_edge(0, 2)
        wg.add_edge(0, 3)
        wg.add_edge(0, 4)

        wg.add_edge(1,2)
        wg.add_edge(2,3)
        wg.add_edge(3,4)
        wg.add_edge(4,1)

        cover = a.min_weighted_vertex_cover(wg, weight="weight")
        csum = sum(wg.node[node]["weight"] for node in cover)
        assert_equals(4, csum)

        for u, v in wg.edges():
            ok_((u in cover or v in cover), "Node node covered!")

def get_graph(objects, properties):
    graph_type = properties['graph_type']
    n = len(objects)-1
    if 'num_nodes_to_attach' in properties.keys():
        k = properties['num_nodes_to_attach']
    else:
        k = 3
    r = properties['connection_probability']

    tries = 0
    while(True):
        if graph_type == 'random':
            x = nx.fast_gnp_random_graph(n,r)
        elif graph_type == 'erdos_renyi_graph':
            x = nx.erdos_renyi_graph(n,r)
        elif graph_type == 'watts_strogatz_graph':
            x = nx.watts_strogatz_graph(n, k, r)
        elif graph_type == 'newman_watts_strogatz_graph':
            x = nx.newman_watts_strogatz_graph(n, k, r)
        elif graph_type == 'barabasi_albert_graph':
            x = nx.barabasi_albert_graph(n, k, r)
        elif graph_type == 'powerlaw_cluster_graph':
            x = nx.powerlaw_cluster_graph(n, k, r)
        elif graph_type == 'cycle_graph':
            x = nx.cycle_graph(n)
        else: ##Star by default
            x = nx.star_graph(len(objects)-1)
        tries += 1
        cc_conn = nx.connected_components(x)
        if len(cc_conn) == 1 or tries > 5: 
            ##best effort to create a connected graph!
            break
    return x, cc_conn

def MinDistanceGraphFinder(number_of_vertices,number_of_edges):
		
	if number_of_edges<number_of_vertices-1:
		print 'Too few edges. The graph will be disconnected. Exiting...'
		return -1
	if number_of_edges>(number_of_vertices-1)*number_of_vertices/2.0:
		print 'Too many edges. Such a graph cannot exist. Exiting...'
		return -1
		
	if number_of_edges>(number_of_vertices-2)*(number_of_vertices-1)/2.0:
		OutputGraph=nx.gnm_random_graph(number_of_vertices,number_of_edges)
		return OutputGraph
	
	
	G=nx.star_graph(number_of_vertices-1)
	VertexList=G.nodes()
	remaining_edges=number_of_edges-number_of_vertices+1
	
	while remaining_edges>0:
		first_vertex=random.choice(VertexList)
		second_vertex=random.choice(VertexList)
		if first_vertex==second_vertex:continue
		if (first_vertex,second_vertex) in G.edges():continue
		if (second_vertex,first_vertex) in G.edges():continue
		
		G.add_edge(first_vertex,second_vertex)
		remaining_edges-=1
		
	OutputGraph=G.copy()
		
	return OutputGraph

 def test_unweighted_undirected(self):
     # create a simple star graph
     size = 50
     sg = nx.star_graph(size)
     cover = min_weighted_vertex_cover(sg)
     assert_equals(2, len(cover))
     ok_(is_cover(sg, cover))

def generate_connection_graph(graph_type, params, count):
    lower_type = graph_type.lower()
    if lower_type == 'complete':
        assert (len(params) == 0)
        return networkx.complete_graph(count)
    elif lower_type == 'complete-bipartite':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        n1 = int(round(count * float(params[0]) / float(params[1])))
        n2 = int(round(count * float(params[1]) / float(params[0])))
        n1 = 1 if n1 < 1 else n1
        n2 = 1 if n2 < 1 else n2
        return networkx.complete_bipartite_graph(n1, n2)
    elif lower_type == 'circular-ladder':
        assert (len(params) == 0)
        return networkx.circular_ladder_graph(count)
    elif lower_type == 'cycle':
        assert (len(params) == 0)
        return networkx.cycle_graph(count)
    elif lower_type == 'periodic-2grid':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        width = int(round(math.sqrt(count * float(params[0]) / float(params[1]))))
        height = int(round(math.sqrt(count * float(params[1]) / float(params[0]))))
        width = 1 if width < 1 else width
        height = 1 if height < 1 else height
        return networkx.grid_2d_graph(width, height, True)
    elif lower_type == 'nonperiodic-2grid':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        width = int(round(math.sqrt(count * float(params[0]) / float(params[1]))))
        height = int(round(math.sqrt(count * float(params[1]) / float(params[0]))))
        width = 1 if width < 1 else width
        height = 1 if height < 1 else height
        return networkx.grid_2d_graph(width, height, False)
    elif lower_type == 'hypercube':
        assert (len(params) == 0)
        return networkx.hypercube_graph(int(round(math.log(count, 2))))
    elif lower_type == 'star':
        assert (len(params) == 0)
        return networkx.star_graph(count - 1)
    elif lower_type == 'wheel':
        assert (len(params) == 0)
        return networkx.wheel_graph(count)
    elif lower_type == 'erdos-reyni':
        assert (len(params) == 1)
        return networkx.erdos_renyi_graph(count, float(params[0]))
    elif lower_type == 'watts-strogatz':
        assert (len(params) == 2)
        if int(params[0]) >= count / 2:
            k = int(count / 2 - 1)
        else:
            k = int(params[0])
        return networkx.connected_watts_strogatz_graph(count, k, int(params[1]))
    else:
        print "Unknown graph type {}".format(lower_type)
        assert False

def star_topology(n):
    """
    Return a star (a.k.a hub-and-spoke) topology of :math:`n+1` nodes

    The root (hub) node has id 0 while all leaf (spoke) nodes have id
    :math:`(1, n+1)`.

    Each node has the attribute type which can either be *root* (for node 0) or
    *leaf* for all other nodes

    Parameters
    ----------
    n : int
        The number of leaf nodes

    Returns
    -------
    topology : A Topology object
    """
    if not isinstance(n, int):
        raise TypeError('n argument must be of int type')
    if n < 1:
        raise ValueError('n argument must be a positive integer')
    G = Topology(nx.star_graph(n))
    G.name = "star_topology(%d)" % (n)
    G.graph['type'] = 'star'
    G.node[0]['type'] = 'root'
    for v in range(1, n + 1):
        G.node[v]['type'] = 'leaf'
    return G

def tuning(hemi='rh', roi='sts', cluster=4):
    df = pandas.read_csv('../analyses/tuning_curves_sts.csv')
    df = df[df.cluster==cluster]
    np.random.seed(0)

    for g, genre in enumerate(df.genre.unique()):
        sel = df[df.genre==genre]
        G = nx.star_graph(len(sel))
        pos = nx.spring_layout(G)
        colors = np.sign(sel.weight).astype(int).tolist()
        node_size = 2000*np.abs(sel.weight)
        node_size = [np.mean(node_size)] + node_size.tolist()
        cmap = sns.color_palette('Set2', 2)
        cond = [np.mean(sel.weight)] + sel.weight.tolist()
        colors = [cmap[0] if c<0 else cmap[1] for c in cond]

        labels = dict([(k+1,v) for k,v in enumerate(sel.style)])
        labels[0] = genre

        sns.plt.subplot(2,3,g+1)
        nx.draw(G, pos, node_color=colors, edge_color='gray',
                width=1, with_labels=True,
                node_size=node_size, labels=labels)

    sns.plt.savefig('../images/%s_%s_%s.svg' % (hemi, roi, cluster))
    sns.plt.show()

def colormap():
    G=nx.star_graph(20)
    pos=nx.spring_layout(G)
    colors=range(20)
    nx.draw(G,pos,node_color='#A0CBE2',edge_color=colors,width=4,edge_cmap=plt.cm.Blues,with_labels=False)
    #plt.savefig("edge_colormap.png") # save as png
    plt.show() # display

def test_star_graph():
    G = nx.star_graph(3)
    # all modes are the same
    answer = {0: 0, 1: 1, 2: 1, 3: 1}
    assert_equal(bipartite.clustering(G, mode='dot'), answer)
    assert_equal(bipartite.clustering(G, mode='min'), answer)
    assert_equal(bipartite.clustering(G, mode='max'), answer)

 def test_ego(self):
     G = nx.star_graph(3)
     H = nx.ego_graph(G, 0)
     assert_true(nx.is_isomorphic(G, H))
     G.add_edge(1, 11)
     G.add_edge(2, 22)
     G.add_edge(3, 33)
     H = nx.ego_graph(G, 0)
     assert_true(nx.is_isomorphic(nx.star_graph(3), H))
     G = nx.path_graph(3)
     H = nx.ego_graph(G, 0)
     assert_edges_equal(H.edges(), [(0, 1)])
     H = nx.ego_graph(G, 0, undirected=True)
     assert_edges_equal(H.edges(), [(0, 1)])
     H = nx.ego_graph(G, 0, center=False)
     assert_edges_equal(H.edges(), [])

    def test_non_edges(self):
        # All possible edges exist
        graph = nx.complete_graph(5)
        nedges = list(nx.non_edges(graph))
        assert_equal(len(nedges), 0)

        graph = nx.path_graph(4)
        expected = [(0, 2), (0, 3), (1, 3)]
        nedges = list(nx.non_edges(graph))
        for (u, v) in expected:
            assert_true((u, v) in nedges or (v, u) in nedges)

        graph = nx.star_graph(4)
        expected = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
        nedges = list(nx.non_edges(graph))
        for (u, v) in expected:
            assert_true((u, v) in nedges or (v, u) in nedges)

        # Directed graphs
        graph = nx.DiGraph()
        graph.add_edges_from([(0, 2), (2, 0), (2, 1)])
        expected = [(0, 1), (1, 0), (1, 2)]
        nedges = list(nx.non_edges(graph))
        for e in expected:
            assert_true(e in nedges)

def MinImpedanceGraphFinder(number_of_vertices,number_of_edges):
	
	if number_of_edges<number_of_vertices-1:
		print 'Too few edges. The graph will be disconnected. Exiting...'
		return -1
	if number_of_edges>(number_of_vertices-1)*number_of_vertices/2.0:
		print 'Too many edges. Such a graph cannot exist. Exiting...'
		return -1
	
	
	G=nx.star_graph(number_of_vertices-1)
	remaining_edges=number_of_edges-number_of_vertices+1
	
	for current_vertex in range(2,number_of_vertices):
		if remaining_edges<=0:break
		G.add_edge(1,current_vertex)
		remaining_edges-=1
		
	while remaining_edges>0:
		for first_vertex in range(2,number_of_vertices):
			if remaining_edges<=0:break
			for second_vertex in range(first_vertex+1,number_of_vertices):
				if remaining_edges<=0:break
				if second_vertex not in G.neighbors(first_vertex):
					G.add_edge(first_vertex,second_vertex)
					remaining_edges-=1
		
	return G

    def test_non_neighbors(self):
        graph = nx.complete_graph(100)
        pop = random.sample(list(graph), 1)
        nbors = list(nx.non_neighbors(graph, pop[0]))
        # should be all the other vertices in the graph
        assert_equal(len(nbors), 0)

        graph = nx.path_graph(100)
        node = random.sample(list(graph), 1)[0]
        nbors = list(nx.non_neighbors(graph, node))
        # should be all the other vertices in the graph
        if node != 0 and node != 99:
            assert_equal(len(nbors), 97)
        else:
            assert_equal(len(nbors), 98)

        # create a star graph with 99 outer nodes
        graph = nx.star_graph(99)
        nbors = list(nx.non_neighbors(graph, 0))
        assert_equal(len(nbors), 0)

        # disconnected graph
        graph = nx.Graph()
        graph.add_nodes_from(range(10))
        nbors = list(nx.non_neighbors(graph, 0))
        assert_equal(len(nbors), 9)