def test_all_pairs_dijkstra_path(self):
        cycle = nx.cycle_graph(7)
        p = dict(nx.all_pairs_dijkstra_path(cycle))
        assert_equal(p[0][3], [0, 1, 2, 3])

        cycle[1][2]['weight'] = 10
        p = dict(nx.all_pairs_dijkstra_path(cycle))
        assert_equal(p[0][3], [0, 6, 5, 4, 3])

def route_remaining_edges_simple(G, T, n2c):
    """The original routing function --- not used now"""
    #for u,v in G.edges_iter():
    #    if T.are_adjacent(n2c[u], n2c[v]):
    #        print 'edge (%d,%d) at %d,%d good' % (u,v,n2c[u], n2c[v])


    if G.number_of_edges() == 0: return []

    H = construct_routing_graph(T, set(n2c.values()))
    SP = nx.all_pairs_dijkstra_path(H)
    SP_len = nx.all_pairs_dijkstra_path_length(H)
    nx.write_edgelist(H, "hex.graph")

    # for every remaining edge
    Routes = []
    for u,v in G.edges_iter():
        c = n2c[u]
        d = n2c[v]
        # find the combination of sides that gives the shortest path
        best = bestp = None
        for s1,s2 in itertools.product(T.hex_sides(),T.hex_sides()):
            source = T.side_name(c,s1)
            target = T.side_name(d,s2)

            if SP_len[source][target] < best or best is None:
                best = SP_len[source][target]
                bestp = SP[source][target]
        #print >>sys.stderr, "Route %d - %d (%g) %s" % (u, v, best, ",".join(bestp)) 
        Routes.append(bestp)
    return Routes

def expand_road_network(road_network, discritization):
    """Discritize a simple road_network
        Takes a simple road network with nodes at features and intersections
        and edges with weights between nodes and add nodes along the edges
    """
    rn_old = road_network
    df = discritization  # nodes per unit weight

    # Find shortest paths and path lengths
    paths = nx.all_pairs_dijkstra_path(rn_old)
    path_lengths = nx.all_pairs_dijkstra_path_length(rn_old)

    # Create new graph
    rn = nx.Graph()
    rn.add_nodes_from(rn_old.nodes(data=True))

    for old_edge in rn_old.edges(data=True):
        beg = old_edge[0]
        end = old_edge[1]
        if int(beg) > int(end):
            beg, end = end, beg

        num_nodes = int(round(old_edge[2]['weight'] * df) - 1)

        old_node_name = beg
        for node in range(num_nodes):
            new_node_name = '{}.{}.{}'.format(beg, end, node)
            if node == num_nodes - 1:
                rn.add_edge(new_node_name, end)
            rn.add_edge(old_node_name, new_node_name)

            old_node_name = new_node_name

    return rn, paths, path_lengths

 def __init__(self, cityMap):
   VRPProblem.__init__(self, cityMap)
   self.src_nodes = {s for s, d in cityMap.passengers}
   print(self.src_nodes)
   self.relevant_nodes = {d for s, d in cityMap.passengers} | self.src_nodes
   print(self.relevant_nodes - self.src_nodes)
   self.short_path = networkx.all_pairs_dijkstra_path(cityMap.g)

    def __init__(self, status):
        
        self.status = status
        
        self.INTERNAL_COST = self.status.INTERNAL_COST
        self.EXTERNAL_COST = self.status.EXTERNAL_COST
        
        self.core = self.status.core
        self.k = self.status.k
        self.h = self.status.h
        
        self.max_delay = self.h * self.INTERNAL_COST + self.EXTERNAL_COST

        if self.status.topo_type == 'tree':
            self.topology = self._create_topology(self.core, self.k, self.h)
        elif self.status.topo_type == 'rocket':
            self.topology = self._parse_rocketfuel_topology()
        
        self.clients = {node: self.topology.node[node] for node in self.topology.node
                        if self.topology.node[node]['type'] == 'leaf'}
        self.pops = {node: self.topology.node[node] for node in self.topology.node
                     if self.topology.node[node]['type'] == 'root'}
        self.routers = {node: self.topology.node[node] for node in self.topology.node
                        if self.topology.node[node]['type'] in ['root', 'intermediate']}        
        
        self.shortest_path = self._symmetrify_paths(nx.all_pairs_dijkstra_path(self.topology))
        self.neighbors2 = {node: self._neighbors_of_neighbors(node) for node in self.topology.node}

def hub_algo(c):
    all_short = networkx.all_pairs_dijkstra_path(c.g)

    clustering_map(c, c.number_of_busses-1)
    central_nodes = [get_subgraph_center(c, i) for i in range(1, c.number_of_busses)]

    central_route = []
    for i in range(len(central_nodes)-1):
        central_route += all_short[central_nodes[i]][central_nodes[i+1]]
    c.set_route(1, central_route)

    for i in range(1, len(central_nodes)+1):
        Gp =  networkx.Graph()
        for v in c.rv:
            for u in c.rv:
                if (v==u) or (c.clusters[u] != i) or (c.clusters[v] != i):
                    continue
                Gp.add_edge(v, u, weight=c.get_route_weight_from_route(all_short[u][v]))

        problem = Problem(Gp)
        best = simple.aStarSearch(problem, unvisited_heuristic)

        new_route = []
        for j in range(len(best)-1):
            new_route += all_short[best[j]][best[j+1]]
        c.set_route(i + 1, new_route)
    return c

def highest_activity_paths(input_network, percentile):
	path_length_thresh = 2

	#print "Calculating shortest paths..."
	shortest_paths = nx.all_pairs_dijkstra_path(input_network)

	#print "Extracting paths with length >=",path_length_thresh,"and corresponding costs into an array..."
	# list of tuples (cost, path)
	# path is a list of nodes
	cost_paths = []
	for src, dest_paths in shortest_paths.items():
		for dest, path in dest_paths.items():
			if (len(path) - 1) >= path_length_thresh:
				cost_paths.append((get_path_cost(input_network, path), path))
	costs = [tup[0] for tup in cost_paths] # this is necessary for the percentile computation
	#print "Got ", len(cost_paths), " shortest paths"

	#print "Sorting paths based on costs..."
	cost_paths_sorted = sorted(cost_paths)

	network_path_cost_thresh = np.percentile(costs, percentile)

	# Get highest activity paths
	highestActivityPaths_network = set()
	for tup in cost_paths_sorted:
		if tup[0] < network_path_cost_thresh:
			highestActivityPaths_network.add(tuple(tup[1]))
		else:
			break
	#print "Got ", len(highestActivityPaths_network), " highest activity paths in network"
	return highestActivityPaths_network

def computeGeoDist(G):
	"""Compute Geographical distances with waypoints"""
	path = nx.all_pairs_dijkstra_path(G)
	outf = open("african-origin-homelands-distances-1.txt", "w")
	for src, src_coordl in source_dict.iteritems():
#		print src, src_coordl
		src_area = src_coordl[0]
		src_coord = src_coordl[1]
		for hm, hm_coordl in hmcoord_dict.iteritems():
			hm_area = hm_coordl[0]
			hm_coord = hm_coordl[1]
			distance = 0
			if src_area != hm_area:
				path_list = path[src_area][hm_area]
				coord_list = []
				coord_list.append(src_coord)
#				distance += getDistance(src_coord,G[src_area][path_list[1]]["coord"])
				for i in range(len(path_list)-1):
					coord_list.append(G[path_list[i]][path_list[i+1]]["coord"])
				coord_list.append(hm_coord)
#				print coord_list				
				for i in range(len(coord_list)-1):
					distance += getDistance(coord_list[i],coord_list[i+1])
			else:
				distance = getDistance(src_coord, hm_coord)
			outf.write(src+"\t"+hm+"\t"+str(distance)+"\n")
			print src, hm, distance

def largearcs_connecting_heuristic( cycles, transport_graph, cost_label='cost' ) :
    APSP = nx.all_pairs_dijkstra_path( transport_graph, weight=cost_label )
    APSPL = nx.all_pairs_dijkstra_path_length( transport_graph, weight=cost_label )
    
    # Step 3(b): Form the inter-node distance from the original edge costs
    # d(ni,nj) = min { c'(u,v) | u \in Ri, v \in Rj }.
    # Associate with (ni,nj) the edge (u,v) yielding minimum cost.
    inter_node_distance = nx.Graph()
    for cycle in cycles :
        u = node()
        u.cycle = cycle     # do we need this?... eh, it's cheap
        inter_node_distance.add_node( u )
        #
        u.enroute, u.balance = cycle_edges( cycle )
        
        # also want to store all nodes visited while *EMPTY*
        u.nodes = set()
        for x,y in u.balance.edges_iter() :
            u.nodes.update( APSP[x][y] )
        #for x,y,key, data in u.graph.edges_iter( keys=True, data=True ) :
            #if not data.get( 'CONNECT_ONLY', False ) : continue
            #u.nodes.update( APSP[x][y] )
            
    NODES = inter_node_distance.nodes()
    for u, v in itertools.combinations( NODES, 2 ) :
        options = [ ( APSPL[x][y] + APSPL[y][x], (x,y) ) for x,y in itertools.product( u.nodes, v.nodes ) ]
            # round trip cost
        cost, edge = min( options )
        inter_node_distance.add_edge( u, v, cost=cost, edge=edge )
        
    # Step 4: Find a minimum cost spanning tree on inter-node distance graph
    MST = nx.algorithms.minimum_spanning_tree( inter_node_distance, weight='cost' )
    
    # Step 2: Initialize PRETOUR to be empty. For each edge in the matching,
    # associate a direction (from head to tail); insert into PRETOUR
    # (Also, insert the arcs...)
    eulerian = nx.MultiDiGraph()
    for u in NODES :
        for x,y, key in u.enroute.edges_iter( keys=True ) :
            eulerian.add_edge( x,y, key, SERVICE=True )
            
    for u in NODES :
        for x,y in u.balance.edges_iter() :
            eulerian.add_edge( x, y )
    for _,__,data in MST.edges_iter( data=True ) :
        x,y = data.get('edge')
        eulerian.add_edge( x, y )
        eulerian.add_edge( y, x )
        
    try :
        tour = []
        for edge in eulerian_circuit_verbose( eulerian ) :
            if not eulerian.get_edge_data( *edge ).get('SERVICE', False ) : continue
            tour.append( edge )
            
        return tour
    
    except :
        return eulerian

    def __init__(self, core, k, h):
        self.CACHE_BUDGET_FRACTION = .04
        self.N_CONTENTS = 3 * 10 ** 4
        self.N_WARMUP_REQUESTS = 5 * 10 ** 4
        self.N_MEASURED_REQUESTS = 1 * 10 ** 4
        self.GAMMA = 1
        self.ALPHA = .8

        self.INTERNAL_COST = 2
        self.EXTERNAL_COST = 10

        self.on_path_routing = True
        self.on_path_winner = True
        self.relative_popularity = True
        self.cache_placement = 'betweenness'
        self.scenario = 'AUC'
        
        self.saved_shots = []
        self.shots = []

        self.max_delay = h * self.INTERNAL_COST + self.EXTERNAL_COST

        # Uniform cache assignement
        self.core, self.k, self.h = core, k, h
        
        self.topology = self._create_topology(core, k, h)
        self.clients = {node: self.topology.node[node] for node in self.topology.node
                        if self.topology.node[node]['type'] == 'leaf'}
        self.pops = {node: self.topology.node[node] for node in self.topology.node
                     if self.topology.node[node]['type'] == 'root'}
        self.routers = {node: self.topology.node[node] for node in self.topology.node
                        if self.topology.node[node]['type'] in ['root', 'intermediate']}

        self.informations = {node: {} for node in self.topology.node}

        self.workload = StationaryWorkload(self.clients.keys(), self.N_CONTENTS, self.ALPHA,
                                           n_warmup=self.N_WARMUP_REQUESTS,
                                           n_measured=self.N_MEASURED_REQUESTS)
        self._cache_budget = None
        self.cache = None

        self.shortest_path = self._symmetrify_paths(nx.all_pairs_dijkstra_path(self.topology))
        self.neighbors2 = {node: self._neighbors_of_neighbors(node) for node in self.topology.node}

        self.hits = 0
        #        self.cache_hit = {node:{i:0 for i in range(1, 1+self.N_CONTENTS)} for node in self.topology.node}
        #        self.delays = {i:[] for i in range(1, 1+self.N_CONTENTS)}
        self.all_delays = []
        self.cr_hit = []
        self.winners = []

#        probs = []    
    
        self.v_value = lambda p,d,v,pp,dp: p
        self.u_value = lambda p,d,u,path,v: 0

        self.cnt = 0

 def _load_nav_graphs(self):
     ''' Load connectivity graph for each scan, useful for reasoning about shortest paths '''
     print 'Loading navigation graphs for %d scans' % len(self.scans)
     self.graphs = load_nav_graphs(self.scans)
     self.paths = {}
     for scan,G in self.graphs.iteritems(): # compute all shortest paths
         self.paths[scan] = dict(nx.all_pairs_dijkstra_path(G))
     self.distances = {}
     for scan,G in self.graphs.iteritems(): # compute all shortest paths
         self.distances[scan] = dict(nx.all_pairs_dijkstra_path_length(G))

 def __init__(self, data_path):
     with open(data_path, 'r') as graph_file:
         graph_data = json.load(graph_file)
     self.graph = json_graph.node_link_graph(graph_data, multigraph=False)
     self.name_node_map = {node[1]['name']: node[0] for node in self.graph.nodes(data=True)}
     self.all_paths = networkx.all_pairs_dijkstra_path(self.graph)
     self.all_costs = networkx.all_pairs_dijkstra_path_length(self.graph)
     # add blank houses set to each node
     for node in self.graph.nodes():
         self.graph.node[node]['houses'] = []

def all_pairs_shortest_path_weighted(graph):
    paths = nx.all_pairs_dijkstra_path(graph, weight='weight')
    path_weighted_lengths = defaultdict(dict)
    for n1 in paths:
        for n2 in paths[n1]:
            path = paths[n1][n2]
            path_len = sum([graph[path[k-1]][path[k]]['weight'] for k in xrange(1, len(path))])
            path_weighted_lengths[n1][n2] = path_len
            path_weighted_lengths[n2][n1] = path_len
    return paths, path_weighted_lengths

 def _all_paris_shortest_path(self):
     # print one shortest path for all node pairs
     # print nx.shortest_path(self.net)
     with open(OFP_ALL_PAIRS_SHOREST_PATH, 'w') as outp:
         shortest_path = nx.all_pairs_dijkstra_path(self.net)
         for src in shortest_path.keys():
             for dst in shortest_path[src]:
                 outp.write("%s -> %s %s\n" % (self._hostname_Check(src),
                                               self._hostname_Check(dst),
                                               [self._hostname_Check(i) for i in shortest_path[src][dst]]))

 def getSortedListOfPaths(self,graph,logicalNodes):
     path = nx.all_pairs_dijkstra_path(graph)
     lst = []
     for u in logicalNodes:
         for v in logicalNodes:
             if (u>=v):
                 continue
             lst.append((u,v,path[u][v]))
     sortedList = sorted(lst, key=lambda x: len(x[2]))
     return sortedList

def calcPaths(num):
    length = nx.all_pairs_dijkstra_path(G, num)
    length_paths = []
    for node in length:
        for target in length[node]:
            if len(length[node][target]) == num:
                length_paths.append(length[node][target])
    labeled_paths = labels[length_paths]
    same_labels = (squareform(pdist(labeled_paths)) < 1e-10).sum(axis=1)
    return length_paths, labeled_paths, same_labels

 def test_all_pairs_shortest_path(self):
     p = nx.shortest_path(self.cycle)
     assert_equal(p[0][3], [0, 1, 2, 3])
     assert_equal(p, dict(nx.all_pairs_shortest_path(self.cycle)))
     p = nx.shortest_path(self.grid)
     validate_grid_path(4, 4, 1, 12, p[1][12])
     # now with weights
     p = nx.shortest_path(self.cycle, weight='weight')
     assert_equal(p[0][3], [0, 1, 2, 3])
     assert_equal(p, dict(nx.all_pairs_dijkstra_path(self.cycle)))
     p = nx.shortest_path(self.grid, weight='weight')
     validate_grid_path(4, 4, 1, 12, p[1][12])
     # weights and method specified
     p = nx.shortest_path(self.cycle, weight='weight', method='dijkstra')
     assert_equal(p[0][3], [0, 1, 2, 3])
     assert_equal(p, dict(nx.all_pairs_dijkstra_path(self.cycle)))
     p = nx.shortest_path(self.cycle, weight='weight',
                          method='bellman-ford')
     assert_equal(p[0][3], [0, 1, 2, 3])
     assert_equal(p, dict(nx.all_pairs_bellman_ford_path(self.cycle)))

def nodesOmitted(Graph, referenceNode):
    shortest_paths = nx.all_pairs_dijkstra_path(Graph)
    front_path = shortest_paths[referenceNode][0]
    back_path = shortest_paths[referenceNode][len(Graph.nodes()) - 1]
    path = concatenate([front_path, back_path])
    omitted = ones(len(Graph.nodes()))
    for node in path:
        omitted[node] = 0
    return omitted
    G = nx.DiGraph()
    G.add_weighted_edges_from(weights)
    return G

 def test_all_pairs_shortest_path(self):
     p=nx.shortest_path(self.cycle)
     assert_equal(p[0][3],[0,1,2,3])
     assert_equal(p,nx.all_pairs_shortest_path(self.cycle))
     p=nx.shortest_path(self.grid)
     assert_equal(p[1][12],[1, 2, 3, 4, 8, 12])
     # now with weights
     p=nx.shortest_path(self.cycle,weighted=True)
     assert_equal(p[0][3],[0,1,2,3])
     assert_equal(p,nx.all_pairs_dijkstra_path(self.cycle))
     p=nx.shortest_path(self.grid,weighted=True)
     assert_equal(p[1][12],[1, 2, 3, 4, 8, 12])

 def test_all_pairs_shortest_path(self):
     p=nx.shortest_path(self.cycle)
     assert_equal(p[0][3],[0,1,2,3])
     assert_equal(p,nx.all_pairs_shortest_path(self.cycle))
     p=nx.shortest_path(self.grid)
     validate_grid_path(4, 4, 1, 12, p[1][12])
     # now with weights
     p=nx.shortest_path(self.cycle,weight='weight')
     assert_equal(p[0][3],[0,1,2,3])
     assert_equal(p,nx.all_pairs_dijkstra_path(self.cycle))
     p=nx.shortest_path(self.grid,weight='weight')
     validate_grid_path(4, 4, 1, 12, p[1][12])