gistfile1.py

from igraph import *

	
def comp_delta(ER,ER_old): # evaluates the graph
	
	print "delta"
	
	n_modu = ER.modularity(ER.community_multilevel(return_levels=False),weights=None)
	o_modu = ER_old.modularity(ER_old.community_multilevel(return_levels=False),weights=None)
	
	n_min_cut = float(len(ER.mincut().cut))/50
	o_min_cut = float(len(ER_old.mincut().cut))/50
	
	n_apl = ER.average_path_length()/50
	o_apl = ER_old.average_path_length()/50
		
	try:
		d_modu = float(n_modu - o_modu) / float(o_modu)
	except:
		d_modu = 0.000000000001
	d_min_cut = float(n_min_cut - o_min_cut) / float(o_min_cut)
	d_apl = float(o_apl - n_apl) / float(o_apl)
	
	delta = d_modu + d_apl + d_min_cut

	return delta


def possible_new_edges(G):
	
	print "Possible new edges"
	
	allPossibleNewEdges = []
	for n1 in range(50):
		for n2 in range(n1,50):
			if G.are_connected(G.vs[n1],G.vs[n2]) == False and n1 != n2:
				allPossibleNewEdges.append(G.vs[n1],G.vs[n2])
	return allPossibleNewEdges

def add_optimal_edge(graph, n=3):
	
	print "Add optimal edge"
	
	paths = [[graph]] # start off with just one graph path, which contains a single graph
	for generation in range(n):
		
		print "Generation:", generation
		
		# path[-1] is the latest graph for each generation
		paths = (path + path[-1].add_edge(e) for path in paths for e in path[-1].possible_new_edges())
	# select best path by comparison of final generation against original graph
	#best = max(paths, lambda path: rank(graph, path[-1])) 
	best = max(paths, lambda path: delta(path[-1],graph)) 
	return best[1] # returns the first generation graph

graph = Graph.Erdos_Renyi(50, .15, directed=False, loops=False) # create a random root graph of density 0.1

add_optimal_edge(graph)