def find_football_communities():
    """ Finds the communities produced for the football network, uses compare
    methods to graph
    """
    fgraph = CD.football_graph()
    known = CD.football_known_c()
    temp7 = known[7]
    temp8 = known[8]
    temp9 = known[9]
    known[7] = temp8
    known[8] = temp9
    known[9] = temp7

    center_g = nx.Graph()
    center_g.add_nodes_from(range(12))
    centers = nx.circular_layout(center_g, scale = 10)
            
    pos = {}
    subgraphs = [nx.subgraph(fgraph, c) for c in known]
    count = -1
    for g in subgraphs:
        count += 1
        (off_x, off_y) = centers[count]
        pos_local = nx.circular_layout(g, scale=2.)
        for n, place in pos_local.iteritems():
            pos[n] = place + np.array([off_x, off_y])
    
    compare_methods(fgraph,
                    'football_',
                    param=[1., 1., 5./115., 4, 0, .7, 20],
                    known=known,
                    pos=pos,
                    color_map={76:1, 11:2, 7:3, 102:4, 104:5, 47:6, 98:7,
                               96:8, 23:9, 94:10, 27:0},
                    data_path="FootballGames/football_metis")

    def test_scale_and_center_arg(self):
        G = nx.complete_graph(9)
        G.add_node(9)
        vpos = nx.random_layout(G, scale=2, center=(4,5))
        self.check_scale_and_center(vpos, scale=2, center=(4,5))
        vpos = nx.spring_layout(G, scale=2, center=(4,5))
        self.check_scale_and_center(vpos, scale=2, center=(4,5))
        vpos = nx.spectral_layout(G, scale=2, center=(4,5))
        self.check_scale_and_center(vpos, scale=2, center=(4,5))
        # circular can have twice as big length
        vpos = nx.circular_layout(G, scale=2, center=(4,5))
        self.check_scale_and_center(vpos, scale=2*2, center=(4,5))
        vpos = nx.shell_layout(G, scale=2, center=(4,5))
        self.check_scale_and_center(vpos, scale=2*2, center=(4,5))

        # check default center and scale
        vpos = nx.random_layout(G)
        self.check_scale_and_center(vpos, scale=1, center=(0.5,0.5))
        vpos = nx.spring_layout(G)
        self.check_scale_and_center(vpos, scale=1, center=(0.5,0.5))
        vpos = nx.spectral_layout(G)
        self.check_scale_and_center(vpos, scale=1, center=(0.5,0.5))
        vpos = nx.circular_layout(G)
        self.check_scale_and_center(vpos, scale=2, center=(0,0))
        vpos = nx.shell_layout(G)
        self.check_scale_and_center(vpos, scale=2, center=(0,0))

    def plot_graphs(self):
        # draw lables
        # choose same layout as in drawing the rest of the graph
        pos_G=nx.circular_layout(self.g1)   # positions for all nodes for G (in this case circular)
        pos_H=nx.circular_layout(self.g2)   # positions for all nodes for H (in this case circular)
        labels_G = {}                 # create a dict with labels
        for item in self.g1.nodes():
            labels_G[item] = item

        labels_H = {}                 # create a dict with labels
        for item in self.g2.nodes():
            labels_H[item] = item

        # color-mapping via numpy
        # list of cmaps can be found here: http://matplotlib.org/examples/color/colormaps_reference.html
        # I chose this cmap because there are no dark colors in it so the labels stay readable regardless
        # the color of the label.
        plt.subplots_adjust(left=0,right=1,bottom=0,top=0.95,wspace=0.01,hspace=0.01)
        plt.subplot(121)
        plt.title("Graph G")
        nx.draw_circular(self.g1, cmap=plt.get_cmap('Set1'), node_color=self.nc1)
        nx.draw_networkx_labels(self.g1, pos_G, labels_G)

        plt.subplot(122)
        plt.title("Graph H")
        nx.draw_circular(self.g2, cmap=plt.get_cmap('Set1'), node_color=self.nc2)
        nx.draw_networkx_labels(self.g2, pos_H, labels_H)

        plt.show()

    def displayRGA(self, pairingoption=1, nodepositions=None):
        """This method will display the RGA pairings.

        It has 2 options of pairings:
            1) pairingoption = 1 (the default) This displays the standard RGA
            pairings where the decision to pair is positive if the relative gain
            array has an element value of more than or equal to 0.5.
            2) pairingoption = 2 This displays the RGA pairs where each input is
            forced to have a paired output. This is selected by using the maximum
            value in each column as a pair.

        It has an optional parameter to set node positions. If left out
        the default node positions will be circular. """

        if pairingoption == 1:
            pairingpattern = self.bristol.pairedvariablesHalf
            message = "Standard RGA Pairings"
            self.G1 = nx.DiGraph()
            self.G1 = self.G.copy()
            print(pairingpattern)
            self.G1.add_edges_from(self.G1.edges(), edgecolour='k')
            self.G1.add_edges_from(pairingpattern, edgecolour='r')
            #correct up to here
            pairingtuplelist = [(row[0], row[1]) for row in pairingpattern] #what a mission to find this error
            edgecolorlist = ["r" if edge in pairingtuplelist else "k" for edge in self.G1.edges()]


            if nodepositions == None:
                nodepositions = nx.circular_layout(self.G1)

            plt.figure(message)
            nx.draw_networkx(self.G1, pos=nodepositions)
            nx.draw_networkx_edges(self.G1, pos=nodepositions, width=2.5, edge_color=edgecolorlist, style='solid', alpha=0.5)
            nx.draw_networkx_nodes(self.G1, pos=nodepositions, node_color='y', node_size=450)
            plt.axis('off')
        else:
            pairingpattern = self.bristol.pairedvariablesMax
            message = "Maximum RGA Pairings"
            self.G2 = nx.DiGraph()
            self.G2 = self.G.copy()
            print(pairingpattern)
            self.G2.add_edges_from(self.G2.edges(), edgecolour='k')
            self.G2.add_edges_from(pairingpattern, edgecolour='r')
        #correct up to here
            pairingtuplelist = [(row[0], row[1]) for row in pairingpattern] #what a mission to find this error
            edgecolorlist = ["r" if edge in pairingtuplelist else "k" for edge in self.G2.edges()]


            if nodepositions == None:
                nodepositions = nx.circular_layout(self.G2)

            plt.figure(message)
            nx.draw_networkx(self.G2, pos=nodepositions)
            nx.draw_networkx_edges(self.G2, pos=nodepositions, width=2.5, edge_color=edgecolorlist, style='solid', alpha=0.5)
            nx.draw_networkx_nodes(self.G2, pos=nodepositions, node_color='y', node_size=450)
            plt.axis('off')

 def test_fixed_node_fruchterman_reingold(self):
     # Dense version (numpy based)
     pos = nx.circular_layout(self.Gi)
     npos = nx.fruchterman_reingold_layout(self.Gi, pos=pos, fixed=[(0, 0)])
     assert_equal(tuple(pos[(0, 0)]), tuple(npos[(0, 0)]))
     # Sparse version (scipy based)
     pos = nx.circular_layout(self.bigG)
     npos = nx.fruchterman_reingold_layout(self.bigG, pos=pos, fixed=[(0, 0)])
     for axis in range(2):
         assert_almost_equal(pos[(0,0)][axis], npos[(0,0)][axis])

 def test_empty_graph(self):
     G=nx.Graph()
     vpos = nx.random_layout(G)
     vpos = nx.circular_layout(G)
     vpos = nx.spring_layout(G)
     vpos = nx.fruchterman_reingold_layout(G)
     vpos = nx.shell_layout(G)
     vpos = nx.spectral_layout(G)
     # center arg
     vpos = nx.random_layout(G, scale=2, center=(4,5))
     vpos = nx.circular_layout(G, scale=2, center=(4,5))
     vpos = nx.spring_layout(G, scale=2, center=(4,5))
     vpos = nx.shell_layout(G, scale=2, center=(4,5))
     vpos = nx.spectral_layout(G, scale=2, center=(4,5))

 def test_single_node(self):
     G = nx.Graph()
     G.add_node(0)
     vpos = nx.random_layout(G)
     vpos = nx.circular_layout(G)
     vpos = nx.spring_layout(G)
     vpos = nx.fruchterman_reingold_layout(G)
     vpos = nx.shell_layout(G)
     vpos = nx.spectral_layout(G)
     # center arg
     vpos = nx.random_layout(G, scale=2, center=(4,5))
     vpos = nx.circular_layout(G, scale=2, center=(4,5))
     vpos = nx.spring_layout(G, scale=2, center=(4,5))
     vpos = nx.shell_layout(G, scale=2, center=(4,5))
     vpos = nx.spectral_layout(G, scale=2, center=(4,5))

def printClusters(msp_list_deleted, msp_list_remain, msp_list, name):
    G = nx.Graph()
    deleted = nx.Graph()
    remain = nx.Graph()

    for l in range(0, len(msp_list)):
        G.add_edge(msp_list[l][1], msp_list[l][2], weight="{0:.2f}".format(msp_list[l][0]))
    pos = nx.circular_layout(G)

    for l in range(0, len(msp_list_deleted)):
        deleted.add_edge(msp_list_deleted[l][1], msp_list_deleted[l][2],
                         weight="{0:.2f}".format(msp_list_deleted[l][0]))

    for l in range(0, len(msp_list_remain)):
        remain.add_edge(msp_list_remain[l][1], msp_list_remain[l][2], weight="{0:.2f}".format(msp_list_remain[l][0]))

    nx.draw(G, pos)
    edge_labels = dict([((u, v,), d['weight']) for u, v, d in G.edges(data=True)])
    edge_labels_deleted = dict([((u, v,), d['weight']) for u, v, d in deleted.edges(data=True)])
    edge_labels_remain = dict([((u, v,), d['weight']) for u, v, d in remain.edges(data=True)])

    nx.draw_networkx_edges(G, pos, edge_labels=edge_labels_deleted)
    nx.draw_networkx_edge_labels(remain, pos, edge_labels=edge_labels)
    nx.draw_networkx_edges(deleted, pos, edge_labels=edge_labels_remain, width=3, edge_color='w', style='dashed')
    plt.savefig(name + ".png")

    def generate_minimum(self):
        
        #ele gera a topologia (com pesos) e ja seta os ligados/desligados iniciais.
        for food in self.food_list:
            self.add_node(food,  {'on': True,'Next': True, 'Threshold': 0})   #CORRIGIR ISSO PRA COMIDA QUE TA ERRADO!!!!!
            self.colors.append(palette[1])

        for gene in self.genes_list:
            r = (True == rndm.randint(0,1))
            self.add_node(gene,  {'on': r, 'Next': r, 'Threshold': 0})  #QUANTO COLOCAR PARA O THRESHOLD?
            self.add_edge(gene, gene, {'w': 1.0})    
            self.colors.append(palette[2 if r else 0])
            if r:
                self.switch_dict.update({gene: True})

	for interm in self.intermediate_list:
	    r = (True == rndm.randint(0,1))
            self.add_node(interm,  {'on': r ,'Next': r , 'Threshold': interm % 2})  #quanto deve ser o threshold inicial??
            self.add_edge(interm, interm, {'w': 1.0})
            self.colors.append(palette[3 if r else 0])


        pos2 = nx.circular_layout(self)
        self.pos = {}
        for i in self.control_list:
            self.pos[i] = pos2[self.nodes()[self.control_list.index(i)]]
        self.draw_BN(self.pos, self.control_list)

def circular_iter(G, start_pos=None):
    if start_pos == None: start_pos = nx.circular_layout(G)

    best_pos = start_pos.copy()

    best_crossings = len(nx_detect_crosses(G,best_pos))
    if best_crossings == 0:
        return best_pos

    for x in range(1,len(G.nodes())):
        print "\nIteration number:",x

        new_pos = all_pair_swaps(G, best_pos)
        new_crossings = len(nx_detect_crosses(G,new_pos))

        if new_crossings < best_crossings:
            best_pos = new_pos.copy()
            best_crossings = new_crossings
            if best_crossings == 0:
                print "Success!  Zero crossings."
                break

        else:
            print "Dead end!  Progress stuck at {} crossings.".format(best_crossings)
            break

    return best_pos

def draw_graph(graph, graph_layout='shell',
               node_size=1600, node_color='blue', node_alpha=0.3, node_text_size=12,
               edge_color='blue', edge_alpha=0.3, edge_tickness=1, edge_text_pos=0.3,
               text_font='sans-serif', save=True, filename=None):

    edge_labels=dict([((u,v,),d['weight']) for u,v,d in graph.edges(data=True)])
    # these are different layouts for the network you may try
    # shell seems to work best
    if graph_layout == 'spring':
        graph_pos=nx.spring_layout(graph)
    elif graph_layout == 'spectral':
        graph_pos=nx.spectral_layout(graph)
    elif graph_layout == 'random':
        graph_pos=nx.random_layout(graph)
    elif graph_layout == 'circular':
        graph_pos=nx.circular_layout(graph)
    else:
        graph_pos=nx.shell_layout(graph)

    # draw graph
    nx.draw_networkx_nodes(graph, graph_pos, node_size=node_size, alpha=node_alpha, node_color=node_color)
    nx.draw_networkx_edges(graph, graph_pos, width=edge_tickness, alpha=edge_alpha, edge_color=edge_color)
    nx.draw_networkx_labels(graph, graph_pos, font_size=node_text_size, font_family=text_font)
    nx.draw_networkx_edge_labels(graph, graph_pos, edge_labels=edge_labels, label_pos=edge_text_pos)

    # show graph
    if save == True:
        plt.savefig(filename, dpi=1000)
    plt.show()

def topology(g):
    if g.size() > 30:
        print "Not drawing topology as size > 30"
    else:
        networkx.draw(g, pos=networkx.circular_layout(g))
        pylab.savefig("topology.png")
        pylab.clf()

 def draw(self):
     """Draws the current game state."""
     unavailables = []
     availables = []
     reds = []
     blues = []
     for i in self.graph.nodes_iter():
         if self.graph.node[i]["label"] == labels.AVAILABLE:
             availables.append(i)
         elif self.graph.node[i]["label"] == labels.RED:
             reds.append(i)
         elif self.graph.node[i]["label"] == labels.BLUE:
             blues.append(i)
         else:
             unavailables.append(i)
     node_labels = {}
     for i in self.graph.nodes_iter():
         node_labels[i] = i
     pos = nx.circular_layout(self.graph)
     nx.draw_networkx_edges(self.graph, pos, edgelist=self.graph.edges(), width=4)
     nx.draw_networkx_nodes(self.graph, pos, nodelist=availables, node_color="w", node_size=500, alpha=1)
     nx.draw_networkx_nodes(self.graph, pos, nodelist=reds, node_color="r", node_size=500, alpha=1)
     nx.draw_networkx_nodes(self.graph, pos, nodelist=blues, node_color="b", node_size=500, alpha=1)
     nx.draw_networkx_nodes(self.graph, pos, nodelist=unavailables, node_color="black", node_size=500, alpha=0.6)
     nx.draw_networkx_node_labels(self.graph, pos, node_labels, font_size=16)

def visualize_weighted_graph(file_name):
    """@todo: Given a file with file that is a graph with first
    column a vertex and preceding columns
    its neighbors and there distances, neighbors are separated by commas

    :a_file: name of the file
    :creates: graph visualization of the Graph and saves it as a file_name.png

    """
    G = nx.Graph()
    with open(file_name) as f:
        for line in f:
            if line:
                line = line.split()
                v1, neighbors = line[0],line[1:]
                for neighbor in neighbors:
                    v2, weight = neighbor.split(',')
                    G.add_edge(v1, v2, weight=int(weight))

    pos=nx.circular_layout(G)
    pylab.figure(2)
    nx.draw(G,pos)
    edge_labels=dict([((u,v,),d['weight'])
                for u,v,d in G.edges(data=True)])
    nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
    pylab.savefig(file_name.replace('txt','png'))

	def get(self):
		G = nx.Graph()
		self.add_header("Access-Control-Allow-Origin", "*")
		n_name = self.get_argument('cnode')
		lt = list(one_x_extend(n_name))
		rtid = {"nodes":[],"links":[]}
		for item in cast_path_2_node(lt):
			tmp = {"name":str(item)}
			rtid["nodes"].append(tmp)
		cdict = {}
		for item in enumerate(cast_path_2_node(lt)):
			cdict[str(item[1])] = item[0]
		for item in cast_path_2_link(lt):
			G.add_edge(item[0],item[1])
			tmp = {"source":item[0],"target":item[1]}
			rtid["links"].append(tmp)
		co = choice('01')
		#pos = nx.spring_layout(G, scale=1.0)
		if co == '0':
			pos = nx.circular_layout(G)
		elif co == '1':
			pos = nx.spring_layout(G)
		else:
			pos = nx.shell_layout(G)
		text = ''.join(cast_dict_2_gexf(rtid,pos))
		print text
		self.write(text)

def transmission(path,g,src,dest):
 global disp_count
 global bar_colors
 global edge_colors
 global node_colors
 k=0
 j=0
 list_of_edges = g.edges() 
 for node in path :
  k=path.index(node)
  disp_count = disp_count + 1
  if k != (len(path)-1):
   k=path[k+1]
   j=list_of_edges.index((node,k))
   initialize_edge_colors(j)
   #ec[disp_count].remove(-3000) 
   pylab.subplot(121) 
   nx.draw_networkx(g,pos = nx.circular_layout(g),node_color= node_colors,edge_color = edge_colors)
   pylab.annotate("Source",node_positions[src])
   pylab.annotate("Destination",node_positions[dest])
   pylab.title("Transmission")

   he=initializeEnergies(disp_count)
   print he
   pylab.subplot(122)
   pylab.bar(left=[1,2,3,4,5],height=[300,300,300,300,300],width=0.5,color = ['w','w','w','w','w'],linewidth=0) 
   pylab.bar(left=[1,2,3,4,5],height=initializeEnergies(disp_count),width=0.5,color = 'b') 
   pylab.title("Node energies")
   #pylab.legend(["already passed throgh","passing" , "yet to pass"])
   pylab.xlabel('Node number')
   pylab.ylabel('Energy') 
   pylab.suptitle('Leach Protocol', fontsize=12)
   pylab.pause(2)
  else :
     return

    def generate_minimum(self):
        
        #ele gera a topologia (com pesos) e ja seta os ligados/desligados iniciais.
        for gene in range(self.number_genes):
            r = (True == rndm.randint(0,1))
            self.add_node(self.genes_list[gene],  {'on': r or (gene in range(self.number_food_total)),'Next': r or (gene in range(self.number_food_total))})
            if gene not in range(self.number_food_total):
                self.add_edge(self.genes_list[gene], self.genes_list[gene], {'w': 1.0})
            self.colors.append(palette[(r or (gene in range(self.number_food_total))) + 0])
            if r and (gene not in range(self.number_food_total)): #or (gene1 in range(self.number_food_total)):
                self.switch_dict.update({self.genes_list[gene]:True})
       
	for interm in range(self.intermediate):
	    r = (True == rndm.randint(0,1))
            self.add_node((interm,),  {'on': r ,'Next': r })
            self.colors.append(palette[r + 0])
##            if r:
##                self.switch_dict.update({(interm,):True})

        pos2 = nx.circular_layout(self)
        self.pos = {}
        for i in self.genes_list + [(c,) for c in range(self.intermediate)]:
            self.pos[i] = pos2[self.nodes()[(self.genes_list + [(c,) for c in range(self.intermediate)]).index(i)]]

        self.draw_BN(self.pos, self.genes_list)

    def displayEigenRankGGb(self, nodepos=None):
        """This method constructs a network graph showing connections and rankings
        in terms of node size going BACKWARD and using unity gains between all node
        i.e. the google rank.

        It has an optional parameter nodepos which sets the positions of the nodes,
        if left out the node layout defaults to circular. """


        self.GGB = nx.DiGraph()
        for i in range(self.gbgain.n):
            for j in range(self.gbgain.n):
                if (self.gbgain.gMatrix[i, j] != 0):
                    self.GGB.add_edge(self.gbgain.gVariables[j], self.gbgain.gVariables[i])


        plt.figure("Node Rankings: Google Gain Backward: Scaled")
        rearrange = self.GGB.nodes()

        for node in self.GGB.nodes():
            self.GGB.add_node(node, importance=self.gbgain.rankDict[node])

        nodelabels = dict((n, [n, round(self.gbgain.rankDict[n], 3)]) for n in self.GGB.nodes())
        sizeArray = [self.gbgain.rankDict[var] * 10000 for var in rearrange]

        if nodepos == None:
            nodepos = nx.circular_layout(self.GGB)

        nx.draw_networkx(self.GGB, pos=nodepos , labels=nodelabels, node_size=sizeArray, node_color='y')
        nx.draw_networkx_edges(self.GGB, pos=nodepos)
        plt.axis("off")

def difference(graph2, graph1):

    D1 = nx.difference(graph2, graph1)
    pos = nx.circular_layout(D1)
    D2 = nx.difference(graph1, graph2)  # edges in graph1 but not in graph2
    pos = nx.circular_layout(D2)

    nx.draw_networkx_nodes(D1,pos, node_color="g", node_size=1000)
    nx.draw_networkx_edges(D1,pos, edge_color='g',width=10) 
    nx.draw_networkx_nodes(D2,pos, node_color="r", node_size=1000)
    nx.draw_networkx_edges(D2,pos, edge_color='r',width=10) 

    plt.show()
#   plt.savefig("M.PDF",facecolor='pink')  #save graph

    return difference

    def displayEigenRankNormalBackward(self, nodepos=None):
        """This method constructs a network graph showing connections and rankings
        in terms of node size going BACKWARD and using the local gains. (it is not
        scaled)

        It has an optional parameter nodepos which sets the positions of the nodes,
        if left out the node layout defaults to circular. """


        self.NBG = nx.DiGraph()
        for i in range(self.normalbackwardgain.n):
            for j in range(self.normalbackwardgain.n):
                if (self.normalbackwardgain.gMatrix[i, j] != 0):
                    self.NBG.add_edge(self.normalbackwardgain.gVariables[j], self.normalbackwardgain.gVariables[i]) #draws the connectivity graph to visualise rankArray


        plt.figure("Node Rankings: Local Gain Backward: Normal")
        rearrange = self.NBG.nodes()

        for node in self.NBG.nodes():
            self.NBG.add_node(node, importance=self.normalbackwardgain.rankDict[node])

        nodelabels = dict((n, [n, round(self.normalbackwardgain.rankDict[n], 3)]) for n in self.NBG.nodes())
        sizeArray = [self.normalbackwardgain.rankDict[var] * 10000 for var in rearrange]

        if nodepos == None:
            nodepos = nx.circular_layout(self.NBG)

        nx.draw_networkx(self.NBG, pos=nodepos , labels=nodelabels, node_size=sizeArray, node_color='y')
        nx.draw_networkx_edges(self.NBG, pos=nodepos)
        plt.axis("off")