def test_weight_function(self):
        """Tests that a callable weight is interpreted as a weight
        function instead of an edge attribute.

        """
        # Create a triangle in which the edge from node 0 to node 2 has
        # a large weight and the other two edges have a small weight.
        G = nx.complete_graph(3)
        G.adj[0][2]['weight'] = 10
        G.adj[0][1]['weight'] = 1
        G.adj[1][2]['weight'] = 1
        # The weight function will take the multiplicative inverse of
        # the weights on the edges. This way, weights that were large
        # before now become small and vice versa.

        def weight(u, v, d): return 1 / d['weight']
        # The shortest path from 0 to 2 using the actual weights on the
        # edges should be [0, 1, 2].
        distance, path = nx.single_source_dijkstra(G, 0, 2)
        assert_equal(distance, 2)
        assert_equal(path, [0, 1, 2])
        # However, with the above weight function, the shortest path
        # should be [0, 2], since that has a very small weight.
        distance, path = nx.single_source_dijkstra(G, 0, 2, weight=weight)
        assert_equal(distance, 1 / 10)
        assert_equal(path, [0, 2])

def ego_graph(G,n,radius=1,center=True,undirected=False,distance=None):
    """Returns induced subgraph of neighbors centered at node n within
    a given radius.
    
    Parameters
    ----------
    G : nxgraph
      A NetworkX Graph or DiGraph

    n : node 
      A single node 

    radius : number, optional
      Include all neighbors of distance<=radius from n.
      
    center : bool, optional
      If False, do not include center node in nxgraph

    undirected : bool, optional      
      If True use both in- and out-neighbors of directed graphs.

    distance : key, optional      
      Use specified edge data key as distance.  For example, setting
      distance='weight' will use the edge weight to measure the
      distance from the node n.

    Notes
    -----
    For directed graphs D this produces the "out" neighborhood
    or successors.  If you want the neighborhood of predecessors
    first reverse the nxgraph with D.reverse().  If you want both
    directions use the keyword argument undirected=True.

    Node, edge, and nxgraph attributes are copied to the returned subgraph.
    """
    if undirected:
        if distance is not None:
            sp,_=nx.single_source_dijkstra(G.to_undirected(),
                                           n,cutoff=radius,
                                           weight=distance)
        else:
            sp=nx.single_source_shortest_path_length(G.to_undirected(),
                                                     n,cutoff=radius)
    else:
        if distance is not None:
            sp,_=nx.single_source_dijkstra(G,
                                           n,cutoff=radius,
                                           weight=distance)
        else:
            sp=nx.single_source_shortest_path_length(G,n,cutoff=radius)

    H=G.subgraph(sp).copy()
    if not center:
        H.remove_node(n)
    return  H

 def shortest_path_tree(self, node, search_type='time', cutoff=None):
     if node in self.graph_time.nodes():
         if search_type == 'distance':
             dist, path = networkx.single_source_dijkstra(self.graph_dist, node, cutoff=cutoff)
         elif search_type == 'time':
             dist, path = networkx.single_source_dijkstra(self.graph_time, node, cutoff=cutoff)
         else:
             print 'invalid search type; valid values for variable - distance or time'
             return None
     else:
         print 'Source node not found in the graph'
         return None
     return dist, path

def main():
    '''
    This is the main function
    http://networkx.lanl.gov/reference/algorithms.operators.html
    '''    
    # Get distance matrices
    walking_times = read_weights_from_file(walking_time_filename)  
    shuttle_times = read_weights_from_file(shuttle_time_filename)
    shuttle_connection_times = read_weights_from_file(shuttle_connection_time_filename)
    outdoorness_matrix = read_weights_from_file(outdoorness_filename)
    #print outdoorness_matrix
    
    # Add penalties
    shuttle_connection_times = apply_penalty(shuttle_connection_times, shuttle_penalty/2, 'add') # /2 because we get in and out the shuttle, so we don't want to have a double penalty
    walking_times = apply_penalty(walking_times, walking_penalty , 'multiply') 
    walking_times = apply_outdoor_penalty(walking_times, outdoorness_matrix, outdoorness_penalty)
    
    # Create subgraphs
    walking_graph = nx.DiGraph(data=walking_times)
    #print G.edges(data=True)
    walking_graph = nx.relabel_nodes(walking_graph,convert_list_to_dict(read_node_labels(walking_time_filename)))    
    print 'walking_graph', walking_graph.edges(data=True)
    
    shuttle_graph = nx.DiGraph(data=shuttle_times)
    shuttle_graph = nx.relabel_nodes(shuttle_graph,convert_list_to_dict(read_node_labels(shuttle_time_filename)))
    print 'shuttle_graph', shuttle_graph.edges(data=True)
    
    shuttle_connection_graph = nx.DiGraph(data=shuttle_connection_times)
    shuttle_connection_graph = nx.relabel_nodes(shuttle_connection_graph,convert_list_to_dict(read_node_labels(shuttle_connection_time_filename)))
    print 'shuttle_connection_graph', shuttle_connection_graph.edges(data=True)
    
    # Create main graph
    main_graph = nx.compose(walking_graph, shuttle_graph)
    print 'main_graph', main_graph.edges(data=True)    
    main_graph = nx.compose(main_graph, shuttle_connection_graph)
    print 'main_graph', main_graph.edges(data=True)
    
    # Compute the shortest paths and path lengths between nodes in the graph.
    # http://networkx.lanl.gov/reference/algorithms.shortest_paths.html
    compute_shortest_path(main_graph, '32', 'NW86')
    compute_shortest_path(main_graph, 'W7', 'W20')
    compute_shortest_path(main_graph, '50', '35')
    #print nx.dijkstra_predecessor_and_distance(main_graph, 'NW86')
    
    # Compute shortest paths and lengths in a weighted graph G. TODO: Return farthest region.
    print nx.single_source_dijkstra(main_graph, '32', 'NW86')
    
    # Compute KSP (k-shortest paths) using https://github.com/Pent00/YenKSP
    yenksp_digraph = convert_nx_digraph_into_yenksp_digraph(main_graph)
    print ksp_yen(yenksp_digraph, 'NW86', '32', 2)

def topk_naive2(G, s, R, K):
    """
    finds all business in the region and returns an iterator of K shortest paths
    find shortest path to all reachable nodes from source by Disjktra's
    return paths and lengths for filtered nodes in the region by R-Tree
    :param G: NetworkX Graph instance
    :param s: Source vertex's ID as a string or number that can be found in G
    :param R: Region of interest as list of co-ordinates [nelat, nelong, swlat, swlong]
    :param K: Number of shortest paths to compute
    :return: Iterator of tuples (distance from s, path from s)
    """
    # start = time.time()
    # print '\nStarted Algorithm at %s' % (start,)
    biz = business_in_loc(R[0], R[1], R[2], R[3])
    # print 'After %ss: Found %s businesses in the region %s' % (time.time() - start, len(biz), R)
    length, path = nx.single_source_dijkstra(G, s)
    res = []
    for b in biz:
        b = BUSINESS_NODE_PREFIX + b
        try:
            res.append((length[b], path[b], b))
        except KeyError:
            # This business is not reachable from s
            res.append((float("inf"), [], b))
            # print 'After %ss: Found shortest path from %s to %s' % (time.time() - start, s, b)
    res.sort()
    return res[:K]

def mst_of_g(g,terminals,verbose=False,weighted=True,cutoff=7,return_gL=False,bidir=False):
	STARTTIME=time.time()
	if verbose:
		logger.info("Starting MST construction")
		sys.stdout.flush()

	STARTTIME=time.time()
	gLedges=[]
	shortest_network=model.AnnotatedGraph()

	for i in range(len(terminals)):
		src=terminals[i]
		if src not in g:
			if verbose:
				logger.info("Node %s not in g"%(src))
			continue
		if weighted:
			costs,paths=nx.single_source_dijkstra(g, src, weight='weight',cutoff=cutoff)
		else:
			paths=nx.single_source_shortest_path(g,src,cutoff=cutoff)
			costs=dict([(k,len(v)) for k,v in paths.items()])

		if bidir:
			span=range(len(terminals))
		else:
			span=range(i+1,len(terminals))
		for j in span:
			if j==i:
				continue
			tgt=terminals[j]
			if tgt not in paths:
				if verbose:
					logger.info("no paths between %s and %s"%(src,tgt))
				continue
			shortest_network.add_path(paths[tgt])
			gLedges.append((src,tgt,{'weight':costs[tgt],'path':paths[tgt]}))
		if verbose:
			logger.info("Done %s. Still %d to go"%(src,len(terminals)-i))
			sys.stdout.flush()			
	if verbose:
		logger.info("Computed Metric closure in %f seconds"%(time.time() - STARTTIME))
		STARTTIME=time.time()
		sys.stdout.flush()			
	gL=nx.Graph()
	gL.add_edges_from(gLedges)
	# Min spanning Tree
	tL=nx.minimum_spanning_tree(gL)
	if verbose:
		logger.info("Computed Min spanning tree in %f seconds"%(time.time() - STARTTIME))
		STARTTIME=time.time()
		sys.stdout.flush()	

	mst=model.AnnotatedGraph()
	for e in tL.edges(data=True):
		mst.add_path(e[2]["path"])
	copy_attributes_from_g(mst,g)
	if return_gL:
		return mst,gL,shortest_network
	else:
		return mst

def prepare(neighbours, costs, benefits, S, C, handpicked_targets=None):
    # return moves, visitations, cars, score
    if handpicked_targets is None:
        return {i: [S] for i in xrange(C)}, set(), sort_cars([car_type(i, S, S, 0, 0) for i in xrange(C)]), 0

    score = 0

    G = nx.DiGraph()
    for (fr, tos) in neighbours.iteritems():
        G.add_node(fr)
        for to in tos:
            G.add_edge(fr, to, weight=costs[(fr, to)])

    distances, shortest_paths =  nx.single_source_dijkstra(G, S)
    paths = {target: (distances[target], shortest_paths[target]) for target in handpicked_targets}
    cars = []
    visitations = set()
    moves = {}
    for (i, (target, (dist, path))) in enumerate(paths.items()):
        assert target == path[-1]
        cars.append(car_type(i, path[-2], path[-1],  None, dist))
        for (k, l) in zip(path[:-1], path[1:]):
            if (k, l) not in visitations and (l, k) not in visitations:
                score += benefits[(k, l)]
            visitations.add((k, l))
            visitations.add((l, k))
        moves[i] = path

    return moves, visitations, cars, score

    def path_to(self, source, target):
        """Return distance, path.

        path[target]
        distance[target]
        """
        return nx.single_source_dijkstra(self.graph, source, target)

def connect_shortest_v3(weigthed_graph,nodes,weighted=True,cutoff=None,verbose=False):
	STARTTIME=time.time()
	if verbose:
		print "Starting SHOV3 construction"
		sys.stdout.flush()

	STARTTIME=time.time()

	res=nx.Graph()
	for i in range(len(nodes)):
		src=nodes[i]
		if src not in weigthed_graph:
			continue
		if weighted:
			costs,spaths=nx.single_source_dijkstra(weigthed_graph, src, weight='weight',cutoff=cutoff)
		else:
			spaths=nx.single_source_shortest_path(weigthed_graph, src,cutoff=cutoff)
		for j in range(i+1, len(nodes)):
			t=nodes[j]
			if t not in spaths:
				continue
			if cutoff and (len(spaths[t])>cutoff):
				continue
			res.add_path(spaths[t])
		if verbose:
			print "Done",src,"to go:",len(nodes)-i
			sys.stdout.flush()			
	if verbose:
		print "Computed SHOV3,",time.time() - STARTTIME,"seconds"
		STARTTIME=time.time()
		sys.stdout.flush()	
	return res

def yen_ksp(G, src, tgt, top_K):
    from copy import deepcopy

    def getWeight(p, w=0):
        for i in range(len(p) - 1):
            w += G[p[i]][p[i + 1]]['weight']
        return w

    _cost, _path = nx.single_source_dijkstra(G, src, tgt)
    A = [_path[tgt]]
    costs = [_cost[tgt]]
    B = PriorityQueue()

    for k in range(1, top_K):
        _G = deepcopy(G)
        for i in range(len(A[k - 1]) - 1):
            spurNode = A[k - 1][i]
            rootPath = A[k - 1][:i]
            for path in A:
                if A[k - 1][:i + 1] == path[:i + 1] and _G.has_edge(path[i], path[i + 1]):
                    _G.remove_edge(path[i], path[i + 1])

            if len(rootPath) > 0 and spurNode != tgt:
                extra_edges = _G.edges(rootPath[len(rootPath) - 1])
                for ed in extra_edges:
                    _G.remove_edge(ed[0], ed[1])

            try:
                spurPathCost, spurPath = nx.single_source_dijkstra(_G, spurNode, tgt)
                spurPath = spurPath[tgt]
            except Exception as e:
                spurPath = []

            if len(spurPath) > 0:
                totalPath = rootPath + spurPath
                B.put((getWeight(totalPath), totalPath))
        if B.empty():
            break
        while not B.empty():
            cost, path = B.get()
            if path not in A:
                A.append(path)
                costs.append(cost)
                break
    return A, costs

def sampling(G,cent,hop,cover):
	
	G2 = share.vincity(G,cent,hop)
	sp = nx.single_source_dijkstra(G2,cent)
	for path in sp[1].values():
		if len(path) >= hop:
			if len(set(path) & set(cover))==0:
				return True
	return False

def diameter_dic(graph):
    ds = {}
    for start_nodes in graph:
        distance_dic, path_dic = nx.single_source_dijkstra(graph,start_nodes)
        far_node = max(distance_dic, key=distance_dic.get) #Farthest Node
        ds[start_nodes] = [far_node]
        dis_from_far_node = distance_dic[far_node]
        ds[start_nodes].append(dis_from_far_node)

    return ds

    def get_Rel_one(self,ipt,tp,N,cut=6.0):
        if N>= len( nx.node_connected_component(self.G, ipt) ):
            N=len( nx.node_connected_component(self.G, ipt) )

        T2L,T2P=nx.single_source_dijkstra(self.G,ipt,cutoff=cut,weight=tp)
        count=len(T2L.keys())

        while count<N:
            cut=cut+1.0
            T2L,T2P=nx.single_source_dijkstra(self.G,ipt,cutoff=cut,weight=tp)
            count=len(T2L.keys())

        sorted_T=sorted(T2L.keys(),key=T2L.get)[:N]
        Rel=[]
        for t in sorted_T:
            Rel.append((t,[T2L[t],T2P[t]]))
        Rel=collections.OrderedDict(Rel)

        return Rel

    def test_dijkstra(self):
        (D,P)= nx.single_source_dijkstra(self.XG,'s')
        assert_equal(P['v'], ['s', 'x', 'u', 'v'])
        assert_equal(D['v'],9)

        assert_equal(nx.single_source_dijkstra_path(self.XG,'s')['v'], 
                     ['s', 'x', 'u', 'v'])
        assert_equal(nx.single_source_dijkstra_path_length(self.XG,'s')['v'],9)
        
        assert_equal(nx.single_source_dijkstra(self.XG,'s')[1]['v'],
                     ['s', 'x', 'u', 'v'])

        assert_equal(nx.single_source_dijkstra_path(self.MXG,'s')['v'],
                     ['s', 'x', 'u', 'v'])

        GG=self.XG.to_undirected()
        (D,P)= nx.single_source_dijkstra(GG,'s')
        assert_equal(P['v'] , ['s', 'x', 'u', 'v'])
        assert_equal(D['v'],8)     # uses lower weight of 2 on u<->x edge
        assert_equal(nx.dijkstra_path(GG,'s','v'), ['s', 'x', 'u', 'v'])
        assert_equal(nx.dijkstra_path_length(GG,'s','v'),8)

        assert_equal(nx.dijkstra_path(self.XG2,1,3), [1, 4, 5, 6, 3])
        assert_equal(nx.dijkstra_path(self.XG3,0,3), [0, 1, 2, 3])
        assert_equal(nx.dijkstra_path_length(self.XG3,0,3),15)
        assert_equal(nx.dijkstra_path(self.XG4,0,2), [0, 1, 2])
        assert_equal(nx.dijkstra_path_length(self.XG4,0,2), 4)
        assert_equal(nx.dijkstra_path(self.MXG4,0,2), [0, 1, 2])

        assert_equal(nx.single_source_dijkstra(self.G,'s','v')[1]['v'],
                     ['s', 'u', 'v'])
        assert_equal(nx.single_source_dijkstra(self.G,'s')[1]['v'],
                     ['s', 'u', 'v'])

        assert_equal(nx.dijkstra_path(self.G,'s','v'), ['s', 'u', 'v'])
        assert_equal(nx.dijkstra_path_length(self.G,'s','v'), 2)

        # NetworkXError: node s not reachable from moon
        assert_raises(nx.NetworkXError,nx.dijkstra_path,self.G,'s','moon')
        assert_raises(nx.NetworkXError,nx.dijkstra_path_length,self.G,'s','moon')

        assert_equal(nx.dijkstra_path(self.cycle,0,3),[0, 1, 2, 3])
        assert_equal(nx.dijkstra_path(self.cycle,0,4), [0, 6, 5, 4])

    def build_prism_between_nodes_static(self, g, source, dest, t_s, t_d):
        ti = time.time()
        reached_d, reached_path = networkx.single_source_dijkstra(g, source, cutoff=t_d-t_s)
        #print '\tReached retrieved in', time.time()-ti

        ti = time.time()
        left_d, left_path = networkx.single_source_dijkstra(g, dest, cutoff=t_d-t_s)
        #print '\tLeft retrieved in', time.time()-ti

        #print ('\tDestination(s) reached from source starting at %s within %s analysis intervals is %s' %
        #       (t_s, t_d, len(reached_d)))
        #print ('\tDestination(s) accessed to destination by %s start after %s analysis intervals is %s' %
        #       (t_d, t_s, len(left_d)))

        #print 'cutoff = ', t_d-t_s
        #print 'max_dist = ', max(reached_d.values()), max(left_d.values())
        dests_accessible = {}
        for i in reached_d:
            if i in left_d and ((reached_d[i] + left_d[i]) < t_d - t_s):
                dests_accessible[i] = reached_d[i]

        return dests_accessible

def get_effdist_tree(G, source, cutoff=None, create_using=nx.DiGraph, weight="weight", effdist_key="effdist"):

    T = create_using()
    T.graph["root"] = source
    T.add_node(source)

    length, path = nx.single_source_dijkstra(G, source, cutoff=cutoff, weight=weight)

    for n in path.keys():
        T.add_path(path[n])
        T.node[n][effdist_key] = length[n]

    return T

    def test_dijkstra(self):
        (D, P) = nx.single_source_dijkstra(self.XG, "s")
        assert_equal(P["v"], ["s", "x", "u", "v"])
        assert_equal(D["v"], 9)

        assert_equal(nx.single_source_dijkstra_path(self.XG, "s")["v"], ["s", "x", "u", "v"])
        assert_equal(nx.single_source_dijkstra_path_length(self.XG, "s")["v"], 9)

        assert_equal(nx.single_source_dijkstra(self.XG, "s")[1]["v"], ["s", "x", "u", "v"])

        assert_equal(nx.single_source_dijkstra_path(self.MXG, "s")["v"], ["s", "x", "u", "v"])

        GG = self.XG.to_undirected()
        (D, P) = nx.single_source_dijkstra(GG, "s")
        assert_equal(P["v"], ["s", "x", "u", "v"])
        assert_equal(D["v"], 8)  # uses lower weight of 2 on u<->x edge
        assert_equal(nx.dijkstra_path(GG, "s", "v"), ["s", "x", "u", "v"])
        assert_equal(nx.dijkstra_path_length(GG, "s", "v"), 8)

        assert_equal(nx.dijkstra_path(self.XG2, 1, 3), [1, 4, 5, 6, 3])
        assert_equal(nx.dijkstra_path(self.XG3, 0, 3), [0, 1, 2, 3])
        assert_equal(nx.dijkstra_path_length(self.XG3, 0, 3), 15)
        assert_equal(nx.dijkstra_path(self.XG4, 0, 2), [0, 1, 2])
        assert_equal(nx.dijkstra_path_length(self.XG4, 0, 2), 4)
        assert_equal(nx.dijkstra_path(self.MXG4, 0, 2), [0, 1, 2])

        assert_equal(nx.single_source_dijkstra(self.G, "s", "v")[1]["v"], ["s", "u", "v"])
        assert_equal(nx.single_source_dijkstra(self.G, "s")[1]["v"], ["s", "u", "v"])

        assert_equal(nx.dijkstra_path(self.G, "s", "v"), ["s", "u", "v"])
        assert_equal(nx.dijkstra_path_length(self.G, "s", "v"), 2)

        # NetworkXError: node s not reachable from moon
        assert_raises(nx.NetworkXNoPath, nx.dijkstra_path, self.G, "s", "moon")
        assert_raises(nx.NetworkXNoPath, nx.dijkstra_path_length, self.G, "s", "moon")

        assert_equal(nx.dijkstra_path(self.cycle, 0, 3), [0, 1, 2, 3])
        assert_equal(nx.dijkstra_path(self.cycle, 0, 4), [0, 6, 5, 4])

def mst_of_g(g,terminals,verbose=False,weighted=True):
	STARTTIME=time.time()
	GLOBALTIME=STARTTIME
	if verbose:
		print "Starting MST construction"
		sys.stdout.flush()

	STARTTIME=time.time()
	gLedges=[]
	for i in range(len(terminals)):
		src=terminals[i]
		if src not in g:
			continue
		if weighted:
			costs,paths=nx.single_source_dijkstra(g, src, weight='weight',cutoff=7)
		else:
			paths=nx.single_source_shortest_path(g,src,cutoff=7)
			costs=dict([(k,len(v)) for k,v in paths.items()])

		for j in range(i+1,len(terminals)):
			tgt=terminals[j]
			if tgt not in paths:
				continue
			gLedges.append((src,tgt,{'weight':costs[tgt],'path':paths[tgt]}))
		if verbose:
			print "Done",src,"to go:",len(terminals)-i
			sys.stdout.flush()			
	if verbose:
		print "Computed Metric closure,",time.time() - STARTTIME,"seconds"
		STARTTIME=time.time()
		sys.stdout.flush()			
	gL=nx.Graph()
	gL.add_edges_from(gLedges)
	# Min spanning Tree
	tL=nx.minimum_spanning_tree(gL)
	if verbose:
		print "Computed Min spanning tree,",time.time() - STARTTIME,"seconds"
		STARTTIME=time.time()
		sys.stdout.flush()	

	mst=nx.Graph()
	for e in tL.edges(data=True):
		mst.add_path(e[2]["path"])
	if verbose:
		print "Totla comp time,",time.time() - GLOBALTIME,"seconds"
		sys.stdout.flush()	

	return mst

def main():
    G = nx.DiGraph()  # G eh um grafo direcionado
    # gera o grafo apartir de suas arestas
    G.add_weighted_edges_from([(1,2,2.0),(1,3,1.0),(2,3,3.0),(2,4,3.0),(3,5,1.0),(4,6,2.0),(5,4,2.0),(5,6,5.0)])
    for i in G.edges():
        # print i[0], i[1]
        G[i[0]][i[1]]["color"] = "black"
    # G[1][2]["color"] = "red"
    comprimento, caminho = nx.single_source_dijkstra(G, 1)
    print caminho
    for i in caminho:
        print i, comprimento[i], caminho[i]
        for j in range(1, len(caminho[i])):
            #print caminho[i][j-1], caminho[i][j]
            G[caminho[i][j-1]][caminho[i][j]]["color"] = "red"
    desenhaGrafo(G, "grafo-1c.png")

def main():
    G = nx.DiGraph()  # G eh um grafo direcionado
    # gera o grafo apartir de suas arestas
    G.add_weighted_edges_from([(1,2,20),(1,3,15),(2,1,2),(2,4,10),(2,5,25),(3,2,4),(3,4,25),(3,5,10),(4,6,15),(5,4,10),(5,6,4)])
    for i in G.edges():
        # print i[0], i[1]
        G[i[0]][i[1]]["color"] = "black"
    # G[1][2]["color"] = "red"
    distancia, caminho = nx.single_source_dijkstra(G,1)
    print caminho
    print distancia
    for i in caminho:
        print i, caminho[i]
        for j in range(1, len(caminho[i])):
            #print caminho[i][j-1], caminho[i][j]
            G[caminho[i][j-1]][caminho[i][j]]["color"] = "red"
    desenhaGrafo(G, "grafo-1a.png")