def maximum_shortest_path(G):
	max_path = 0
	for i in nx.nodes_iter(G):
		for j in nx.nodes_iter(G):
			if nx.has_path(G, i,j):
				path = nx.shortest_path_length(G, i, j)
				if path > max_path:
					max_path = path
	return max_path

def remove_catalysis(Graph):
    """
    DESCRIPTION:\n
        Return a Graph where Catalysis were removed.\n
        Remove Catalysis nodes from a graph generated with a BioPAX file.\n
        Catalysis has to be a 'biopax.entity_type' attribute of node.\n
    
    USAGE:\n
        Graph - a graph generated with NetworkX
    """
    print_nodes(Graph)
    targets = []
    for i in nx.nodes_iter(Graph):
        if Graph.node[i]['biopax.entity_type'] == 'Catalysis':
            targets.append(i)
            neigh = Graph[i].keys() #neighboors of catalysis node
            enz = [] #enzymes neighboors of catalysis node
            react = [] #reactions neigh of catalysis node
            pairs = []
            for n in neigh:
                if Graph[i][n][0]['label'] == 'CONTROLLER':
                    enz.append(n)
                elif Graph[i][n][0]['label'] == 'CONTROLLED':
                    react.append(n)
            for p in it.product(enz,react): #compute couple E1 R1 - E2 R1, etc.
                pairs.append(p)
            Graph.add_edges_from(pairs,root_index = '',label = 'CONTROLLER')
    if len(targets) == 0:
        print "No Catalysis node found in network"
    else:
        Graph.remove_nodes_from(targets)
        print "%d Catalysis nodes removed" % (len(targets))
        print_nodes(Graph)
    return Graph

def find_nodes_with_degree(graph, filter_function):
    junctures = []
    for node in nx.nodes_iter(graph):
        degree = nx.degree(graph, node)
        if filter_function(degree):
            junctures.append(node)
    return junctures

    def compare_list(self, graph_list, types, h, D):
        """
        Compute the all-pairs kernel values for a list of graph representations of verification tasks
        """
        all_graphs_number_of_nodes = 0
        node_labels = [0] * (h+1)
        node_depth = [0] * len(graph_list)
        edge_types = [0] * len(graph_list)
        edge_truth = [0] * len(graph_list)

        for it in range(h+1):
            node_labels[it] = [0] * len(graph_list)

        for i, g in enumerate(graph_list):
            node_labels[0][i] = {key: self._compress(value)
                                 for key, value in nx.get_node_attributes(g, 'label').items()}
            node_depth[i] = nx.get_node_attributes(g, 'depth')
            edge_types[i] = nx.get_edge_attributes(g, 'type')
            edge_truth[i] = nx.get_edge_attributes(g, 'truth')
            all_graphs_number_of_nodes += len([node for node in nx.nodes_iter(g) if node_depth[i][node] <= D])
            # if i == 0:
            #     self._graph_to_dot(g, node_labels[0][i], "graph{}.dot".format(i))

        # all_graphs_number_of_nodes is upper bound for number of possible edge labels
        phi = np.zeros((all_graphs_number_of_nodes, len(graph_list)), dtype=np.uint64)

        # h = 0
        for i, g in enumerate(graph_list):
            for node in g.nodes_iter():
                if node_depth[i][node] <= D:
                    label = node_labels[0][i][node]
                    phi[self._compress(label), i] += 1

        K = np.dot(phi.transpose(), phi)

        # h > 0
        for it in range(1, h+1):
            # Todo check if the shape fits in all cases
            phi = np.zeros((2*all_graphs_number_of_nodes, len(graph_list)), dtype=np.uint64)

            print('Updating node labels of graphs in iteration {}'.format(it), flush=True)

            # for each graph update edge labels
            for i, g in tqdm(list(enumerate(graph_list))):
                node_labels[it][i] = {}
                for node in g.nodes_iter():
                    if node_depth[i][node] <= D:
                        label_collection = self._collect_labels(node, i, g, it-1, node_labels, node_depth, types, D, edge_types, edge_truth)
                        long_label = "_".join(str(x) for x in [np.concatenate([np.array([node_labels[it-1][i][node]]),
                                                               np.sort(label_collection)])])
                        node_labels[it][i][node] = self._compress(long_label)
                        phi[self._compress(long_label), i] += 1
                        # node_labels[it][i][node] = long_label
                        # phi[self._compress(long_label), i] += 1
                # if i == 0:
                #     self._graph_to_dot(g, node_labels[it][i], "graph{}_it{}.dot".format(i, it))

            K += np.dot(phi.transpose(), phi)

        return K

def graphToCSV(G,graphtype, section, test):
    directory = "Datarows/"+graphtype+"/"
    if not os.path.exists(directory):
        os.makedirs(directory)
    writer_true = csv.writer(open(directory+section+"_true.csv", "a"))
    writer_false = csv.writer(open(directory+section+"_false.csv", "a"))
    A = nx.to_numpy_matrix(G)
    A = np.reshape(A, -1)
    arrGraph = np.squeeze(np.asarray(A))

    nb_nodes = 0
    for node in nx.nodes_iter(G):
        if len(G.neighbors(node))>0:
            nb_nodes += 1

    meta_info = [test,nb_nodes,G.number_of_edges(),nx.number_connected_components(G)]
    # On garde la même taille d'élemt de valeur de vérité #
    if test:
        if os.path.getsize(directory+section+"_true.csv") <= os.path.getsize(directory+section+"_false.csv"):
            writer_true.writerow(np.append(arrGraph, meta_info))
            return True
        else:
            return False
    else:
        if os.path.getsize(directory+section+"_false.csv") <= os.path.getsize(directory+section+"_true.csv"):
            writer_false.writerow(np.append(arrGraph, meta_info))
            return True
        else:
            return False

 def connected_observations(self, subgraph):
     objids = [node for node in nx.nodes_iter(subgraph)]
     points = [p for p in self.objects if p.objid in objids]
     cat = Catalog(points)
     cat.add_constant('obscode', 807)
     cat.add_constant('err', self.astrometric_err)
     return cat

def getAllOpenTriangles(G, sets):   #  open[(u,v)]:  third edge of open triangles (u,v) in
    opens = {}          #   reverse:  node --> teamID
    index = {}
    # close = {}
    for v in nx.nodes_iter(G):
        s1 = set(G[v])
        for w in s1:
            s2 = set(G[w])
            pair = (v,w) if v < w else (w,v)
            
            if pair not in opens:
                opens[pair] = set()
                # close[pair] = set()
            else:   # add following two lines
                continue
            opens[pair] |= set([(i,v) if i < v else (v,i) for i in (s1 - s2 - set([w]))])
            opens[pair] |= set([(i,w) if i < w else (w,i) for i in (s2 - s1 - set([v]))])
            # close[pair] = s1 & s2
            for teamID, nodes in sets.iteritems():
                if v in nodes and w in nodes:
                    if pair not in index:
                        index[pair] = set()
                    index[pair].add(teamID)  # which teams edge(v,w) belongs to
    for pair in opens: 
        if opens[pair].empty(): del opens[pair]        
    return opens, index

 def updateLayout(self):
     self.pos = nx.spring_layout(self.graph)
     self.x = []
     self.y = []
     for n in nx.nodes_iter(self.graph):
         self.x.append(self.pos[n][0])
         self.y.append(self.pos[n][1])

def analyze_event_sequence_graph(graph_file):
    G = cPickle.load(open(graph_file, 'rb'))
    
    sequences_by_degree = {}
    for n in nx.nodes_iter(G):
        if G.node[n]['type'] == 'section':
            sequences_by_degree[n] = G.degree(n)

    sorted_seq = sorted(sequences_by_degree.iteritems(), key=itemgetter(0))

    print sorted_seq

    # plot parameters
    imw = 1024.0 # the full image width
    imh = 1024.0
    lm = 40.0
    rm = 50.0
    tm = 50.0
    bm = 50.0
    res = 72.0
    
    imwi = imw/res
    imhi = imh/res
    fig = mplt.figure(figsize=(imwi, imhi), dpi=res)
    ph = imh - tm - bm # the height for both matricies
    pw = imw - lm - rm
    ax = fig.add_axes((lm/imw, bm/imh, pw/imw, ph/imh))

    ax.plot(range(len(sorted_seq)),[x[1] for x in sorted_seq])

    print [x for x in G.edges(sorted_seq[0][0], data=True)]

def pkg_filter(g):
    # removes built-in packages
    non_built_in = g.nodes()
    for n in nx.nodes_iter(g):
        prime_pkg = n.split('.')
        if prime_pkg[0] in built_in_pkgs:
            non_built_in.remove(n)
    return g.subgraph(non_built_in)

def point_sizes(g, node_sizes):
    sizes = []
    for n in nx.nodes_iter(g):
        if (node_sizes.has_key(n)):
            sizes.append(node_sizes[n])
        else:
            sizes.append(0)
    return sizes

 def draw(self):
     if(drawgif):
         nodeColors = [x.color for x in nx.nodes_iter(self.worldgraph)]
         plt.figure(figsize=(8,6))
         plt.title("Network at Age "+str(self.age))
         nx.draw(self.worldgraph, pos=self.nodeLayout, node_color=nodeColors, node_size=30, hold=1)
         plt.savefig("graphseries/graph"+str(self.age).zfill(4)+".png", dpi=250)
         plt.close()

    def refine(self, threshold):

        big_nodes = []
        for n in nx.nodes_iter(self.graph):
            if nx.degree(self.graph, n) >= threshold:
                big_nodes.append(n)

        sg = self.graph.subgraph(big_nodes)
        self.setGraph(sg);

def nearest_vertex(G,measurement):
	minimum_distance = 1000000
	for node in nx.nodes_iter(G):
		pos = G.node[node]['pos']
		distance = math.sqrt((measurement[0]-pos[0])**2+(measurement[1]-pos[1])**2)
		if distance< minimum_distance:
			minimum_distance=distance
			result = node
	return result

def printCommunities(graph, membership):
    for edge in membership:
        nodes = edge.split("-")
        u = nodes[0]
        v = nodes[1]
        graph.remove_edge(u, v)

    for node in nx.nodes_iter(graph):
        pass

def data_polish(Graph, polish_ratio = 0.3, loop = 30):
        for i in xrange(loop):
            intersection = {}
            for j in nx.nodes_iter(Graph):
                    intersection[j] = 0
            temp = Graph.copy()
            for u in nx.nodes_iter(Graph):
                L = []
                for w in (temp.neighbors(u)+[u]):
                    for v in [x for x in (temp.neighbors(w)+[w]) if x < u]:
                        if(intersection[v] == 0):
                            L.append(v)
                        intersection[v] += 1
                for v in L:
                    sim = float(intersection[v]) / ((temp.degree(v)+1) + (temp.degree(u)+1) - intersection[v])
                    polish(Graph, u, v, sim, polish_ratio)
                    intersection[v] = 0
        print "end", i+1 , "times"

def coordinate(g):
    pos = nx.spring_layout(g)
    
    x = []
    y = []
    for n in nx.nodes_iter(g):
        x.append(pos[n][0])
        y.append(pos[n][1])
    return pos, x, y

def create_egonet_features(g):
    egoNetList = []
    for n in nx.nodes_iter(g):
        resultObj = Result()
        resultObj.egoNetGraph = nx.ego_graph(g, n, radius=1, center=True, undirected=False, distance=None)
        resultObj.egoNetDegree = nx.number_of_nodes(resultObj.egoNetGraph)
        resultObj.nofEdges = nx.number_of_edges(resultObj.egoNetGraph)
        egoNetList.append(resultObj)
 #       print resultObj
    return egoNetList

 def updateSizes(self, amplification = 40):
     for n in nx.nodes_iter(self.graph):
         if self.sizeDict.has_key(n):
             pass
         else:
             self.sizeDict[n] = 0;
     if ( len(self.sizeDict) != len(self.graph.nodes()) ):
         print 'panic'
     self.sizes = []
     for key in self.sizeDict:
         self.sizes.append(self.sizeDict[key] * amplification)

def binaryAdd(G1, G2):
    '''
    "Adds" G1 and G2 on their 'class' attribute
    '''
    Gout = G1.copy()
    for v in nx.nodes_iter(Gout):
        Gout.node[v]['class'] = G1.node[v]['class'] + G2.node[v]['class']
        if Gout.node[v]['class'] == 2:
            Gout.node[v]['class'] = 1
    
    return Gout