def draw_graph(graph, showLabels = True):

    # extract nodes from graph
    nodes = set([n1 for n1, n2 in graph] + [n2 for n1, n2 in graph])

    # create network graph
    G=nx.Graph()

    # add nodes
    for node in nodes:
        G.add_node(node)

    # add edges
    for edge in graph:
        G.add_edge(edge[0], edge[1])

    # draw graph 1 in shell layout
    pos = nx.shell_layout(G)
    nx.draw(G, pos)
    plt.figure()

    # draw graph 2 with a random layout
    # might need to zoom in to see edges
    # labels are now on top of the nodes
    nx.draw_random(G)
    plt.figure()
    nx.draw_spring(G, node_size=100, with_labels=showLabels, font_size=16, edge_color="grey", width=0.5)

    # draw graph 3 the standard way and save
    plt.savefig("fig1.png")
    plt.show()

def draw_networkx_ex():
    G = nx.dodecahedral_graph()
    nx.draw(G)
    plt.show()
    nx.draw_networkx(G, pos=nx.spring_layout(G))
    limits = plt.axis('off')
    plt.show()
    nodes = nx.draw_networkx_nodes(G, pos=nx.spring_layout(G))
    plt.show()
    edges = nx.draw_networkx_edges(G, pos=nx.spring_layout(G))
    plt.show()
    labels = nx.draw_networkx_labels(G, pos=nx.spring_layout(G))
    plt.show()
    edge_labels = nx.draw_networkx_edge_labels(G, pos=nx.spring_layout(G))
    plt.show()
    print("Circular layout")
    nx.draw_circular(G)
    plt.show()
    print("Random layout")
    nx.draw_random(G)
    plt.show()
    print("Spectral layout")
    nx.draw_spectral(G)
    plt.show()
    print("Spring layout")
    nx.draw_spring(G)
    plt.show()
    print("Shell layout")
    nx.draw_shell(G)
    plt.show()
    print("Graphviz")

def get_communities(graph):
	betweenness = nx.edge_betweenness_centrality(graph)
	sorted_betweeness = [x[0] for x in sorted(betweenness.items(), key = lambda x : x[1], reverse = True)]
	best_partitions = []
	max_modularity = -1.0
	graph_copy = graph.copy()
	while sorted_betweeness:
		communities = [list(x) for x in nx.connected_components(graph_copy)]
		partitions = {}
		for i in range(len(communities)):
			for node in communities[i]:
				partitions[node] = i
		modularity = community.modularity(partitions, graph_copy)
		if modularity > max_modularity:
			best_partitions = communities
			max_modularity = modularity
		elif modularity <= max_modularity:
			break;
		graph_copy.remove_edge(*sorted_betweeness[0])
		del sorted_betweeness[0]
	for partition in best_partitions:
		print sorted(partition)
	val_map = {}
	for partition in best_partitions:
		value = random.random()
		while value in val_map.values():
			value = random.random()
		for node in partition:
			val_map[node] = value
	values = [val_map.get(node) for node in graph.nodes()]
	nx.draw_spring(graph, node_color = values, node_size = 500, with_labels = True)
	plt.savefig(sys.argv[2])

def lattice_plot(component_list, file_path):
    """
    Creates a lattice style plot of all graph components
    """
    graph_fig=plt.figure(figsize=(20,10))    # Create figure
    
    # Set the number of rows in the plot based on an odd or
    # even number of components  
    num_components=len(component_list)
    if num_components % 2 > 0:
        num_cols=(num_components/2)+1
    else:
        num_cols=num_components/2
    
    # Plot subgraphs, with centrality annotation
    plot_count=1
    for G in component_list:
        # Find actor in each component with highest degree
        in_cent=nx.degree(G)
        in_cent=[(b,a) for (a,b) in in_cent.items()]
        in_cent.sort()
        in_cent.reverse()
        high_in=in_cent[0][1]
        
        # Plot with annotation
        plt.subplot(2,num_cols,plot_count)
        nx.draw_spring(G, node_size=35, with_labels=False)
        plt.text( 0,-.1,"Highest degree: "+high_in, color="darkgreen")
        plot_count+=1
    
    plt.savefig(file_path)

def construct_de_bruijn_velvet(kmers, draw, outfile):
	#make list of k-1mers for quick edge construction
	k1mers = [x[:-1] for x in kmers.keys()]
	k1mers_array = np.array(k1mers)

	#find overlaps
	edge_list = []
	for kmer in kmers.keys():
		matches = np.where(k1mers_array==kmer[1:])
		for match in matches[0]:
			#print match
			edge_list.append((kmer, kmers.keys()[match]))

	#make graph
	G = nx.DiGraph()
	#add seq_kmers as nodes and overlaps as edges
	for kmer in kmers.items():
		G.add_node(kmer[0], num=kmer[1])
	G.add_edges_from(edge_list)

	# draw the graph if desired
	if draw == "True":
		nx.draw_spring(G)
		plt.show()

	#output adjacency list format of the graph if desired
	if outfile != "":
		nx.write_adjlist(G, outfile)

	return G

def get_topics_noun_phrases(num_news, draw=False, url='http://cnn.com'):

    texts = get_news(url, num_news)

    gb = NounPhraseGraphBuilder(text_processing.clean_punctuation_and_stopwords)
    gb.load_texts(texts)
    G = gb.create_graph()
    print "Graph built"

    partition = community.best_partition(G)
    words_by_part = get_words_by_partition(partition)

    print_topics_from_partitions(G, words_by_part, 10)

    mod = community.modularity(partition,G)
    print("modularity:", mod)

    #print_topics_from_partitions(G, words_by_part, 10)
    if draw:
        values = [partition.get(node) for node in G.nodes()]
        nx.draw_spring(G, cmap = plt.get_cmap('jet'), node_color = values, node_size=30, with_labels=False)
        plt.show()

    topics = get_topics_from_partitions(G, words_by_part, 10)

    return G, topics

def print_graph_nx(vertices, edges, name, draw_spring=False, print_dist=False):
  G=nx.DiGraph()
  labels = []

  for v in vertices:
    G.add_node(v)

  for v in vertices:
    for e in edges:
      if(len(e)) > 2:
        G.add_edge(e[0], e[1], weight=int(e[2]))
      else:
        G.add_edge(e[0], e[1])

  print("Nodes of graph: ")
  print(G.nodes())
  print("Edges of graph: ")
  print(G.edges())

  if not draw_spring:
    nx.draw(G, with_labels=True, node_color='y')
  else:
    nx.draw_spring(G, with_labels=True, node_color='y')
  #nx.draw_networkx_edge_labels(G,labels)
  plt.savefig("%s.png" % name) # save as png
  #plt.show()
  plt.clf()

 def plotGraph(self, path):
     if self.graph is None:
         raise Exception("The graph has not been generated")
     values = [self.colorScheme(n) for n in self.graph.nodes()]
     nx.draw_spring(self.graph, cmap="jet", node_color=values, node_size=100)
     plt.savefig(path)
     plt.close()

    def draw_graph(self, G, node_list=None, edge_colour='k', node_size=15, node_colour='r', graph_type='spring',
                   back_bone=None, side_chains=None, terminators=None):
        # determine nodelist
        if node_list is None:
            node_list = G.nodes()
        # determine labels
        labels = {}
        for l_atom in G.nodes_iter():
            labels[l_atom] = l_atom.symbol

        # draw graphs based on graph_type
        if graph_type == 'circular':
            nx.draw_circular(G, with_labels=True, labels=labels, node_list=node_list, node_size=node_size,
                             edge_color=edge_colour, node_color=node_colour)
        elif graph_type == 'random':
            nx.draw_random(G, with_labels=True, labels=labels, node_list=node_list, node_size=node_size,
                           edge_color=edge_colour, node_color=node_colour)
        elif graph_type == 'spectral':
            nx.draw_spectral(G, with_labels=True, labels=labels, node_list=node_list, node_size=node_size,
                             edge_color=edge_colour, node_color=node_colour)
        elif graph_type == 'spring':
            nx.draw_spring(G, with_labels=True, labels=labels, node_list=node_list, node_size=node_size,
                           edge_color=edge_colour, node_color=node_colour)
        elif graph_type == 'shell':
            nx.draw_shell(G, with_labels=True, labels=labels, node_list=node_list, node_size=node_size,
                          edge_color=edge_colour, node_color=node_colour)
        # elif graph_type == 'protein':
        # self.draw_protein(G, with_labels=True, labels=labels, node_list=node_list, node_size=node_size,
        #                   edge_color=edge_colour, node_color=node_colour, back_bone, side_chains, terminators)
        else:
            nx.draw_networkx(G, with_labels=True, labels=labels, node_list=node_list, node_size=node_size,
                             edge_color=edge_colour, node_color=node_colour)
        plt.show()

def draw_Graph( G ):
	nx.draw_spring(G,
			node_color=[float(G.degree(v)) for v in G],
			node_size=40,
			with_labels=False,
			cmap=plt.cm.Reds,
			)
	plt.show()

	def randBearGenealogy(self):
		"""show all direct older relatives of a random bear"""
		G = nx.Graph()
		bear = self.getRandomBear()
		self.helpGenes(G, bear.mom)
		self.helpGenes(G, bear.dad)
		nx.draw_spring(G)
		plt.show()

def main():
    """For testing with iPython"""
    # nx.draw_spring(g, with_labels=True)
    dfs = nx.Graph()
    # for k, v in tarjan(draw_network(), "sum1")[0].items():
    # for k, v in tarjan(draw_small(), "A")[0].items():
    for k, v in tarjan(draw_wiki(), "A")[0].items():
        dfs.add_edge(k, v)
    nx.draw_spring(dfs, with_labels=True)

def showGraph( graph ) :
	# pos = nx.spring_layout(graph, k=1)
	# nx.draw_networkx_nodes(graph, pos, node_size=4000, node_color="white")
	# nx.draw_networkx_edges(graph, pos, width=3, alpha=0.5, edge_color="black", arrows=True)
	# nx.draw_networkx_labels(graph, pos, font_size=12)
	# nx.draw_networkx_edge_labels(graph, pos, label_pos=0.6, font_size = 10)
	# plt.axis('off')
	nx.draw_spring (graph)
	plt.show ()

 def graph(self, plot=False):
     import networkx as nx
     G = nx.DiGraph()
     for n1,n2 in self.probas:
         G.add_edge(n1,n2,{'p':self.probas[n1,n2]})
     if plot:
         nx.draw_spring(G)
     else:
         return G

def ego():
    '''
    This node is deceptively connected because it's from the index
    (page 750 of volume2.pdf).
    '''
    g_9_56_090 = nx.ego_graph(g, '9.56.090')
    nx.draw_spring(g_9_56_090)
    plt.savefig("9.56.090.png")
    print nodes['9.56.090']

def main():
	cities = {}
	paths = defaultdict(int)
	ants = []

	#init city data
	with open('cities.txt') as cityFile:
		for line in cityFile:
			line = line.split() # to deal with blank 
			if line:
				cities[ line[0] ] = int(line[1])

	numberOfAnts = int(len(cities)*1.5)

	numberOfIterations = 10
	optimalDistance = 1000000
	optimalPath = []
	money = 0
	

	for i in range(numberOfIterations):
			#init distance data
		with open('distances.txt') as distanceFile:
			for line in distanceFile:
				line = line.split()
				if line:
					initMatrixAtIndexes(paths,line[0],line[1],int(line[2]),cities)

		ALPHA = random.randint(1,1)
		BETA = random.randint(1,1)
		#EVAPORATION_RATE = random.random()
		ants = []
		for i in range(numberOfAnts):
			a = Ant('INITIAL')
			ants.append(a)

		for a in ants:
			#Tour until stuck or until visited all cities
			for i in range(len(cities)):
				if not a.hasVisitedAllCities(cities) and not a.isStuck():
					evaporatePheromones(paths,ants)
					a.moveToNextEdge(paths)
				elif not a.hasReturnedHome() and not a.isStuck():
					evaporatePheromones(paths,ants)
					a.returnToStartingCity(paths)
			if (a.getTravelledDistance()<optimalDistance and not a.isStuck()):
				optimalPath = a.getPath()
				optimalDistance = a.getTravelledDistance()
				money = a.getMoney()		
	g=nx.DiGraph()
		
	for i in range (len(optimalPath)-1):
		g.add_weighted_edges_from([(optimalPath[i],optimalPath[i+1],paths[(optimalPath[i],optimalPath[i+1])]['distance'])])
	nx.draw_spring(g)
	plt.savefig("file.png")
	nx.write_dot(g,'file.dot')
	print optimalDistance, optimalPath, money

	def showGraph(self):
		"""show a graph of all bears that are alive"""
		G = nx.Graph()
		for bear in self.bears:
			mom = bear.mom
			dad = bear.dad
			if dad!=None and mom != None:
				G.add_edges_from([(str(mom),str(mom)+"-"+str(dad)),(str(mom)+str(dad),str(dad)), (str(mom)+str(dad), str(bear))])
		nx.draw_spring(G)
		plt.show()

def bn_ex():
    print("BN Example")
    fig, ax = newfig(1.0)

    G = nx.DiGraph()
    for (p, q) in [('A', 'C'), ('B', 'C'), ('C', 'D')]:
        G.add_edge(p, q)

    nx.draw_spring(G, node_color='w', ax=ax, with_labels=True, font_size=10)
    savefig('bn_ex')

def graphattempt():
	G = nx.Graph() 
	for friend in frndct:
		for person in frndct[friend]:
			G.add_edge(friend, person)
	
	nx.write_gexf(G, 'networkforge.gexf')
	pos=nx.spring_layout(G)
	nx.draw_spring(G, with_labels=True, font_size=20, font_color='black', node_color = "steelblue") 
	plt.show()

def test_multilayer():
    net = Multilayer([2,5,1])
    print net.network_inputs
    print net.network_outputs
    print net.hidden_layers
    print net.network.edges()
    print net.evaluate_pattern([1.0, 1.0])
    import matplotlib.pyplot as plt
    import networkx
    networkx.draw_spring(net.network)
    plt.show()