def test_dijkstra_predecessor(self):
        G = nx.path_graph(4)
        assert_equal(
            nx.dijkstra_predecessor_and_distance(G, 0), ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})
        )
        G = nx.grid_2d_graph(2, 2)
        pred, dist = nx.dijkstra_predecessor_and_distance(G, (0, 0))
        assert_equal(
            sorted(pred.items()), [((0, 0), []), ((0, 1), [(0, 0)]), ((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])]
        )
        assert_equal(sorted(dist.items()), [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])

        XG = nx.DiGraph()
        XG.add_weighted_edges_from(
            [
                ("s", "u", 10),
                ("s", "x", 5),
                ("u", "v", 1),
                ("u", "x", 2),
                ("v", "y", 1),
                ("x", "u", 3),
                ("x", "v", 5),
                ("x", "y", 2),
                ("y", "s", 7),
                ("y", "v", 6),
            ]
        )
        (P, D) = nx.dijkstra_predecessor_and_distance(XG, "s")
        assert_equal(P["v"], ["u"])
        assert_equal(D["v"], 9)

 def test_dijkstra_predecessor3(self):
     XG = nx.DiGraph()
     XG.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5),
                                 ('u', 'v', 1), ('u', 'x', 2),
                                 ('v', 'y', 1), ('x', 'u', 3),
                                 ('x', 'v', 5), ('x', 'y', 2),
                                 ('y', 's', 7), ('y', 'v', 6)])
     (P, D) = nx.dijkstra_predecessor_and_distance(XG, 's')
     assert_equal(P['v'], ['u'])
     assert_equal(D['v'], 9)
     (P, D) = nx.dijkstra_predecessor_and_distance(XG, 's', cutoff=8)
     assert_false('v' in D)

 def test_dijkstra_pred_distance_multigraph(self):
     G = nx.MultiGraph()
     G.add_edge("a", "b", key="short", foo=5, weight=100)
     G.add_edge("a", "b", key="long", bar=1, weight=110)
     p, d = nx.dijkstra_predecessor_and_distance(G, "a")
     assert_equal(p, {"a": [], "b": ["a"]})
     assert_equal(d, {"a": 0, "b": 100})

 def test_dijkstra_pred_distance_multigraph(self):
     G = nx.MultiGraph()
     G.add_edge('a', 'b', key='short',foo=5, weight=100)
     G.add_edge('a', 'b', key='long',bar=1, weight=110)
     p,d= nx.dijkstra_predecessor_and_distance(G, 'a')
     assert_equal(p,{'a': [], 'b': ['a']})
     assert_equal(d,{'a': 0, 'b': 100})

def dijkstra_all_shortest_paths(G, source, target, weight=None):
    ''' This function is the networkX's implementation of the "all-shortest-paths-problem" algorithm
        and is used as ground truth for our implementation. It uses a modified version of the 
        dijkstra algorithm that compute  the shortest path length and predecessors 
        on shortest paths.'''
        
    if weight is not None:
        pred,dist = nx.dijkstra_predecessor_and_distance(G,source,weight=weight)
    else:
        pred = nx.predecessor(G,source)
    if target not in pred:
        raise nx.NetworkXNoPath()
    stack = [[target,0]]
    top = 0
    while top >= 0:
        node,i = stack[top]
        if node == source:
            yield [p for p,n in reversed(stack[:top+1])]
        if len(pred[node]) > i:
            top += 1
            if top == len(stack):
                stack.append([pred[node][i],0])
            else:
                stack[top] = [pred[node][i],0]
        else:
            stack[top-1][1] += 1
            top -= 1

def explore_shortestpath(G,K):
    cx,cy = position(entiers=True)
    _ , dist = nx.dijkstra_predecessor_and_distance( G,(cx,cy) )
    dist = {ij:dist[ij] for ij in dist if ij not in K}
    if dist:
        closest, _ = min(dist.items(), key=itemgetter(1))
        p = nx.shortest_path(G,(cx,cy),closest,weight='weight')
        suivre_chemin(p,aller)

def dijkstra_plan_networkX(product, beta=10):
	# requires a full construct of product automaton
	start = time.time()
	runs = {}
	loop = {}
	# minimal circles
	for prod_target in product.graph['accept']:
                #print 'prod_target', prod_target
                # accepting state in self-loop
                if prod_target in product.predecessors(prod_target):
                        loop[prod_target] = (product.edges[prod_target,prod_target]["weight"], [prod_target, prod_target])
                        continue
                else:
                        cycle = {}
                        loop_pre, loop_dist = dijkstra_predecessor_and_distance(product, prod_target)
                        for target_pred in product.predecessors(prod_target):
                                if target_pred in loop_dist:
                                        cycle[target_pred] = product.edges[target_pred,prod_target]["weight"] + loop_dist[target_pred]
                        if cycle:
                                opti_pred = min(cycle, key = cycle.get)
                                suffix = compute_path_from_pre(loop_pre, opti_pred)
                                loop[prod_target] = (cycle[opti_pred], suffix)
	# shortest line
	for prod_init in product.graph['initial']:
                line = {}
		line_pre, line_dist = dijkstra_predecessor_and_distance(product, prod_init)
		for target in loop.iterkeys():
			if target in line_dist:
				line[target] = line_dist[target]+beta*loop[target][0]
		if line:
			opti_targ = min(line, key = line.get)
			prefix = compute_path_from_pre(line_pre, opti_targ)
			precost = line_dist[opti_targ]
			runs[(prod_init, opti_targ)] = (prefix, precost, loop[opti_targ][1], loop[opti_targ][0])
	# best combination
	if runs:
		prefix, precost, suffix, sufcost = min(runs.values(), key = lambda p: p[1] + beta*p[3])
		run = ProdAut_Run(product, prefix, precost, suffix, sufcost, precost+beta*sufcost)
		print '=================='
		print 'Dijkstra_plan_networkX done within %.2fs: precost %.2f, sufcost %.2f' %(time.time()-start, precost, sufcost)
		return run, time.time()-start
		#print '\n==================\n'
	print '=================='        
	print 'No accepting run found in optimal planning!'
        return None, None

 def test_dijkstra_predecessor2(self):
     # 4-cycle
     G = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 0)])
     pred, dist = nx.dijkstra_predecessor_and_distance(G, (0))
     assert_equal(pred[0], [])
     assert_equal(pred[1], [0])
     assert_true(pred[2] in [[1, 3], [3, 1]])
     assert_equal(pred[3], [0])
     assert_equal(dist, {0: 0, 1: 1, 2: 2, 3: 1})

    def test_dijkstra_predecessor(self):
        G=nx.path_graph(4)
        assert_equal(nx.dijkstra_predecessor_and_distance(G,0),
                     ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3}))
        G=nx.grid_2d_graph(2,2)
        pred,dist=nx.dijkstra_predecessor_and_distance(G,(0,0))
        assert_equal(sorted(pred.items()),
                     [((0, 0), []), ((0, 1), [(0, 0)]), 
                      ((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])])
        assert_equal(sorted(dist.items()),
                     [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])

        XG=nx.DiGraph()
        XG.add_weighted_edges_from([('s','u',10) ,('s','x',5) ,
                                    ('u','v',1) ,('u','x',2) ,
                                    ('v','y',1) ,('x','u',3) ,
                                    ('x','v',5) ,('x','y',2) ,
                                    ('y','s',7) ,('y','v',6)])
        (P,D)= nx.dijkstra_predecessor_and_distance(XG,'s')
        assert_equal(P['v'],['u'])
        assert_equal(D['v'],9)

def test_dijkstra_all_digraph(testgraph):
    """
    Testing dijkstra_all function for directed graphs.
    """

    a, b = testgraph[2:]
    s = randint(0, 99)
    nx_dijk =  nx.dijkstra_predecessor_and_distance(a, s)
    nx_dijk = nx_dijk[1]
    sg_dijk = sg.dijkstra.dijkstra_all(b, s, directed = True)
    for i in range(len(nx_dijk)):
        assert sg_dijk[1][i] == nx_dijk[sg_dijk[0][i]]

def _node_betweenness(G, source, cutoff=False, normalized=True, weight=None):
    """Node betweenness_centrality helper:

    See betweenness_centrality for what you probably want.
    This actually computes "load" and not betweenness.
    See https://networkx.lanl.gov/ticket/103

    This calculates the load of each node for paths from a single source.
    (The fraction of number of shortests paths from source that go
    through each node.)

    To get the load for a node you need to do all-pairs shortest paths.

    If weight is not None then use Dijkstra for finding shortest paths.
    """

    # get the predecessor and path length data
    if weight is None:
        (pred, length) = nx.predecessor(G, source, cutoff=cutoff,
                                        return_seen=True)
    else:
        (pred, length) = nx.dijkstra_predecessor_and_distance(G, source,
                                                              cutoff, weight)

    # order the nodes by path length
    onodes = [(l, vert) for (vert, l) in length.items()]
    onodes.sort()
    onodes[:] = [vert for (l, vert) in onodes if l > 0]

    # intialize betweenness
    between = {}.fromkeys(length, 1.0)

    while onodes:
        v = onodes.pop()
        if v in pred:
            num_paths = len(pred[v])  # Discount betweenness if more than
            for x in pred[v]:         # one shortest path.
                if x == source:  # stop if hit source because all remaining v
                    break        # also have pred[v]==[source]
                between[x] += between[v] / float(num_paths)
    #  remove source
    for v in between:
        between[v] -= 1
    # rescale to be between 0 and 1
    if normalized:
        l = len(between)
        if l > 2:
            # scale by 1/the number of possible paths
            scale = 1.0 / float((l - 1) * (l - 2))
            for v in between:
                between[v] *= scale
    return between

def all_shortest_paths(G, source, target, weight=None):
    if weight is not None:
        pred,dist = nx.dijkstra_predecessor_and_distance(G,source,weight=weight)
    else:
        pred = nx.predecessor(G,source)
    if target not in pred:
        raise nx.NetworkXNoPath()
    stack = [[target,0]]
    top = 0
    while top >= 0:
        node,i = stack[top]
        if node == source:
            yield [p for p,n in reversed(stack[:top+1])]
        if len(pred[node]) > i:
            top += 1
            if top == len(stack):
                stack.append([pred[node][i],0])
            else:
                stack[top] = [pred[node][i],0]
        else:
            stack[top-1][1] += 1
            top -= 1

def all_shortest_paths(G, source, target, weight=None):
    """Compute all shortest paths in the graph.

    Parameters
    ----------
    G : NetworkX graph

    source : node
       Starting node for path.

    target : node
       Ending node for path.

    weight : None or string, optional (default = None)
       If None, every edge has weight/distance/cost 1.
       If a string, use this edge attribute as the edge weight.
       Any edge attribute not present defaults to 1.

    Returns
    -------
    paths: generator of lists
        A generator of all paths between source and target.

    Examples
    --------
    >>> G=nx.Graph()
    >>> G.add_path([0,1,2])
    >>> G.add_path([0,10,2])
    >>> print([p for p in nx.all_shortest_paths(G,source=0,target=2)])
    [[0, 1, 2], [0, 10, 2]]

    Notes
    -----
    There may be many shortest paths between the source and target.

    See Also
    --------
    shortest_path()
    single_source_shortest_path()
    all_pairs_shortest_path()
    """
    if weight is not None:
        pred,dist = nx.dijkstra_predecessor_and_distance(G,source,weight=weight)
    else:
        pred = nx.predecessor(G,source)
    if target not in pred:
        raise nx.NetworkXNoPath()
    stack = [[target,0]]
    top = 0
    while top >= 0:
        node,i = stack[top]
        if node == source:
          yield [p for p,n in reversed(stack[:top+1])]
        if len(pred[node]) > i:
            top += 1
            if top == len(stack):
                stack.append([pred[node][i],0])
            else:
                stack[top] = [pred[node][i],0]
        else:
            stack[top-1][1] += 1
            top -= 1

 def test_dijkstra_predecessor1(self):
     G = nx.path_graph(4)
     assert_equal(nx.dijkstra_predecessor_and_distance(G, 0),
                  ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3}))

	def dijkstra_plan_networkX(self, beta=10):
		# requires a full construct of product automaton
		start = time.time()
		runs = {}
		loop = {}

		# minimal circles
		for prod_target in self.graph['accept']:
			cycle = {}
			loop_pre, loop_dist = nx.dijkstra_predecessor_and_distance(self, prod_target)
			#print "\nTEST",prod_target
			for target_pred in self.predecessors_iter(prod_target):
				if target_pred in loop_dist:
					#print target_pred, prod_target
					cycle[target_pred] = self.edge[target_pred][prod_target]["weight"] + loop_dist[target_pred]
			if cycle:
				opti_pred = min(cycle, key = cycle.get)
				suffix = compute_path_from_pre(loop_pre, opti_pred)
				#print opti_pred,prod_target,suffix
				loop[prod_target] = (cycle[opti_pred], suffix)

		# print "loops"
		# for p in loop.keys():
		# 	print p,"\t>>",loop[p]
		# shortest line
		for prod_init in self.graph['initial']:
			line = {}
			line_pre, line_dist = nx.dijkstra_predecessor_and_distance(self, prod_init)

			# print
			# print prod_init
			# print "line_dist"
			# for l,m in line_dist.items():
			# 	print l,m

			# print "line_pre"
			# for l,m in line_pre.items():
			# 	print l,m
			# print "loop"
			# for n in loop.iterkeys():
			# 	print n
			# print "\n<<<<<<<<<<<<"
			for target in loop.iterkeys():
				if target in line_dist.iterkeys():
					line[target] = line_dist[target]+beta*loop[target][0]
					# print prod_init,target,line[target]
			# print "<<<<<<<<<<<<\n"
			if line:
				opti_targ = min(line, key = line.get)
				prefix = compute_path_from_pre(line_pre, opti_targ)
				precost = line_dist[opti_targ]
				runs[(prod_init, opti_targ)] = (prefix, precost, loop[opti_targ][1], loop[opti_targ][0])
				# print prod_init,">>",opti_targ, ">>",loop[opti_targ][1]

		# print "Runs\n...................................."
		# for r,p in runs.items():
		# 	print
		# 	print r
		# 	print p
		# print "...................................."
		# best combination
		if runs:
			prefix, precost, suffix, sufcost = min(runs.values(), key = lambda p: p[1] + beta*p[3])
			#print '\n==================\n'
			return prefix, precost, suffix, sufcost
			#print '\n==================\n'
		print 'no accepting run found in optimal planning!'