def test_edges(self):
     assert_edges_equal(self.G.edges(), list(nx.edges(self.G)))
     assert_equal(sorted(self.DG.edges()), sorted(nx.edges(self.DG)))
     assert_edges_equal(self.G.edges(nbunch=[0, 1, 3]),
                        list(nx.edges(self.G, nbunch=[0, 1, 3])))
     assert_equal(sorted(self.DG.edges(nbunch=[0, 1, 3])),
                  sorted(nx.edges(self.DG, nbunch=[0, 1, 3])))

def bfs_bd_ucs(graph, start, goal):

    if start == goal:
        return {'cost' : 0, 'expanded' : 0}

    frontier0 = [start]
    frontier1 = [goal]
    explored0 = []
    explored1 = []
    num_explored = 0

    commonNodes = []

    while len(frontier0) + len(frontier1) > 0:

        linked01 = len(commonNodes) > 0

        ## 0 front
        if frontier0:
            node = popClosest(frontier0)
            explored0.append(node)
            if node in explored0 and node in explored1:
                commonNodes += [node]
            for edge in networkx.edges(graph, node.node['data'].id):
                child = State(graph.node[edge[1]], node, node.cost + nodeDist(node.node, graph.node[edge[1]])) 
                if child not in explored0:
                    if child not in frontier0:
                        if not linked01:
                            frontier0.append(child)
                            num_explored = num_explored + 1
                    else:
                        swapIfBetter(frontier0, child)
                        
        ## 0 front
        if frontier1:
            node = popClosest(frontier1)
            explored1.append(node)
            if node in explored0 and node in explored1:
                commonNodes += [node]
            for edge in networkx.edges(graph, node.node['data'].id):
                child = State(graph.node[edge[1]], node, node.cost + nodeDist(node.node, graph.node[edge[1]])) 
                if child not in explored1:
                    if child not in frontier1:
                        if not linked01:
                            frontier1.append(child)
                            num_explored = num_explored + 1
                    else:
                        swapIfBetter(frontier1, child)

    if commonNodes:
        bestNode = commonNodes[0]
        for node in commonNodes:
            if commonCost(node, explored0, explored1) < commonCost(bestNode, explored0, explored1):
                bestNode = node
        return {'cost' : commonCost(bestNode, explored0, explored1), 'expanded' : num_explored}

    print "No path found, explored: ", num_explored

    return None

    def update(self, dev = 0 ):
        if not dev:
            return
        else:
            print dev, dev.neighbours, nx.edges( self.proxNet, dev )
            print self.proxNet.nodes(), self.proxNet.edges()
            self.proxNet.remove_edges_from( nx.edges( self.proxNet, dev ) )

            registered = []
            for item in dev.neighbours:
                neighbour = self.deviceManager.getDevice( item )
                if neighbour != 0:
                    registered.append( neighbour )
                    
            self.proxNet.add_edges_from( [(dev, item) for item in registered] )

def get_links(g, link_type):
	if link_type == 'path':
		edges = nx.edges(g)
		l = []
		for edge in edges:
			x1 =  data_dict[str(id_key[str(edge[0])])]
			x2 =  data_dict[str(id_key[str(edge[1])])]
			l.append({'source': x1[1]+'('+str(x1[0])+')', 'target':x2[1]+'('+str(x2[0])+')'})
		return l
	else:
		edges = nx.edges(st_links)
		l = []
		for edge in edges:
			l.append({'source': str(get_name(edge[0])), 'target':str(get_name(edge[1]))})
		return l

def add_speed_attribute(GD):
	
	vertices_pos = nx.get_node_attributes(GD, 'pos')
	edge_layer_attributes = nx.get_edge_attributes(GD, "layer")
	
	for curr_edge in nx.edges(GD):
		
		u = curr_edge[0]
		v = curr_edge[1]
		
		u_pos = vertices_pos[u]
		v_pos = vertices_pos[v]
		
		u_x = float(u_pos.split(",")[0])
		v_x = float(v_pos.split(",")[0])
		
		u_y = float(u_pos.split(",")[1])
		v_y = float(v_pos.split(",")[1])
		
		distance = math.sqrt( (u_x - v_x)**2 + (u_y - v_y)**2)
		
		curr_edge_layer_attr = edge_layer_attributes[curr_edge]
		
		speed = beta
		
		if  (int(re.findall('\d+', curr_edge_layer_attr.split(":")[0])[0])==1):
			speed = alpha
		
		travel_time = distance * speed
		
		GD[u][v]['travel_time'] = travel_time
		GD[u][v]['length'] = distance

def CopyDAG(G_train, data_total, pmin, pmax):
    edges = nx.edges(G_train)
    kern = dict.fromkeys(edges)
    M = len(data_total)
    kern_temp = {}

    for edge in edges:
        kern[edge] = np.zeros(M)

    for m in range(M):
        print('Data item: %d' % m)
        data = data_total[m]
        for i in range(0, len(data)-pmin+1+1):
            for j in range(pmin-1, pmax+1):
                if data[i:i+j] in kern_temp:
                    kern_temp[data[i:i+j]][m] += 1
                else:
                    kern_temp[data[i:i+j]] = np.zeros(M)
                    kern_temp[data[i:i+j]][m] = 1

    for edge in edges:
        key = edge[0]+edge[1][-1]
        if key in kern_temp:
            kern[edge] = kern_temp[key]

    G = nx.DiGraph()
    G.add_edges_from(edges)
    nx.set_edge_attributes(G, 'kern_unnorm', kern)

    return G

def smallWorldness(graph):
	return_values = []
	#Small-worldness criteria
	n = len(nx.nodes(graph))
	e = len(nx.edges(graph))
	#probability of edges: (number of edges in real graph)/possible edges
	p = e/float((n*(n-1)/2.0))	
	##
	#generate random graph using probability
	rand_graph = nx.fast_gnp_random_graph(n, p, seed=1)
	#calculate values for real graph and random graph
	Creal = nx.transitivity(graph) #float
	Crand = nx.transitivity(rand_graph) #float
	Lreal = 0
	Lrand = 0
	real_sum = 0
	rand_sum = 0
	splReal = shortest_path_lengths(graph)
	splRand = shortest_path_lengths(rand_graph)
	for i in range(len(splReal)):
		real_sum += splReal[i]
		rand_sum += splRand[i]
	Lreal = real_sum / len(splReal)
	Lrand = rand_sum / len(splRand)		
	#compare with actual graph
	if(Lreal != 0 and Lrand !=0 and Crand !=0):
		S = (Creal)/(Crand) / (float(Lreal)/(Lrand))
	else:
		S = 0
	return_values.append(S)
	return return_values

def generate_G(graph, source_from, source_to):
	nodes = nx.nodes(graph)
	edges = nx.edges(graph)

	N_nodes = len(nodes)
	N_edges = len(edges)

	G = np.zeros((N_nodes - 1, N_nodes - 1))

	# only elements in the diagonal
	for x in nodes:
		if x == 0: 			# do not consider GND
			continue
		
		connected_nodes = nx.all_neighbors(graph, x)
		conductances = 0
		for i in connected_nodes:
			if (x == source_from and i == source_to) or (x == source_to and i == source_from):
				continue
			conductances += 1.0/(graph.get_edge_data(x, i)['weight'])
		G[x - 1][x - 1] = conductances

	# other, off diagonal elements
	for p in edges:
		if abs(p[0] - p[1]) == (p[0] + p[1]):		# if one node is GND 
			continue
		if (p[0] == source_from and p[1] == source_to) or (p[0] == source_to and p[1] == source_from):
			continue

		conductance = 1.0/graph.get_edge_data(p[0], p[1])['weight']
		G[p[0] - 1][p[1] - 1] = conductance
		G[p[1] - 1][p[0] - 1] = conductance

	return G

def random_rewiring(network):
    """
    Rewires a pair of edges such that the degree sequence is preserved.

    Arguments:
        network => The input network.

    Returns:
        A network with one pair of edges randomly rewired.
    """

    # Don't terminate until the rewiring is performed.
    while True:

        # Store the number of edges in the network to avoid repeated computation.
        network_edges = nx.edges(network)

        # If there isn't at least 1 edge, break out and return.
        if len(network_edges) == 0:
            break

        # Randomly selected a link from the network.
        link1 = (source1, target1) = random.choice(network_edges)

        # Find all the edges that share no nodes with link1.
        disjoint_links = [link for link in network_edges if not any(node in link for node in link1)]

        # If there are no disjoint links, it would be impossible to randomize the network while
        # still preserving the degree sequence, so break out and return.
        if len(disjoint_links) == 0:
            break

        # Randomly selected a DIFFERENT link from the network (no sharing of nodes allowed).
        link2 = (source2, target2) = random.choice(disjoint_links)

        # If the graph is directed, there is only one option.
        # If the graph is undirected, there are two options, each with a 50-50 chance.
        if not nx.is_directed(network) and random.random() < 0.5:

            # Rewire links A-B and C-D to A-C and B-D.
            new_link1 = (source1, source2)
            new_link2 = (target1, target2)

        else:

            # Rewire links A-B and C-D to A-D and C-B.
            new_link1 = (source1, target2)
            new_link2 = (source2, target1)

        # If the new links aren't in the network already, replace the old links with the new links.
        if not network.has_edge(*new_link1) and not network.has_edge(*new_link2):

            # Remove the old links.
            network.remove_edges_from([link1, link2])

            # Add the new links.
            network.add_edges_from([new_link1, new_link2])

            # Returned the slightly altered new network.
            return network

 def forwarder_down(self, fwID):
     tunelIDs = []
     for v in DynamicGraph[fwID].keys():
         tunelIDs += DynamicGraph[fwID][v]['tunely']
     for tunelID in tunelIDs:
         vymaz_tunel(tunelID)
     self.DynamicGraph.remove_edges_from(nx.edges(DynamicGraph, fwID))

def single_source_number_of_walks(G, source, walk_length):
    """Returns a dictionary whose keys are the vertices of `G` and whose values
    are the numbers of walks of length exactly `walk_length` joining `source`
    to that node.

    Raises :exc:`ValueError` if `walk_length` is negative.

    """
    if walk_length < 0:
        raise ValueError('walk length must be a positive integer')
    # Create a counter to store the number of walks of length
    # `walk_length`. Ensure that even unreachable vertices have count zero.
    result = Counter({v: 0 for v in G})
    queue = deque()
    queue.append((source, 0))
    # TODO We could reduce the number of iterations in this loop by performing
    # multiple `popleft()` calls at once, since the queue is partitioned into
    # slices in which all enqueued vertices in the slice are at the same
    # distance from the source. In other words, if we keep track of the
    # *number* of vertices at each distance, we could just immediately dequeue
    # all of those vertices.
    while queue:
        (u, distance) = queue.popleft()
        if distance == walk_length:
            result[u] += 1
        else:
            # Using `nx.edges()` accounts for multiedges as well.
            queue.extend((v, distance + 1) for u_, v in nx.edges(G, u))
    # Return the result as a true dictionary instead of a Counter object.
    return dict(result)

def analyseConnectedComponents(graphs):
    conflicts = {}
    for cc in graphs:
        nodes = nx.nodes(cc)
        for node in nodes:
            if nx.degree(cc,node) > 1:
                edges = nx.edges(cc,node)
                for pair in itertools.combinations(edges,2):
                    leftSet = cc[pair[0][0]][pair[0][1]]["species"]
                    left = set()
                    for elem in leftSet:
                        left.add(elem)
                    rightSet = cc[pair[1][0]][pair[1][1]]["species"]
                    right = set()
                    for elem in rightSet:
                        right.add(elem)
                    #identify conflicts
                    if not left.isdisjoint(right):
                        conflict = left.intersection(right)
                        for elem in conflict:
                            if elem in conflicts:
                                conflicts[elem].append(pair)
                            else:
                                conflicts[elem] = [pair]
    #combineConflicts(conflicts)
    print " "
    for species in conflicts:
        print "Number of conflicts in "+species+" : "+str(len(conflicts[species]))
    return conflicts

def write_gspan(graph, outfile):
    # get all subgraphs only works with undirected
    subgraphs=nx.connected_components(graph.to_undirected())
    id_count=1
    node_count=0
    #get labels
    label_dic=nx.get_node_attributes(graph,'label')
    for s in subgraphs:
        node_count_tree=0
        node_dict={}
        outfile.write("t # id "+str(id_count)+"\n")
        # for every node in subgraph
        for v in sorted(s):
        # node id restart from 0 for every sub graph
            node_dict[v]=node_count_tree
            outfile.write("v "+str(node_count_tree)+" "+label_dic[v]+" \n")
            node_count_tree+=1
            node_count+=1
            
        # all edges adjacent to a node of s
        edges=nx.edges(graph, s)
        for e in sorted(edges):
            #print(graph[e[0]][e[1]])
            try:
                outfile.write("e "+str(node_dict[e[0]])+" "+str(node_dict[e[1]])+" "+graph[e[0]][e[1]]['label']+"\n")
            except KeyError:
                outfile.write("e "+str(node_dict[e[0]])+" "+str(node_dict[e[1]]))
            
        id_count+=1

def bfs_default(graph, start, goal):

    if start == goal:
        return {'cost' : 0, 'expanded' : 0}

    frontier = [start]
    explored = []
    num_explored = 0

    while len(frontier) > 0:

        node = frontier.pop(0)

        #print node.cost

        explored.append(node)
        for edge in networkx.edges(graph, node.node['data'].id):
            child = State(graph.node[edge[1]], node, node.cost + nodeDist(node.node, graph.node[edge[1]])) 
            if child not in explored and child not in frontier:
                if child == goal:
                    return {'cost' : child.cost, 'expanded' : num_explored}
                else:
                    frontier.append(child)
                num_explored = num_explored + 1

    return None

def delete_links(G):
	'''
	Delete links in the graph if they disavantage the person.
	The link is deleted if (r1-r2)/affect(n1, n2)*deg(n1) > alpha
	where r1 > r2 and alpha is a random number between 0 and a given paramater beta.
	'''
	beta = 100
	reput = nx.get_node_attributes(G, "reput")
	affect = nx.get_edge_attributes(G, "affect")
	n = 0
	for edge in nx.edges(G):
		# Calculate alpha
		alpha = beta*random.random()

		# Define who has the higher reputation
		n1 = edge[1]
		n2 = edge[0]
		if(reput[edge[0]] > reput[edge[1]]):
			n1 = edge[0]
			n2 = edge[1]
		
		# Compute the coefficient
		coef = (reput[n1]-reput[n2])/affect[edge]*G.degree(n1)

		# Decide wether we delete the link
		if(coef > alpha):
			G.remove_edge(edge[0], edge[1])
			del affect[edge]

	# Set the new affect dict and return the graph
	nx.set_edge_attributes(G, "affect", affect)
	return G

def bfs_ucs(graph, start, goal):
    
    if start == goal:
        return {'cost' : 0, 'expanded' : 0}

    frontier = [start]
    explored = []
    num_explored = 0

    while len(frontier) > 0:

        node = popClosest(frontier)

        #print node.cost

        explored.append(node)
        if node == goal:
            return {'cost' : node.cost, 'expanded' : num_explored}
        for edge in networkx.edges(graph, node.node['data'].id):
            child = State(graph.node[edge[1]], node, node.cost + nodeDist(node.node, graph.node[edge[1]])) 
            if child not in explored:
                if child not in frontier:
                    frontier.append(child)
                    num_explored += 1
                else:
                    swapIfBetter(frontier, child)

    return None

def costo_longitud_random(grafo):
    for e in nx.edges(grafo):
        costo = rnd.randint(1,100) 
        longitud = rnd.randint(1,100)
        (u, v) = e
        grafo.edge[u][v]['longitud'] = longitud
        grafo.edge[u][v]['costo'] = costo

def print_output(graph, x):
	nodes_out = []
	edges_out = []

	edges = nx.edges(graph)
	for edge in edges:
		R = graph.get_edge_data(edge[0], edge[1])['weight']     # resistance between 2 nodes
		
		U = abs(x[edge[0]] - x[edge[1]]) 	# calculate voltage as potential difference
		
		if R == 0:
			I = 0 		# let's assume so
		else:
			I = float(U) / R 	# from Ohm's law
			
		edges_out.append({'from': edge[0], 'to': edge[1], 'value': I, 'label': R})

	nodes = nx.nodes(graph)
	for node in nodes:
		nodes_out.append({'id': node, 'label': str(node)})

	f = open('data.jsonp', 'w')

	f.write("nodes = " + str(nodes_out) + ";\n")

	f.write("edges = " + str(edges_out) + ";")

	f.close()

 def dagToFile(self,dag):
     #file format:
     # (Tasks): id req act procs(always 1))
     # (Edges): e id1 id2
     # Keep ids contiguous, so ignore the given job ID
     # The ids will also be output as negative values.
     #MakeContiguous makes ids starting at 0, but evertthing is incremented
     #before output. Ie tasks will have ids -1, -2, -3. . . 
     
     #The file name will be the given file base, followed by _p
     #and then its current number, in text file format.
     #i.e. example_p0.txt
     name = self.base + "_p" + str(self.permNo) + ".txt"
     self.permNo += 1
     f = open(name,'w')
     #Make the nodes contiguous for ease of use later.
     nodes = self.makeContiguous(dag)
     edges = nx.edges(dag)
     string = ''
     #Writing out each string to the file.
     for n in nodes:
         string = "T -" + str(n.job_id+1) + " " + str(n.requested_time) + " " + str(n.actual_time) + " 1\n"
         f.write(string)
     for e in edges:
         string = "E -" + str(e[0].job_id+1) + " -" + str(e[1].job_id+1) + "\n"
         f.write(string)
     f.close()

def random_pairs(G, n=100000, frac=0.1, saving=True):
    """ Select a training set of n send/receive pairs, with frac
    of them representing actual transactions.  Calculate stats for
    each pair using the get_features() helper.  For those send/receive
    pairs that represent actual transactions in the training data, remove
    the link from the graph before calculating the features to simulate
    transaction prediction. """
    # initialize numpy arrays for holding features
    features = np.empty((n, n_features), dtype=int)
    mask = np.empty(n, dtype=bool)

    # Grab edges and nodes
    edges_list = nx.edges(G)
    np.random.shuffle(edges_list)
    nodes_list = nx.nodes(G)

    # number of real transactions to consider
    n_true = int(n*frac)

    # pick random transacting pairs and calculate features w/o transaction
    for i in range(n_true):
        # output progress
        prog = 100*(i+1)/n
        print('Considering random pairs: %.1f%% complete\r' % prog, end='')

        # set mask to true
        mask[i] = True
        # Pick pair from list of transactions
        (snd, rcv) = edges_list[i]
        # Save edge weight and remove from graph
        n_trans = G[snd][rcv]['trans']
        G.remove_edge(snd, rcv)
        # get features
        features[i, :] = get_features(G, snd, rcv)
        # re-add link
        G.add_edge(snd, rcv, trans=n_trans)

    # Calculate stats for unconnected nodes
    for i in range(n_true, n):
        # output progress
        prog = 100*(i+1)/n
        print('Considering random pairs: %.1f%% complete\r' % prog, end='')

        # set mask to false
        mask[i] = False
        # Pick two addresses and ensure they are unconnected
        snd, rcv = np.random.choice(nodes_list, 2)
        while G.has_edge(snd, rcv):
            snd, rcv = np.random.choice(nodes_list, 2)
        # get features
        features[i, :] = get_features(G, snd, rcv)

    # save to csv file
    if saving:
        feats_and_mask = np.hstack(features, mask.astype(int))
        np.savetxt('random_pairs.txt', feats_and_mask, delimiter=',')

    print() # end line

    return features, mask