def test_astar_undirected2(self):
     XG3 = nx.Graph()
     edges = [(0, 1, 2), (1, 2, 12), (2, 3, 1), (3, 4, 5), (4, 5, 1),
              (5, 0, 10)]
     XG3.add_weighted_edges_from(edges)
     assert_equal(nx.astar_path(XG3, 0, 3), [0, 1, 2, 3])
     assert_equal(nx.astar_path_length(XG3, 0, 3), 15)

 def test_astar_undirected3(self):
     XG4 = nx.Graph()
     edges = [(0, 1, 2), (1, 2, 2), (2, 3, 1), (3, 4, 1), (4, 5, 1),
              (5, 6, 1), (6, 7, 1), (7, 0, 1)]
     XG4.add_weighted_edges_from(edges)
     assert_equal(nx.astar_path(XG4, 0, 2), [0, 1, 2])
     assert_equal(nx.astar_path_length(XG4, 0, 2), 4)

def total_exit_time(graph, start_points_list, exit_points_list):
    """
    Calculates the total exit time as the longest time it takes any soldier to reach the exit
    Satisfies TB033
    """
    ## Initialize to impossible value
    max_exit_time = -1.0

    for p_i in start_points_list:
        assert p_i in graph, "Specified start point not walkable"
        for p_e in exit_points_list:
            assert p_e in graph, "Specified exit point not walkable"

            try:
                dist_to_exit = nx.astar_path_length(graph,
                                                    source=p_i,
                                                    target=p_e,
                                                    weight='weight',
                                                    heuristic=a_star_heuristic)
                max_exit_time = max(max_exit_time, dist_to_exit)
            except (KeyError, nx.NetworkXNoPath):
                # If points are in graph but no path exists, log a message
                logging.info("No path found between voxel indices {} and {}".format(p_i, p_e))
                
    if max_exit_time == -1.0:
        raise ValueError("No exit paths were found")
        
    return max_exit_time

def hyperEmbed(g):
    locs = {x: randomPoint() for x in g.nodes()}
    rev_locs = {locs[x]: x for x in locs.keys()}
    MAX_iter = 100
    for i in range(0, MAX_iter):
        print(i)
        overlay = HyperfastDGVH(rev_locs.keys())
        newlocs = {}
        for p in g.nodes():
            ploc = locs[p]
            force = [0.0, 0.0]
            total_hDist = 0.0
            total_realdist = 0.0
            weight = 0.0
            for locq in overlay.nodes():
                q = rev_locs[locq]
                if p == q:
                    continue
                qloc = locs[q]
                dist = hDist(ploc, qloc)
                ideal_dist = nx.astar_path_length(g, p, q) * 0.5
                w = eDist((0, 0), qloc)
                delta_f = (ideal_dist - dist) * 0.1 * (
                    1.0 - float(i) / MAX_iter) * w
                weight += w
                force[0] -= (qloc[0] - ploc[0]) * delta_f
                force[1] -= (qloc[1] - ploc[1]) * delta_f

            force[0] /= weight
            force[1] /= weight
            newlocs[p] = hyperDelta(ploc, force)
        locs = newlocs
        rev_locs = {locs[x]: x for x in locs.keys()}
    print(isGreedy(HyperfastDGVH(rev_locs.keys()), hDist))
    return locs

 def test_astar_w1(self):
     G = nx.DiGraph()
     G.add_edges_from([('s', 'u'), ('s', 'x'), ('u', 'v'), ('u', 'x'),
                       ('v', 'y'), ('x', 'u'), ('x', 'w'), ('w', 'v'),
                       ('x', 'y'), ('y', 's'), ('y', 'v')])
     assert_equal(nx.astar_path(G, 's', 'v'), ['s', 'u', 'v'])
     assert_equal(nx.astar_path_length(G, 's', 'v'), 2)

 def test_astar_undirected(self):
     GG = self.XG.to_undirected()
     # make sure we get lower weight
     # to_undirected might choose either edge with weight 2 or weight 3
     GG['u']['x']['weight'] = 2
     GG['y']['v']['weight'] = 2
     assert_equal(nx.astar_path(GG, 's', 'v'), ['s', 'x', 'u', 'v'])
     assert_equal(nx.astar_path_length(GG, 's', 'v'), 8)

def BA_sp(m, N_range):
    number_of_trials = 100
    #D=1
    myfile = open('BA_shortest_path', 'w')
    myfile.write('N' + '\t' + 'average shortest path'+ '\t'+'std err'+'\n')
    
    for N in N_range:
        sp_list = []
        comparison_sp_list = []
        for trial in range(number_of_trials):
            model = models.barabasi_albert_graph(N,m)
    #        model = models.box_model(D, N)
            G = model[0]
            extremes = model[1]
            #tr_DAG = tr.trans_red(G)
            sp_length = nx.astar_path_length(G, extremes[1], extremes[0])
    #        sp_length = 
     
            sp_list.append(sp_length)
            
            average_in_degree = float(m)*float((N-1))/(float(N))
            comparison_model = oneD_random_comparison(N,average_in_degree)
            comparison_G = comparison_model[0]
            comparison_extremes = comparison_model[1]
            
            if nx.has_path(comparison_G, comparison_extremes[1], comparison_extremes[0]): 
                comparison_sp_length = nx.astar_path_length(comparison_G, comparison_extremes[1], comparison_extremes[0])
#                comparison_sp_length = comparison_sp[2]
            else: comparison_sp_length=0
            
            comparison_sp_list.append(comparison_sp_length)
            
        statistics = stats.list_stats(sp_list)
        sp_av = statistics[3]
        sp_std_err = statistics[0]
        
        comparison_stats = stats.list_stats(comparison_sp_list)
        comparison_sp_av = comparison_stats[3]
        comparison_sp_std_err = comparison_stats[0]
        
        print "done ", N
        myfile.write(str(N) + '\t' + str(sp_av) + '\t' + str(sp_std_err) + '\t' + str(N) + '\t' + str(comparison_sp_av) + '\t' + str(comparison_sp_std_err) + '\n')
        
    return

 def test_astar_undirected2(self):
     XG3=nx.Graph()
     XG3.add_edges_from([ [0,1,{'weight':2}],
                          [1,2,{'weight':12}],
                          [2,3,{'weight':1}],
                          [3,4,{'weight':5}],
                          [4,5,{'weight':1}],
                          [5,0,{'weight':10}] ])
     assert nx.astar_path(XG3,0,3)==[0, 1, 2, 3]
     assert nx.astar_path_length(XG3,0,3)==15

def findMaxScorePath(CandidateNodesList,SelectNodesGraph, i):
	CanPath = []
	for j in CandidateNodesList[i[0]]:
		for k in CandidateNodesList[i[-1]]:
			CanPath.append((nx.astar_path(SelectNodesGraph,j,k),nx.astar_path_length(SelectNodesGraph,j,k)))
	MaxScore = min([j[1] for j in CanPath])
	for j in CanPath:
		if MaxScore==j[1]:
			MaxScorePath = j[0]
	return MaxScorePath

 def closestStation(self, graph, node): #Returns the closest station and the distance from it
     if (len(self.stations) == 0): return 0,999999
     bestDistance = 99999999
     bestStation = self.stations[0]
     for station in self.stations:
         dist = nx.astar_path_length(graph,station,node)
         if (dist == 0): return node, 1
         if (dist < bestDistance):
             bestDistance = dist
             bestStation = station
     return bestStation, bestDistance

 def test_astar_undirected3(self):
     XG4=nx.Graph()
     XG4.add_edges_from([ [0,1,{'weight':2}],
                          [1,2,{'weight':2}],
                          [2,3,{'weight':1}],
                          [3,4,{'weight':1}],
                          [4,5,{'weight':1}],
                          [5,6,{'weight':1}],
                          [6,7,{'weight':1}],
                          [7,0,{'weight':1}] ])
     assert nx.astar_path(XG4,0,2)==[0, 1, 2]
     assert nx.astar_path_length(XG4,0,2)==4

def pathadddistance(patharray,GGG):
    #global allnodedist
    
    for p in patharray:
        nodepeer = zip(p[::1], p[1::1]) #参考高手的代码。将list的元素两两一组，重叠组成tuple。下面也有同样代码，最后的数字是2。
        ttlong = 0 #累加路径长度。
        for np in nodepeer:
            dd = 0 #缓存清零。保证数值方便排障。
            dd = nx.astar_path_length(GGG,np[0],np[1])#各个算法都尝试过了，结果一致。再观察。
            #dd = nx.dijkstra_path_length(GGG,np[0],np[1])
            #dd = allnodedist[np[0]][np[1]] #路径上每2个节点间的最短距离。其实不是最短距离，这个全局变量给点值很疑惑。
            ttlong  += dd #在节点直连字典中查找两点之间的距离，并累加。
            p.insert(p.index(np[1]),dd) #在路径上每两个节点之间插入距离数值。
        p.append(ttlong)
    return patharray

 def test_astar_w1(self):
     G = nx.DiGraph()
     G.add_edges_from(
         [
             ("s", "u"),
             ("s", "x"),
             ("u", "v"),
             ("u", "x"),
             ("v", "y"),
             ("x", "u"),
             ("x", "w"),
             ("w", "v"),
             ("x", "y"),
             ("y", "s"),
             ("y", "v"),
         ]
     )
     assert nx.astar_path(G, "s", "v") == ["s", "u", "v"]
     assert nx.astar_path_length(G, "s", "v") == 2

	def getPairwiseDistanceWithinGraphOfChosenMonkey(self, graph=None, chosenMonkeyIDDict=None):
		"""
		2012.11.27
		"""
		sys.stderr.write("Getting list of pairwise distance of all pairs in graph for %s chosen monkeys ..."%\
						(len(chosenMonkeyIDDict)))
		distance_ls = []
		chosenMonkeyIDList = list(chosenMonkeyIDDict)
		for i in xrange(len(chosenMonkeyIDList)):
			monkey1ID = chosenMonkeyIDList[i]
			for j in xrange(i+1, len(chosenMonkeyIDList)):
				monkey2ID = chosenMonkeyIDList[j]
				try:
					distance = nx.astar_path_length(graph, source=monkey1ID, target=monkey2ID, weight='weight')
				except:
					distance = -5
				distance_ls.append(distance)
				#distance_ls.append(lengthStructure[monkey1ID][monkey2ID])
		sys.stderr.write("%s pairs .\n"%(len(distance_ls)))
		return distance_ls

	def updateNewMonkeyToChosenSetDistanceVector(self, graph=None, oldShortestDistanceVectorData=None, \
												newlyChosenMonkeyID=None, minShortestDistance=0.4):
		"""
		2012.11.26
			supplement to constructNewMonkeyToChosenSetDistanceVector()
		"""
		oldShortestDistanceToChosenSet_monkeyID_ls = oldShortestDistanceVectorData.shortestDistanceToChosenSet_monkeyID_ls
		
		sys.stderr.write("Updating the shortest-distance to chosen set vector (%s elements) because monkeys %s has been added into the chosen set ..."%\
						(len(oldShortestDistanceToChosenSet_monkeyID_ls), newlyChosenMonkeyID))
		
		returnData = PassingData(shortestDistanceToChosenSet_monkeyID_ls = [])
		
		counter = 0
		real_counter = 0
		spanStartPos = 0
		
		monkey2ID = newlyChosenMonkeyID
		for element in oldShortestDistanceToChosenSet_monkeyID_ls:
			shortestDistance, monkey1ID, shortestDistanceToThisChosenMonkey = element[:3]
			if monkey1ID!=monkey2ID:	#skip the chosen monkey
				counter += 1
				#get the shortest path
				#short path in graph, sum all the edge weights, A* star algorithm seems to be much faster (>100%) than default shortest_path.
				#distance = nx.shortest_path_length(graph, source=monkey1ID, target=monkey2ID, weight='weight')
				distance = nx.astar_path_length(graph, source=monkey1ID, target=monkey2ID, weight='weight')
				if distance<shortestDistance:
					shortestDistance = distance
					shortestDistanceToThisChosenMonkey = monkey2ID
					element = (shortestDistance, monkey1ID, shortestDistanceToThisChosenMonkey)
					real_counter += 1
				if shortestDistance>=minShortestDistance:
					returnData.shortestDistanceToChosenSet_monkeyID_ls.append(element)
					spanStartPos += shortestDistance	#increase the distance.
		returnData.totalDistance = spanStartPos
		sys.stderr.write("%s (out of %s) monkeys changed their shortest distance to the chosen set (%s elements). \n\
	total distance to the chosen set is %s.\n"%\
						(real_counter, counter, len(returnData.shortestDistanceToChosenSet_monkeyID_ls), spanStartPos))
		
		return returnData

def simulate_random_walk (G, damping, max_jumps):
    """ Random walk simulation on weighted graph G with damping factor d
        and max_jumps as maximum number of jumps"""

    results = []
    nodes = [] # keep nodes
    current_node = random.randrange(N)
    while not G.has_node(current_node):
        current_node = random.randrange(N)

    j = 0
    while (j < max_jumps):
        previous_node = current_node
        jump_decision = random.uniform(0, 1)

        if jump_decision < damping or G.out_degree(current_node) == 0:
            # make a jump
            current_node = random.randrange(N)
            while not G.has_node(current_node):
                current_node = random.randrange(N)

            j += 1
            try:
                distance = nx.astar_path_length(G, previous_node, \
                               current_node, weight = 'weight')
                # distance intervals 1h traveling
                results.append(distance)
                nodes.append(previous_node)
            except nx.NetworkXNoPath: continue

        else:
            # move to neighbor node
            incident = G.out_edges([current_node], data = False)
            distribution = [ G.get_edge_data(e[0], e[1])['transition'] for e in incident ]
            xk = np.arange(len(incident))
            generator = stats.rv_discrete(values = (xk, distribution))
            current_node = incident[generator.rvs()][1]

    return results, nodes

def stitch(local_graph, global_graph, kd_tree, tolerance, target, rename_string):
    """ stitch local unconstrained graph with global graph,
    as long as the distance to nearest global graph node is within certain 
    tolerance. Requires pre-generated kd-tree for the global graph. """

    path_candidates = []
    for node, d in local_graph.nodes(data=True):
        node_pos = d['pos'] 
        dist, indexes = kd_tree.query([node_pos])
        if dist[0] < tolerance:
            #find astar path to the selected close proximity  node
            #TODO: compute node path here, and save it, extract length like this:
            # path = astar_path(G, source, target, heuristic)
            # length =  sum(G[u][v].get(weight, 1) for u, v in zip(path[:-1], path[1:]))
            path_length = nx.astar_path_length(local_graph, target, node)
            entry_node = indexes[0]

            path_candidates.append((path_length, target, node, entry_node))

    #chose best way to join to global graph
    path_candidates.sort()

    best_candidate = path_candidates[0]
    (path_length, target, node, entry_node) = best_candidate

    astar_path = nx.astar_path(local_graph, target, node)

    h = local_graph.subgraph(astar_path)
    route = h.to_directed()

    # because local_graphs have the same naming, aka (1,2) we have to rename
    # to join properly
    global_graph = nx.union(global_graph, route, rename=(None, rename_string))

    #connect two graphs
    global_graph.add_edge(rename_string + str(node), entry_node)
    global_graph.add_edge( entry_node, rename_string + str(node))

    return global_graph

	def constructNewMonkeyToChosenSetDistanceVector(self, graph=None, preChosenMonkeyIDSet=None, minShortestDistance=0.4):
		"""
		2012.11.26
			each monkey is assigned a probability mass based on its geographic distance to the closest monkey
				in the preChosenMonkeyIDSet.
		"""
		sys.stderr.write("Constructing distance vector from new monkey to %s chosen monkeys (%s total monkeys) ..."%\
						(len(preChosenMonkeyIDSet), len(graph)))
		counter = 0
		real_counter = 0
		
		spanStartPos = 0
		unChosenMonkeyIDSet = set(graph.nodes()) - preChosenMonkeyIDSet
		preChosenAndInGraphMonkeyIDSet = set(graph.nodes()) - unChosenMonkeyIDSet
		
		returnData = PassingData(shortestDistanceToChosenSet_monkeyID_ls = [])
		for monkey1ID in unChosenMonkeyIDSet:
			counter += 1
			shortestDistance = None
			shortestDistanceToThisChosenMonkey = None
			for monkey2ID in preChosenAndInGraphMonkeyIDSet:
				#get the shortest path
				#distance = nx.shortest_path_length(graph, source=monkey1ID, target=monkey2ID, weight='weight')
				distance = nx.astar_path_length(graph, source=monkey1ID, target=monkey2ID, weight='weight')
				#short path in graph, sum all the edge weights
				if shortestDistance is None or distance<shortestDistance:
					shortestDistance = distance
					shortestDistanceToThisChosenMonkey = monkey2ID
			if shortestDistance is not None and shortestDistance>=minShortestDistance:	#ignore monkeys from same sites
				returnData.shortestDistanceToChosenSet_monkeyID_ls.append((shortestDistance, monkey1ID, shortestDistanceToThisChosenMonkey))
				real_counter += 1
				spanStartPos += shortestDistance	#increase the distance.
		returnData.totalDistance = spanStartPos
		sys.stderr.write("%s (out of %s candidate) monkeys added into candidate vector, total distance to the chosen set is %s.\n"%\
						(real_counter, counter, spanStartPos))
		return returnData

def main82():
    g = g82(matrix)
    N = len(matrix)
    M = len(matrix[0])
    print "(%d) Nodes, (%d) Edges" % (len(g.nodes()), len(g.edges()))
    #print nx.dijkstra_path_length(g, (0,0), (N-1,M-1)) + g.node[(N-1, M-1)].get('value')
    minimum = 1e6
    minimum2 = 1e6
    for r in xrange(N):
        for r1 in xrange(M):
            try:
                source = (r,0)
                destiny = (r1, M-1)
                l = nx.dijkstra_path_length(g, source, destiny)
                l += g.node[destiny].get('value')
                l2 = nx.astar_path_length(g, source, destiny, dist)
                l2 += g.node[destiny].get('value')
                if l < minimum:
                    minimum = l
                if l2 < minimum2:
                    minimum2 = l2
            except:
                continue
    print minimum, minimum2    

 def test_astar_directed(self):
     assert nx.astar_path(self.XG, "s", "v") == ["s", "x", "u", "v"]
     assert nx.astar_path_length(self.XG, "s", "v") == 9