def test_planned_path_smoothing():
    start_pos = [2650, 2650]
    goal_pos = [1900, 400]

    graph_path = plan_path(start_pos, goal_pos)

    path_pos = nx.get_node_attributes(graph_path, 'pos')

    #this relies on the fact that nodes are sorted properly
    od = OrderedDict(sorted(path_pos.items(), key=lambda t: t[0]))

    path_keys = od.keys()
    path_list = od.values()

    #finally, actual smoothing
    smoothed_path = smooth(path_list)

    printpaths(path_list, smoothed_path)
    
    smoothed_graph = deepcopy(graph_path)

    for i, k in enumerate(path_keys):
        smoothed_graph.node[k]['pos'] = smoothed_path[i]
    
    smoothed_pos = nx.get_node_attributes(smoothed_graph, 'pos')

    plot_map()
    
    nx.draw(smoothed_graph, smoothed_pos, node_size=5, edge_color='r')
    
    nx.draw(graph_path, path_pos, node_size=5, edge_color='b')
    #nx.draw_networkx_labels(graph_path, path_pos)

    plt.show()

def drawGraph(G):
	xcords = nx.get_node_attributes(G,'x')
	ycords = nx.get_node_attributes(G,'y')
	coordinates = dict([(k, [xcords[k], ycords[k]]) for k in xcords])
	ns = nx.get_node_attributes(G, 'n')
	nx.draw_networkx(G,pos=coordinates,node_color=[1 if int(ns[i])>0 else 0 for i in ns],cmap=py.cm.PuBu)
	py.show() 

    def loc_save(self,S):
        """
        save txt 
        node ID , True pos x , True pos y , est pos x , est pos y , timestamp


        Attributes:
        ----------
        
        S        : Simulation
                   Scipy.Simulation object

        """

        pos=nx.get_node_attributes(self,'p')
        pe=nx.get_node_attributes(self,'pe_alg')
        typ = nx.get_node_attributes(self,'type')
        if self.idx == 0:
            entete = 'NodeID, True Position x, True Position y, Est Position x, Est Position y, Timestamp\n'
            file=open(basename+'/' + pstruc['DIRNETSAVE'] +'/simulation.txt','write')
            file.write(entete)
            file.close()

        try:
            file=open(basename+'/' + pstruc['DIRNETSAVE'] +'/simulation.txt','a')
            for n in self.nodes():
                if typ[n] != 'ap':
                    data = n + ',' + str(pos[n][0]) + ',' + str(pos[n][1]) + ',' + str(pe[n][0][0]) + ',' + str(pe[n][0][1]) + ',' +pyu.timestamp(S.now()) +',\n'
                    file.write(data)
            file.close()
            self.idx = self.idx +1
        except:
            pass

 def run_monte_carlo(self, pickle_fn=None, init=False):
     if init:
         self.results = []
     for nnodes in self.nnodes:
         print 'Running MC n='+repr(nnodes)
         embed_param = self.get_embed_param(nnodes)
         for mc in xrange(self.nmc):
             G = self.get_random_graph(nnodes)
             for epar in embed_param:
                 embed = epar['embed'] 
                 x = embed.embed(G)
                 x = embed.get_embedding(epar['dim'], epar['scale'])
                 
                 k_means = KMeans(init='k-means++', k=self.k, n_init=5)
                 pred = k_means.fit(x).labels_
                 epar['num_diff'][mc] = num_diff_w_perms(
                                             nx.get_node_attributes(G, 'block').values(), pred)
                 epar['rand_idx'][mc] = metrics.adjusted_rand_score(
                                             nx.get_node_attributes(G, 'block').values(), pred)
         [epar.pop('embed') for epar  in embed_param] # pop off the Embedding to save space
         self.results.extend(embed_param)
         if pickle_fn:
             pickle.dump(self, open(pickle_fn,'wb'))
             print 'Saved to '+pickle_fn
     return self.results

    def plot_graph(cls, G, filename=None, node_attribute_name='id', edge_attribute_name=None, 
                    colored_nodes=None, colored_edges=None, colored_path=None, **kwargs):
    #def plot_graph(self, G, out_file, **kwd):
        """plot graph"""
        plt.clf()

        # get the layout of G
        pos = nx.get_node_attributes(G, 'pos')
        if not pos:
            pos = nx.spring_layout(G)

        # get node attributes
        with_labels = False
        node_labels = None
        if node_attribute_name == 'id':
            with_labels = True
        elif node_attribute_name:
            node_labels = nx.get_node_attributes(G, node_attribute_name)

        # get edge attributes
        if not edge_attribute_name:
            edge_labels = nx.get_edge_attributes(G, edge_attribute_name)

        # colored nodes
        node_default_color = '0.75' # Gray shades 

        node_color = node_default_color
        if colored_nodes:
            node_color = ['r' if node in colored_nodes else node_default_color
                            for node in G.nodes()]

        # colored path
        if colored_path:
            nrof_nodes = len(colored_path)
            idx = 0
            colored_edges = list()
            while idx < nrof_nodes-1:
                colored_edges.append((colored_path[idx], colored_path[idx+1]))
                idx += 1

        # colored edges
        edge_default_color = 'k' # black
        edge_color = edge_default_color
        if colored_edges:
            set_colored_edges = {frozenset(t) for t in colored_edges}  # G.edges returns a list of 2-tuples

            edge_color = ['r' if frozenset([u, v]) in set_colored_edges else edge_default_color
                            for u, v in G.edges()]


        # draw 
        nx.draw(G, pos, with_labels=with_labels, node_color=node_color, edge_color=edge_color, **kwargs)
        if node_labels:
            nx.draw_networkx_labels(G, pos, labels=node_labels)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

        if filename:
            plt.savefig(filename, bbox_inches='tight', pad_inches=0)
        else:
            plt.show()

def find_seq_changes(nodes, G, name):
	limit = len(nodes)
	errors =[]
	G1=G.copy()
	nodes_to_be_deleted=nodes[:]
	ranks = nx.get_node_attributes(G1,"weight_rank")
	ranks_keys = {y:x for x,y in ranks.iteritems()}
	for count in range(1,limit):
		weights_original = nx.get_node_attributes(G1, "weight_sum")
		
		G1, interface_nodes_new = delete_node_by_rank(nodes_to_be_deleted, G1, 1)
		nodes_to_be_deleted.remove(ranks_keys[1])
		
		G1 = find_ranks(interface_nodes_new, G1, find_weights, 'weight')
		weights_new = nx.get_node_attributes(G1, "weight_sum")
		
		error =0.0
		for node in weights_new:
			error += np.square(weights_original[node] - weights_new[node])
		G.node[ranks_keys[1]][name+"_sum"] = round(error/len(nodes), 6)
		errors.append((ranks_keys[1], round(error/len(nodes), 6)))
		ranks = nx.get_node_attributes(G1,"weight_rank")
		ranks_keys = {y:x for x,y in ranks.iteritems()}
	G.node[nodes_to_be_deleted[0]][name+"_sum"] = 0
	errors.append((nodes_to_be_deleted[0], 0))
	return sorted(errors, key=operator.itemgetter(1)), G

def process_graph(graph):
	for (n, data) in graph.nodes(data=True):
		data["orig_id"] = str(n)

	# get largest connected component
	sc = sorted(nx.connected_components(graph), key=len, reverse=True)
	lcc = graph.subgraph(sc[0])
	graph = lcc

	graph = nx.convert_node_labels_to_integers(graph)

	if hasattr(graph, 'pos'):
		pos = graph.pos
	else:
		x = nx.get_node_attributes(graph, 'x')
		y = nx.get_node_attributes(graph, 'y')
		if len(x) != 0 and len(y) != 0:
			pos = { n: [x[n], y[n]] for n in graph.nodes() }
		else:
			pos = nx.spring_layout(graph)

	#graph = nx.Graph(graph) # in case of di/multi graph
	graph.pos = pos

	if len(nx.get_edge_attributes(graph, 'weight')) == 0:
		for (u,v) in graph.edges():
			weight = 1
			graph[u][v]['weight'] = weight

	return graph

    def _retrieve_skycoords(V):
        coords_l = []
        # Accessing the borders one by one. At this step, V_subgraphs contains a list of cycles
        # (i.e. one describing the external border of the MOC component and several describing the holes
        # found in the MOC component).
        V_subgraphs = nx.connected_component_subgraphs(V)
        for v in V_subgraphs:
            # Compute the MST for each cycle
            v = nx.convert_node_labels_to_integers(v)
            mst = nx.minimum_spanning_tree(v)
            # Get one end of the span tree by looping over its node and checking if the degree is one
            src = None
            for (node, deg) in mst.degree():
                if deg == 1:
                    src = node
                    break

            # Get the unordered lon and lat
            ra = np.asarray(list(nx.get_node_attributes(v, 'ra').values()))
            dec = np.asarray(list(nx.get_node_attributes(v, 'dec').values()))
            coords = np.vstack((ra, dec)).T
            # Get the ordering from the MST
            ordering = np.asarray(list(nx.dfs_preorder_nodes(mst, src)))
            # Order the coords
            coords = coords[ordering]
            # Get a skycoord containing N coordinates computed from the Nx2 `coords` array
            coords = SkyCoord(coords, unit="deg")
            coords_l.append(coords)

        return coords_l

def clust(Graph):
    """
    Returns the graph that merges artificial loops into a
    single node. Detects the nodes included to the triangles
    and merges them. Uses the extern function merge_nodes.
    
    Parameters
    --------
    Graph : input graph with artificial loops
    
    Returns
    -------
    G : a graph without loops; triangles of neighboring nodes
    are replaced by a single node


    """
    G = Graph.copy()
    size = G.number_of_nodes()           
    for i in G.nodes():
        neigh = nx.get_node_attributes(G, 'neig')
        index = nx.get_node_attributes(G, 'index')
        if (i in G.nodes() and nx.triangles(G, i))>0:
            n = nx.all_neighbors(G,i)
            l = [i]
            for k in n:
                if ((neigh[k]>2) and 
                    (nx.get_edge_attributes(G, 'length')[min(i,k), max(i,k)]<2)):
                    l = np.append(l, k)
            merge_nodes(G,l,size+1,index = index[i], neig = neigh[i])
            size+=1
        if (i==G.number_of_nodes()):
            break
    G = nx.convert_node_labels_to_integers(G, first_label=1)
    return G

    def _split_nodes(self, node_class_names):
        """
        Split nodes based on the attribute specified in self.node_class_attribute

        :param node_class_names: Values of node_class_attribute which will be included in the plot (in clockwise order)
        :type node_class_names: list
        :return: A dictionary whose keys are the node class attribute values, and values are lists of nodes belonging to that class
        :rtype: dict
        """
        node_attribute_dict = nx.get_node_attributes(self.network, self.node_class_attribute)
        if self.order_nodes_by != 'degree':
            valid_node_set = set(nx.get_node_attributes(self.network, self.order_nodes_by))
        else:
            valid_node_set = set(node_attribute_dict)

        if node_class_names is None:
            node_class_names = set(node_attribute_dict.values())
            if len(node_class_names) > 3:
                raise ValueError("Nodes should be in 3 or fewer classes based on their {} attribute.".format(
                    self.node_class_attribute))
            node_class_names = sorted(node_class_names)
        else:
            for_deletion = []
            for node in node_attribute_dict:
                if node_attribute_dict[node] not in node_class_names:
                    for_deletion.append(node)
            for fd in for_deletion:
                node_attribute_dict.pop(fd)

        split_nodes = OrderedDict([(node_class, []) for node_class in node_class_names])
        for node_name, node_class in node_attribute_dict.items():
            if node_name in valid_node_set:
                split_nodes[node_class].append(node_name)

        return split_nodes

def test_weights_planning():
    plot_map()

    start_pos = [ 2650, 2650 ]

    L, c = grid_graph(start_pos, dim=10, width=1000)

    filename = os.path.join(root, 'flash', 'fft2', 'processed', 'map.png')

    img_data = imread(filename)

    custom_labels = add_weights(L, img_data)

    astar_path = nx.astar_path(L, (5, 5), (0, 4))

    H = L.subgraph(astar_path)

    h_pos = nx.get_node_attributes(H, 'pos')

    pos = nx.get_node_attributes(L,'pos')
    nx.draw(L, pos, node_size=5)

    edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in L.edges(data=True)])

    nx.draw_networkx_edge_labels(L,pos,edge_labels=edge_weight)
    nx.draw_networkx_nodes(L,pos, node_size=0)
    nx.draw_networkx_edges(L,pos)
    nx.draw_networkx_labels(L,pos, labels=custom_labels)

    nx.draw(H,h_pos, node_size=5, edge_color='r')


    plt.show()

def copy_layout_GML2NX(Fname, Graph, verbose=1):
    if not Fname[-4:]=='.gml': Fname+='.gml'
    print 'Copying layout from', Fname+'..'
    
    g1 =  NX.read_gml( Fname )
    labels1 = NX.get_node_attributes(g1, 'label')
    n1 = set(labels1.values())
    
    nodes = set( Graph.nodes() )

    if not n1:
        print '   empty layout graph'
        return
    if not nodes:
        print '   empty target graph'
        return

    mapping = {}
    for L1 in labels1:
        for name in nodes:
            if labels1[L1]==name:
                mapping[L1] = name
                break

    intersection = len(nodes.intersection(n1))
    percent=100.*intersection/len(nodes)
    print '   %.1f%%'%percent,'(%i positions)'%intersection

    layout = NX.get_node_attributes(g1, 'graphics')
    attr = dict([  (  mapping[ID],  {'x':layout[ID]['x'],'y':layout[ID]['y']}  )   for ID in mapping])
    
    NX.set_node_attributes( Graph, 'graphics', attr)

	def plotGraph(self):
		self.posH = nx.get_node_attributes(self.H,'xy')
		self.posG = nx.get_node_attributes(self.G,'xy')
		self.posDG = nx.get_node_attributes(self.DG,'xy')

		self.color=[]
		for i,j in self.H.edges_iter():
			self.color.append(self.H[i][j]['color'])
		self.elabels = dict([((u,v,),int(d['key'])) for u,v,d in self.G.edges(data=True)])
		#for i,j in self.H.edges_iter():
		#	print self.H[i][j]['color']
		#print elabels
		#nx.draw_networkx_nodes(self.G, posG, with_labels=False, node_size = 50, ax=self.a)
		#nx.draw_networkx_edges(self.G, posG, edge_labels=elabels, edge_color='b', with_labels=True, width = 2, ax=self.a)

		nx.draw_networkx_nodes(self.G, self.posG, with_labels=False, node_size = 150, node_color='#A0CBE2', ax=self.a)
		nx.draw_networkx_edges(self.H, self.posH, edge_color=self.color, edge_cmap=self.cmap, width = 5, alpha=1, ax=self.a) # , edge_vmin=0, edge_vmax=1
		nx.draw_networkx_nodes(self.DG, self.posDG, node_size=150, alpha=1, ax=self.a, arrows=True, edge_color='r')
		#nx.draw_networkx_edges(self.DG, self.posDG, alpha=1, width = 2, ax=self.a, arrows=True, edge_color='r')
		#nx.draw_networkx_edges(self.H, posH, edge_color='k', width = 0.5, alpha=1., ax=self.a)
		nx.draw_networkx_edge_labels(self.G, self.posG, edge_labels=self.elabels, font_size= 12, alpha = 0.4, rotate=True)
		self.a.set_title("Gas Network colored by values of pressure.")
		self.a.text(0.45,0.05, "Time t = %.4f hours" % 0,transform=self.a.transAxes )
		self.ax1 = self.f.add_axes([ 0.02, 0.05, 0.04, 0.9])
		norm = mpl.colors.Normalize(vmin=3, vmax=7)
		cb1 = mpl.colorbar.ColorbarBase(self.ax1, cmap=self.cmap, norm=norm, orientation='vertical') #, norm=norm, orientation='horizontal')
		cb1.set_ticks([3, 4, 5, 6, 7])
		cb1.set_label('Pressure in MPa', labelpad=3)
		self.canvas.draw()

    def get_pos(self,RAT=None):
        """ get node positions

        Parameters 
        ----------

        RAT : specify a RAT to display node position. If None, all RAT are displayed    
        
        Returns 
        -------

        dictionnary :     key     : node ID
        value     : np.array node position
        

        """
        if RAT == None:
            if self.node[self.nodes()[0]].has_key('p'):
                return nx.get_node_attributes(self,'p')
            else :
                return nx.get_node_attributes(self,'pe')
        else :
            try:
                if self.SubNet[RAT].node[self.SubNet[RAT].nodes()[0]].has_key('p'):
                    return nx.get_node_attributes(self.SubNet[RAT],'p')
                else :
                    return nx.get_node_attributes(self.SubNet[RAT],'pe')
            except: 
                raise NameError('invalid RAT name')

    def consistent(self):
        """
        Determine if the assignment of values to the lattice is self-consistant.

        Returns
        -------
        valid : bool
            True if the lattice is self-consistent, False otherwise.
        """
        reds = nx.get_node_attributes(self._lattice, 'red')
        pis = nx.get_node_attributes(self._lattice, 'pi')

        if self.SELF_REDUNDANCY:  # pragma: no branch
            for node in self._lattice:
                if len(node) == 1:
                    red = reds[node]
                    mi = coinformation(self._dist, [node[0], self._output])
                    if not np.isclose(red, mi, atol=1e-5, rtol=1e-5):  # pragma: no cover
                        return False

        # ensure that the mobius inversion holds
        for node in self._lattice:
            red = reds[node]
            parts = sum(pis[n] for n in descendants(self._lattice, node, self=True))
            if not np.isnan(red) and not np.isnan(parts):
                if not np.isclose(red, parts, atol=1e-5, rtol=1e-5):
                    return False

        return True

    def test_build_unique_fragments(self):
        edges = {(e[0], e[1]): None for e in self.pc_edges}
        mol_graph = MoleculeGraph.with_edges(self.pc, edges)
        unique_fragments = mol_graph.build_unique_fragments()
        self.assertEqual(len(unique_fragments), 295)
        nm = iso.categorical_node_match("specie", "ERROR")
        for ii in range(295):
            # Test that each fragment is unique
            for jj in range(ii + 1, 295):
                self.assertFalse(
                    nx.is_isomorphic(unique_fragments[ii].graph,
                                     unique_fragments[jj].graph,
                                     node_match=nm))

            # Test that each fragment correctly maps between Molecule and graph
            self.assertEqual(len(unique_fragments[ii].molecule),
                             len(unique_fragments[ii].graph.nodes))
            species = nx.get_node_attributes(unique_fragments[ii].graph, "specie")
            coords = nx.get_node_attributes(unique_fragments[ii].graph, "coords")

            mol = unique_fragments[ii].molecule
            for ss, site in enumerate(mol):
                self.assertEqual(str(species[ss]), str(site.specie))
                self.assertEqual(coords[ss][0], site.coords[0])
                self.assertEqual(coords[ss][1], site.coords[1])
                self.assertEqual(coords[ss][2], site.coords[2])

            # Test that each fragment is connected
            self.assertTrue(nx.is_connected(unique_fragments[ii].graph.to_undirected()))

    def compute_LDPs(self,ln,RAT):
        """compute edge LDP

        Parameters
        ----------

        n1      : float/string
            node ID
        n2      : float/string
            node ID
        RAT     : string
            A specific RAT which exist in the network ( if not , raises an error)
        value    : list : [LDP value , LDP standard deviation] 
        method    : ElectroMagnetic Solver method ( 'direct', 'Multiwall', 'PyRay'


        """
        p=nx.get_node_attributes(self.SubNet[RAT],'p')
        epwr=nx.get_node_attributes(self.SubNet[RAT],'epwr')
        sens=nx.get_node_attributes(self.SubNet[RAT],'sens')
        e=self.link[RAT]#self.SubNet[RAT].edges()
        re=self.relink[RAT] # reverse link aka other direction of link
        lp,lt, d, v= self.EMS.solve(p,e,'all',RAT,epwr,sens)
        lD=[{'Pr':lp[i],'TOA':lt[np.mod(i,len(e))] ,'d':d[np.mod(i,len(e))],'vis':v[i]} for i in range(len(d))]
        self.update_LDPs(iter(e+re),RAT,lD)

def copy_layout(from_fname, to_fname):
    if not from_fname[-4:]  =='.gml': from_name +='.gml'
    if not to_fname[-4:]    =='.gml': to_name   +='.gml'

    print 'reading A=', from_fname,'..',
    g1 =  NX.read_gml(from_fname)
    labels1 = NX.get_node_attributes(g1, 'label')
    n1 = set(labels1.values())
    print len(n1),'nodes'
    
    print 'reading B=', to_fname,'..',
    g2 =    NX.read_gml(to_fname)
    labels2 = NX.get_node_attributes(g2, 'label')
    n2 = set(labels2.values())
    print len(n2),'nodes'

    intersection = len(n2.intersection(n1))
    percent=100.*intersection/len(n2)
    print 'B.intersect(A)=',intersection,'(%.1f%%)'%percent

    print 'copying layout..',
    mapping = {}
    for L1 in labels1:
        for L2 in labels2:
            if labels1[L1]==labels2[L2]:
                mapping[L1] = L2
                break

    layout = NX.get_node_attributes(g1, 'graphics')
    attr = dict([  (  mapping[ID],  {'x':layout[ID]['x'],'y':layout[ID]['y']}  )   for ID in mapping])
    
    NX.set_node_attributes(g2, 'graphics', attr)
    NX.write_gml(g2, to_fname)
    print 'done.'

    def drawLabels(self, labelAll=True):
        """Draw labels on nodes in graph (nodeId by default)"""
#        circleNodes = [ n for (n, m) in self.G.nodes(data=True) if m.get('shape','circle') == 'circle']
#        pdb.set_trace()
        if labelAll:
            nx.draw_networkx_labels(self.G, 
              pos=nx.get_node_attributes(self.G, 'pos'),
              font_size=10,
              labels=self.labelMap)
        else:
#             boxNodes = [ n for (n, m) in self.G.nodes(data=True) if m.get('shape','circle') == 'box']
#             lm = {} 
#             for n in boxNodes:
#                 lm[n]=self.labelMap[n]
#             nx.draw_networkx_labels(self.G, 
#               pos=nx.get_node_attributes(self.G, 'pos'),
#               font_size=10,
#               labels=lm)
            emptyNodes = [ n for (n,m) in self.G.nodes(data=True) if m.get('shape','circle') == 'empty']
            if emptyNodes:
                lm = {} 
                for n in emptyNodes:
                    lm[n]=self.labelMap[n]
                nx.draw_networkx_labels(self.G,
                  pos=nx.get_node_attributes(self.G, 'pos'),
                  font_size=10,
                  labels=lm)

def recursive_f (scopegraph, scope):
    #no need to calc this every scope, find another solution 
    ex_scopes=nx.get_node_attributes(scopegraph, 'ex')
    cond_scopes=nx.get_node_attributes(scopegraph, 'cond')
    ab_scopes=nx.get_node_attributes(scopegraph, 'ab')
    
    print ("new scope {0}".format(scope))
    ex = ex_scopes[scope]
    print
    ab_state = ab_scopes[scope]
    cond = cond_scopes[scope]
    #print ("ex: {0}, cond{1}".format(ex, cond))
    flag = True
    while(len(ab_state._abstract_store) != 0):
        if(flag):
            flag = False
            ab_state = abex.abstract_execution_for_simple_loop(ab_state, ex, cond, True)
            if len(scopegraph.successors(scope)) != 0: #multi edges not supported
                print ("scopegraph succesors {0}".format(scopegraph.successors(scope)[0]))
                recursive_f(scopegraph, scopegraph.successors(scope)[0])

                #scopegraph.remove_node(scopegraph.succesors(node))
        else: 
            ab_state = abex.abstract_execution_for_simple_loop(ab_state, ex, cond, False)
            if len(scopegraph.successors(scope)) != 0: #multi edges not supported
                print ("scopegraph succesors {0}".format(scopegraph.successors(scope)[0]))
                recursive_f(scopegraph, scopegraph.successors(scope)[0])