def test_single_source_shortest_path_length(self):
     ans = dict(nx.shortest_path_length(self.cycle, 0))
     assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
     assert_equal(ans,
                  dict(nx.single_source_shortest_path_length(self.cycle,
                                                             0)))
     ans = dict(nx.shortest_path_length(self.grid, 1))
     assert_equal(ans[16], 6)
     # now with weights
     ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight'))
     assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
     assert_equal(ans, dict(nx.single_source_dijkstra_path_length(
         self.cycle, 0)))
     ans = dict(nx.shortest_path_length(self.grid, 1, weight='weight'))
     assert_equal(ans[16], 6)
     # weights and method specified
     ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight',
                                        method='dijkstra'))
     assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
     assert_equal(ans, dict(nx.single_source_dijkstra_path_length(
         self.cycle, 0)))
     ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight',
                                        method='bellman-ford'))
     assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
     assert_equal(ans, dict(nx.single_source_bellman_ford_path_length(
         self.cycle, 0)))

def main():
    matrix = []
    with open('src/matrix.txt', 'r', encoding='utf-8') as f:
        csv_reader = csv.reader(f)
        for row in csv_reader:
            matrix.append([int(a) for a in row])

    G = nx.DiGraph()
    G.add_nodes_from([(i, j) for i in range(80) for j in range(8)])
    s = (-1, -1)  # supersource
    t = (80, 80)  # supersink
    G.add_nodes_from([s, t])  # supersource and supersink
    for i in range(80):
        G.add_edge(s, (i, 0), weight=0)
        G.add_edge((i, 79), t, weight=matrix[i][-1])

    for i in range(80):
        for j in range(80):
            w = matrix[i][j]
            if i > 0:  # up
                G.add_edge((i, j), (i - 1, j), weight=w)
            if i < 79:  # down
                G.add_edge((i, j), (i + 1, j), weight=w)
            if j < 79:  # right
                G.add_edge((i, j), (i, j + 1), weight=w)

    return nx.single_source_dijkstra_path_length(G, source=s)[t]

def run_simple_iteration(G, ground_motion, demand, multi):
  #G is a graph, demand is a dictionary keyed by source and target of demand per weekday. multi is a boolean that is true if it is a multigraph (can have two parallel edges between nodes)
  #change edge properties
  newG, capacities = damage_network(G, ground_motion, multi) #also returns the number of bridges out
  num_out = sum(x < 100 for x in capacities)
#  util.write_list(time.strftime("%Y%m%d")+'_bridges_scen_1.txt', capacities)   
  #get max flow
  start = time.time()
  #node 5753 is in superdistrict 12, which is santa clara county, and node 3144 is in superdistrict 18, which is alameda county. roughly these are san jose and oakland
  #node 7619 is in superdistrict 1 (7493 is also), which is sf, and node node 3144 is in superdistrict 18, which is alameda county. roughly these are san francisco and oakland
  s = '5753'
  t = '7493' #2702 
  flow = nx.max_flow(newG, s, t, capacity='capacity') #not supported by multigraph
  print 'time to get max flow: ', time.time() - start
#  flow = -1 
  #get ave. shortest path
#  start = time.time()
  sp_dict = nx.single_source_dijkstra_path_length(newG,'7619',weight='distance')
  sp = sum(sp_dict.values())/float(len(sp_dict.values()))
  sp2 = 0
  for target in demand.keys():
    sp2 += sp_dict[target]
  sp2 = sp2 / float(len(demand.keys()))
#  print 'time to get shortest path: ', time.time() - start
  newG = util.clean_up_graph(newG, multi)
  return (num_out, flow, sp, sp2) 

    def nodes_by_distance(self, genome, onlyLeaves=True):
        """
        Returns leaves names sorted by the distance from
        the given genome.
        """
        graph = nx.Graph()
        start = [None]
        def rec_helper(root):
            if root.identifier == genome:
                start[0] = root
            if root.terminal:
                return
            for node, _bootstrap, branch_length in root.edges:
                graph.add_edge(root, node, weight=branch_length)
                rec_helper(node)

        rec_helper(self.tree)
        distances = nx.single_source_dijkstra_path_length(graph, start[0])
        if onlyLeaves:
            nodes = [g for g in distances.keys()
                  if g.terminal and g.identifier != genome]
        else:
            nodes = [g for g in distances.keys()
                  if g.identifier != genome]
        return list(map(str, sorted(nodes, key=distances.get)))

 def test_on_undirected_not_connected_graph(self):
     """
     Test on an undirected and not connected graph. 
     
     Not all nodes will be reachable from the source.
     """
     # make the undirected not connected graph
     params_uncg = {'num_nodes': 200, 'num_edges': 400, 'seed': 0, 
                    'directed': False}
     graph = make_graph(**params_uncg)
     assert(not nx.is_connected(graph))
     # first run dijkstra_sssp 
     dist, _ = dijkstra_sssp.solve(graph, source=0, weight='weight')
     # then run networkx's dijkstra
     nx_dist = nx.single_source_dijkstra_path_length(graph, source=0, 
                                                     weight='weight')
     # finally, compare results
     inf = float('inf')
     for node in graph.nodes_iter():
         if dist[node] != inf:
             # node was reachable
             self.assertEqual(dist[node], nx_dist[node])
         else:
             # node was unreachable
             self.assertTrue(node not in nx_dist)
             self.assertEqual(dist[node], inf)

    def destnode(self, node, dest):
        '''
        return the destination node corresponding to a dest ip.
        node: current node
        dest: ipdest
        returns: destination node name
        '''
        # radix trie lpm lookup for destination IP prefix
        xnode = self.ipdestlpm.get(dest, None)

        if xnode:
            dlist = xnode['dests']
            best = None
            if len(dlist) > 1: 
                # in the case that there are multiple egress nodes
                # for the same IP destination, choose the closest egress
                best = None
                bestw = 10e6
                for d in dlist:
                    w = single_source_dijkstra_path_length(self.graph, node, d)
                    if w < bestw:
                        bestw = w
                        best = d
            else:
                best = dlist[0]

            return best
        else:
            raise InvalidRoutingConfiguration('No route for ' + dest)

def k_skip_graph(G,cover,k):

        H = nx.Graph()
	s1=time.time()
	for node in cover:
		
		G2 = share.vincity(G,node,k)
		SPT = share.SPT(G2,node)
		SPTD = nx.single_source_dijkstra_path_length(SPT,node)
		tmp = [node]
		picked = []
		while(len(tmp)>0):
			x = tmp.pop()
			picked.append(x)
			for u in SPT.neighbors(x):
				if u in picked:
					continue
				if u in cover and u != node:
					H.add_edge(node,u)
					H[node][u]['weight'] = SPTD[u]
				else:
					tmp.insert(0,u)
		
	#	print '..............................................'
        t1 = time.time()
	print '%.4f sec -- kG construct finished' %(t1-s1)        
        return H

    def initialize(self):
        # Generate our corridor map, capturing useful information out of the map
        self.corridor_graph = corridormap.build_graph(self.level.blockHeights, self.level.width, self.level.height)

        # We use scipy to perform a nearest neighbour look-up.
        # This allows use to work out which node the bots are closest to.
        self.kdtree = scipy.spatial.cKDTree([self.corridor_graph.node[n]["position"]
                                             for n in self.corridor_graph.nodes()])
        for node in self.corridor_graph.nodes():
            self.corridor_graph.node[node]["distances"] = nx.single_source_dijkstra_path_length(self.corridor_graph, node, weight="weight")

        # Using the nearest neighbour tree. For each grid block, which is 1m x 1m, what is the closest node.
        self.lookup = [[None for y in range(self.level.height)] for x in range(self.level.width)]
        node_count = len(self.corridor_graph.nodes())
        for x, y in itertools.product(range(self.level.width), range(self.level.height)):
            closest = None
            for d, i in zip(*self.kdtree.query((x, y), 2, distance_upper_bound=8.0)):
                if i >= node_count:
                    continue
                if closest is None or d < closest:
                    self.lookup[x][y] = i
                    closest = d

        self.terminal_nodes = []
        for node in self.corridor_graph.nodes():
            # If only one neighbor then it's a terminal node.
            if len(self.corridor_graph.neighbors(node)) == 1:
                self.terminal_nodes.append(node)


        # Initialise all nodes to not having been visited.
        self.explored = [False for x in range(len(self.corridor_graph.nodes()))]

        self.initialise = True

def shortestpath(picking):
    # iterate through the list of  picking and calculate distance between each items
    # using Graph(setup). Calculates shortest path and returns result
    # undirected graph, nodes does not repeat
    p = picking
    setup = G
    newsort = [picking[0]]
    k = picking[0]
    lowest = []

    while len(newsort) != len(p):
        filteredlist = {}
        path = nx.single_source_dijkstra_path_length(setup, k, cutoff=None, weight='weight')

        for x in newsort:
            if path.has_key(x):
                del path[x]

        for key in path:
            if key in p:
                filteredlist[key] = path[key]


        if filteredlist != {}:
            lowest = min(filteredlist, key=filteredlist.get)
        newsort.append(lowest)
        k = lowest

    return newsort[0:len(p)]

def bounding_diameters(graph):
    w_set = dict(graph.degree())
    n = len(w_set)

    e_lower = numpy.empty((n,))
    e_upper = numpy.empty((n,))
    e_lower[:] = -float("inf")
    e_upper[:] = float("inf")

    lower_bound = -float("inf")
    upper_bound = float("inf")

    while (lower_bound != upper_bound) and (len(w_set) != 0):
        v = max(w_set.iteritems(), key=operator.itemgetter(1))[0]
        path_lengths = nx.single_source_dijkstra_path_length(graph, v)
        ecc = max(path_lengths.iteritems(), key=operator.itemgetter(1))[1]  # plucking highest value in dict

        lower_bound = max(lower_bound, ecc)
        upper_bound = min(upper_bound, 2 * ecc)
        temp = w_set.copy()
        for w in w_set:
            e_lower[w] = max(e_lower[w], max(ecc - path_lengths[w], path_lengths[w]))
            e_upper[w] = min(e_upper[w], ecc + path_lengths[w])
            if (e_upper[w] <= lower_bound and e_lower[w] >= upper_bound / 2) or e_lower[w] == e_upper[w]:
                del temp[w]
        w_set = temp

    return lower_bound

 def calculateGameDistance(self,gameProduct):
     """Calculates the graph distance from each state in the
     Automaton to the nearest accepting state, that is it constructs
     the field lyapFun."""
     
     ###Find all shortest paths from each node to each accepting state ####
     dictList = list()
     for acceptingstate in copy.deepcopy(self.acceptingStates):
         nei = self.graph.predecessors(acceptingstate)
         if len(nei) > 0:
             nextDict = nx.single_source_dijkstra_path_length(copy.deepcopy(self.graph.reverse()),acceptingstate)
             dictList.append(nextDict)
         else:
             self.acceptingStates.remove(acceptingstate)
     self.lyapFun = dict()
     for state in self.graph.nodes():
         self.lyapFun[state] = None
     for state in self.acceptingStates:
         self.lyapFun[state] = 0.0
     for state in self.graph.nodes():
         if gameProduct.gameStates[state[0]].userID[7][0]!='E': #not the environment's turn
             for d in dictList:
                 if state in d.keys():
                     if d[state] < self.lyapFun[state] or self.lyapFun[state] is None: 
                         self.lyapFun[state] = copy.deepcopy(d[state])# Find closest accepting state for each node

    def initialize(self):
        layer = self.visualizer.anonymousLayer(True)
        self.visualizer.addLabel("Initializing...", "centered-info-box", Color(222, 222, 222, 255), None)
        self.visualizer.endLayer()

        self.bestBotShapeId = -1
        self.selectedBot = None
        self.selectedBotShapeId = -1
        self.lastClickTime = time.time()
        self.botWaypoints = {}
        self.graph = corridormap.build_graph(self.level.blockHeights, self.level.width, self.level.height)
        self.kdtree = scipy.spatial.cKDTree([self.graph.node[node]["position"] for node in self.graph.nodes()])

        self.lookup = [[None for y in range(self.level.height)] for x in range(self.level.width)]
        node_count = len(self.graph.nodes())
        for x, y in itertools.product(range(self.level.width), range(self.level.height)):
            closest = None
            for d, i in zip(*self.kdtree.query((x, y), 2, distance_upper_bound=8.0)):
                if i >= node_count:
                    continue
                if closest is None or d < closest:
                    self.lookup[x][y] = i
                    closest = d

        for node in self.graph.nodes():
            self.graph.node[node]["distances"] = nx.single_source_dijkstra_path_length(self.graph, node, weight="weight")
            self.graph.node[node]["explored"] = False
        self.initGraphVisualization()

        self.visualizer.hideLayer(layer)

    def getFreePathToTarget(self, bot, current, target):
        ## tmp: get one of the current active paths
        if len(self.botWaypoints) == 0 or (len(self.botWaypoints) == 1 and bot in self.botWaypoints):
            return nx.shortest_path(self.graph, current, target, weight="weight")
        rndKey = random.choice([key for key in self.botWaypoints.keys() if key != bot])
        otherPath = self.botWaypoints[rndKey][0]

        ## Create a dummy graph node and connect it to each nodes of the shortest path.
        u = "startNode"
        self.graph.add_node(u)
        for v in otherPath:
            self.graph.add_edge(u, v, weight=1)

        ## Now calculate the path lengths of all graph nodes to the shortest path nodes.
        distances = nx.single_source_dijkstra_path_length(self.graph, u, weight="weight")
        self.graph.remove_node(u)  # we don't need the dummy graph node any more
        del distances[u]

        ## Create weight heuristics based on path lengths.
        for node_index, length in distances.iteritems():
            self.graph.node[node_index]["weight"] = length
        for u, v in self.graph.edges():
            w = (self.graph.node[u]["weight"] + self.graph.node[v]["weight"]) * 0.5
            self.graph[u][v]["weight"] = 1 / w ** 2

        ## And finally calculate the path to the flanking position.
        return nx.shortest_path(self.graph, current, target, weight="weight")

def average_shortest_path_length(G, weight=None):
    r"""Return the average shortest path length.

    The average shortest path length is

    .. math::

       a =\sum_{s,t \in V} \frac{d(s, t)}{n(n-1)}

    where `V` is the set of nodes in `G`,
    `d(s, t)` is the shortest path from `s` to `t`,
    and `n` is the number of nodes in `G`.

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

    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.

    Raises
    ------
    NetworkXError:
       if the graph is not connected.

    Examples
    --------
    >>> G=nx.path_graph(5)
    >>> print(nx.average_shortest_path_length(G))
    2.0

    For disconnected graphs you can compute the average shortest path
    length for each component:
    >>> G=nx.Graph([(1,2),(3,4)])
    >>> for g in nx.connected_component_subgraphs(G):
    ...     print(nx.average_shortest_path_length(g))
    1.0
    1.0

    """
    if G.is_directed():
        if not nx.is_weakly_connected(G):
            raise nx.NetworkXError("Graph is not connected.")
    else:
        if not nx.is_connected(G):
            raise nx.NetworkXError("Graph is not connected.")
    avg=0.0
    if weight is None:
        for node in G:
            path_length=nx.single_source_shortest_path_length(G, node)
            avg += sum(path_length.values())
    else:
        for node in G:
            path_length=nx.single_source_dijkstra_path_length(G, node, weight=weight)
            avg += sum(path_length.values())
    n=len(G)
    return avg/(n*(n-1))

 def compute_shortest_paths(self, ydim):
     start = time.time()
     self.source = self.N.nodes()[argmin(self.P[self.N.nodes(), ydim])]
     self.shortest_paths = nx.single_source_dijkstra_path(self.N,
                                                          self.source)
     self.max_path_len = max(nx.single_source_dijkstra_path_length(self.N,
                                                       self.source).values())
     print 'G compute time: %f seconds' % (time.time() - start)

def GlobalEfficiency(G):
    avg = 0.0
    n = len(G)
    for node in G:
        path_length=nx.single_source_dijkstra_path_length(G, node, weight='weight')
        avg += sum(1.0/v for v in path_length.values() if v !=0)
    avg *= 1.0/(n*(n-1))
    return avg

 def _landmark_index(self):
     """
     Uses any of the landmark selection algorithms and returns a list of landmarks and the shortest paths to all of its
     reachable vertices
     :return: {landmark1: {v1: 5, v2: 10, ...}, landmark2: {v1: 4, v2: 15}}
     """
     landmarks = self._pick_landmarks(self.resolution)
     return {l: nx.single_source_dijkstra_path_length(self.G, l) for l in landmarks}

def AIS(G, alpha, k, uq):
	H = [] #initialise min-heap H
	R = {} #result set
	global clusters
	global fk
	global fk_id
	global max_dist
	count = 0
	length=nx.single_source_dijkstra_path_length(G,uq)
	for c in clusters:
		heapq.heappush(H, (clusters[c].MINF, 'Cluster', clusters[c].cluster_id)) #push all clusters into heap with MINF as key
	while len(H): #while heap is not empty and head's key is less than fk
		if count<k:
			temp = heapq.heappop(H) #pop the head item of H
			if temp[1] == 'Cluster': #if popped item is a cluster
				cluster = clusters[temp[2]]				
				for u in cluster.users: #push all users in cluster with MINF as key
					if u != uq:
						d = math.sqrt((G.node[uq]['x'] - G.node[u]['x'])**2 + (G.node[uq]['y'] - G.node[u]['y'])**2)
						user_key = alpha*cluster.pcap + (1-alpha)*d/max_dist
						heapq.heappush(H, (user_key, 'User', u))
			else: #if popped item is a user
				if temp[2] in length:
					p = length[temp[2]] #implement Dijkstra's here for now
					d = math.sqrt((G.node[uq]['x'] - G.node[temp[2]]['x'])**2 + (G.node[uq]['y'] - G.node[temp[2]]['y'])**2)
					f = alpha*p + (1-alpha)*d/max_dist
					if f>fk:
						fk = f
						fk_id = temp[2]
					R[temp[2]] = f
					#print(R)
					count += 1
		else:
			if H[0][0] < fk:
				temp = heapq.heappop(H) #pop the head item of H
				if temp[1] == 'Cluster': #if popped item is a cluster
					cluster = clusters[temp[2]]				
					for u in cluster.users: #push all users in cluster with MINF as key
						if u != uq:
							d = math.sqrt((G.node[uq]['x'] - G.node[u]['x'])**2 + (G.node[uq]['y'] - G.node[u]['y'])**2)
							user_key = alpha*cluster.pcap + (1-alpha)*d/max_dist
							heapq.heappush(H, (user_key, 'User', u))
				else: #if popped item is a user
					if temp[2] in length:
						p = length[temp[2]] #implement Dijkstra's here for now
						d = math.sqrt((G.node[uq]['x'] - G.node[temp[2]]['x'])**2 + (G.node[uq]['y'] - G.node[temp[2]]['y'])**2)
						f = alpha*p + (1-alpha)*d/max_dist
						if f<fk:
							del R[fk_id]
							R[temp[2]] = f
							#print(R)
							fk_id = max(R, key=R.get)
							fk = R[fk_id]
			else:
				break					
	return R

 def closeness_centrality(self):
     """calculate the closeness centrality
     i.e., the average path length to every other network node
     """
     print '\n++++++++ closeness centrality ++++++++'
     nc = {}
     for n in self.graph:
         distances = nx.single_source_dijkstra_path_length(self.graph, n)
         nc[n] = sum(distances.values()) / len(self.graph)
     self.print_centralities(nc)

def get_travel_times(edges, locations, origin=DEFAULT_ORIGIN, transit_time=5):
    G = nx.Graph()
    G.add_weighted_edges_from(map(tuple, list(edges.reset_index().values)))
    
    for naptan, location in locations.iterrows():
        if location.hub_naptan != '':
            G.add_weighted_edges_from([(naptan, location.hub_naptan, transit_time)])
            
    times = nx.single_source_dijkstra_path_length(G, origin, weight='weight')
    return pd.Series(times)