def compare_complexity(max_size, iterations=10):
    size = []
    d_time = []
    f_time = []
    for n in range(10, max_size, 10):
        nodes = n
        size.append(nodes)
        g = SmallWorldGraph(nodes, 4, 0.5)
        # Get Dijkstra time:
        start = etime()
        # Iterate to get a stable estimate of the time
        for it in range(iterations):
            nx.all_pairs_dijkstra_path_length(g)
        end = etime()
        d_time.append(end - start)
        # Get Floyd-Warshall time
        start = etime()
        # Iterate to get a stable estimate of the time
        for it in range(iterations):
            g.shortest_path_all_pairs()
        end = etime()
        f_time.append(end - start)
    pyplot.plot(size, d_time, 'rs')
    pyplot.plot(size, f_time, 'bo')
    pyplot.title("Floyd-Warshall (blue) vs Dijkstra (red)")
    pyplot.savefig("shortest_path_compare.png")

    def test_all_pairs_dijkstra_path_length(self):
        cycle = nx.cycle_graph(7)
        pl = dict(nx.all_pairs_dijkstra_path_length(cycle))
        assert_equal(pl[0], {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})

        cycle[1][2]['weight'] = 10
        pl = dict(nx.all_pairs_dijkstra_path_length(cycle))
        assert_equal(pl[0], {0: 0, 1: 1, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1})

 def compare(self, g1, g2, verbose=False):
     """
     Compute the kernel value between the two graphs.
     """
     djk1 = nx.Graph(nx.all_pairs_dijkstra_path_length(g1))
     djk1.remove_edges_from(djk1.selfloop_edges())
     
     djk2 = nx.all_pairs_dijkstra_path_length(g2)
     djk2.remove_edges_from(djk2.selfloop_edges())

def path_check(G,kG):
	pair = []
	s1 = time.time()
	sp1 = nx.all_pairs_dijkstra_path_length(G)
	t1 = time.time()
	#print 'G %f sec' %(t1-s1)
	s2 = time.time()
	sp2 = nx.all_pairs_dijkstra_path_length(kG)
	t2 = time.time()
	#print 'kG %f sec' %(t2-s2)
	for u,v in kG.edges():
		if sp1[u][v] != sp2[u][v]:
			pair.append((u,v,sp1[u][v],sp2[u][v]))
	print 'speed %f' %(float((t2-s2)-(t1-s1))/(t1-s1))

def create_shortest_path_matrix(weighted=False, discount_highways=False):
    G = nx.DiGraph()

    logging.info("Loading graph to NetworkX from database...")
    c = connection.cursor()
    if discount_highways:
        c.execute("SELECT l.beg_node_id, l.end_node_id, (CASE WHEN l.link_type='1' THEN 0.5 WHEN l.link_type='2' THEN 0.5 ELSE 1.0 END) FROM microsim_link l")
    else:
        c.execute("SELECT l.beg_node_id, l.end_node_id, l.length/l.lane_count AS resistance FROM microsim_link l")
    G.add_weighted_edges_from(c.fetchall())

    logging.debug("Road network is strongly connected: %s" % repr(nx.is_strongly_connected(G)))

    logging.info("Computing shortest paths...")
    if weighted:
        sp = nx.all_pairs_dijkstra_path_length(G)
    else:
        sp = nx.all_pairs_shortest_path_length(G)

    logging.info("Converting shortest paths into matrix...")
    c.execute("SELECT ROW_NUMBER() OVER (ORDER BY id), beg_node_id, end_node_id FROM microsim_link")
    links = c.fetchall()
    N_LINKS = len(links)
    shortest_paths = np.zeros((N_LINKS, N_LINKS))
    for col_idx, _, col_end_node in links:
        for row_idx, _, row_end_node in links:
            if col_idx == row_idx:
                continue
            nodes = sp[col_end_node]
            if row_end_node not in nodes:
                shortest_paths[row_idx - 1, col_idx - 1] = float(N_LINKS)
            else:
                shortest_paths[row_idx - 1, col_idx - 1] = nodes[row_end_node]
    logging.info("Shortest path matrix complete.")
    return shortest_paths

 def compareGraphToOptimum(self):
     shortestPathsWeights = nx.all_pairs_dijkstra_path_length(self.G)
     optimalSum = 0
     graphSum = 0
     mypath = 0
     pathsNotFound = 0
     for source, val in shortestPathsWeights.iteritems():
         for destination, pathLenght in val.iteritems():
             if source == destination:
                 continue
             try:
                 mypath = self.pathLenght(source, destination)
                 graphSum += mypath
                 optimalSum += pathLenght
                 if not mypath == pathLenght:
                     print 'different path from %s to %s with %d to %d' % (str(source), str(destination), mypath, pathLenght)
             except KeyError:
                 print 'incomplete solultion! No path from %s to %s' % (str(source), str(destination))
                 pathsNotFound += 1
                 optimalSum += pathLenght
                 graphSum += 2*pathLenght
                 #return '','incomplete'
     error = (float(graphSum)-float(optimalSum))/float(optimalSum)
     print "Error of found paths: %f%%, Paths not found: %d" %(100*error,pathsNotFound)
     #print 'optimal shortest-paths sum: %s, graph shortest-path sum: %s.' % (str(optimalSum), str(graphSum))
     return error, pathsNotFound

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 diameter(g, weighted):
    if not weighted:
        return nx.diameter(g)
    else:
        ret = nx.all_pairs_dijkstra_path_length(g)
        return max(map(lambda perSourceDists: max(perSourceDists.values()), ret.values()))
        pass

    def distances_to_tour(self):
        scaffolds = self.scaffolds
        distances = self.distances
        G = nx.DiGraph()
        for (a, b), v in distances.items():
            d = self.weighted_mean(v)
            G.add_edge(a, b, weight=d)
            if a == START or b == END:
                continue
            G.add_edge(b, a, weight=d)

        logging.debug("Graph size: |V|={0}, |E|={1}.".format(len(G), G.size()))

        L = nx.all_pairs_dijkstra_path_length(G)
        for a, b in combinations(scaffolds, 2):
            if G.has_edge(a, b):
                continue
            l = L[a][b]
            G.add_edge(a, b, weight=l)
            G.add_edge(b, a, weight=l)

        edges = []
        for a, b, d in G.edges(data=True):
            edges.append((a, b, d['weight']))

        try:
            tour = hamiltonian(edges, directed=True, precision=2)
            assert tour[0] == START and tour[-1] == END
            tour = tour[1:-1]
        except:
            logging.debug("concorde-TSP failed. Use default scaffold ordering.")
            tour = scaffolds[:]
        return tour

def initialize_graph(size):
    points_x = []
    points_y = []
    terminals = []
    for i in range(size):
        points_x.append(random.uniform(-100, 100))
        points_y.append(random.uniform(-100, 100))
    for i in range(size):
        if i % 2 == 0:
            terminals.append(i)

    h = nx.erdos_renyi_graph(size, 0.3)
    g = nx.Graph()
    for i in range(size):
        g.add_node(i)

    for i in range(size):
        for j in range(i, size):
            if h.has_edge(i, j):
                g.add_edge(i, j)
                # weight=manhattan_distance((points_x[i], points_y[i]), (points_x[j], points_y[j])))

    length_shortest_paths = nx.all_pairs_dijkstra_path_length(g)
    shortest_paths = nx.all_pairs_shortest_path(g)

    metric_closure = nx.Graph()
    for i in range(size):
        metric_closure.add_node(i)
    for i in range(size):
        for j in range(size):
            metric_closure.add_edge(i, j, weight=length_shortest_paths[i][j])

    print metric_closure
    return (terminals, shortest_paths, metric_closure, points_x, points_y, g)

    def __init__(self, view, controller, metacaching, implementation='ideal',
                 radius=4, **kwargs):
        """Constructor

        Parameters
        ----------
        view : NetworkView
            An instance of the network view
        controller : NetworkController
            An instance of the network controller
        metacaching : str (LCE | LCD)
            Metacaching policy used
        implementation : str, optional
            The implementation of the nearest replica discovery. Currently on
            ideal routing is implemented, in which each node has omniscient
            knowledge of the location of each content.
        radius : int, optional
            Radius used by nodes to discover the location of a content. Not
            used by ideal routing.
        """
        super(NearestReplicaRouting, self).__init__(view, controller)
        if metacaching not in ('LCE', 'LCD'):
            raise ValueError("Metacaching policy %s not supported" % metacaching)
        if implementation not in ('ideal', 'approx_1', 'approx_2'):
            raise ValueError("Implementation %s not supported" % implementation)
        self.metacaching = metacaching
        self.implementation = implementation
        self.radius = radius
        self.distance = dict(nx.all_pairs_dijkstra_path_length(self.view.topology(),
                                                               weight='delay'))

def get_diameter(g):
    vertices = g.nodes()
    #pairs = get_pairs(vertices)
    dists = networkx.all_pairs_dijkstra_path_length(g)
    #for s in  shortest_paths.keys():
    #    print s,shortest_paths[s]
    return  max(get_vertices([x.values() for x in dists.values()]))

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 getGroupMetrics(G, results):
    results.numEdges = len(G.edges())
    results.numNodes = len(G.nodes())
    pathLenghts = nx.all_pairs_dijkstra_path_length(G, 
            weight="weight").values()
    results.averageShortestPathWeighted = np.average(
            [ x.values()[0] for x in pathLenghts])
    results.maxShortestPathWeighted = np.max(
            [ x.values()[0] for x in pathLenghts])
    pathLenghts = nx.all_pairs_shortest_path_length(G).values()
    results.averageShortestPath = np.average(
            [ x.values()[0] for x in pathLenghts])
    results.maxShortestPath = np.max(
            [ x.values()[0] for x in pathLenghts])
    cache = None
    runResB = {}
    runResC = {}
    for i in range(4,6):
        res = computeGroupMetrics(G, groupSize=i, weighted=True, 
            cutoff = 2, shortestPathsCache=cache)
        cache = res[-1]
        runResB[i] = [res[0], res[1]]
        runResC[i] = [res[2], res[3]]
    results.groupMetrics['betweenness'] = runResB 
    results.groupMetrics['closeness'] = runResC 

def shortest_path(graph):
    """ All-pairs shortest path on the graph of inverse weights.

    For each pair, calculates the sum of the weights on the shortest path
    (by weight) between each pair in the graph. Uses the inverse weights
    to calculate, and inverts the final weight, such that a higher score is
    considered better.

    Returns:
        An array of n arrays of length n, representing the weight of the
        shortest path between each pair of nodes on the graph of inverse
        weights. None is used for pairs where there is no path.
    """
    num_nodes = graph.number_of_nodes()
    nx_dict = nx.all_pairs_dijkstra_path_length(
        graph, weight='inv_weight')
    # Convert from dict format to array format
    shortest_paths = np.zeros((num_nodes, num_nodes))
    for i, d in nx_dict.iteritems():
        for j in xrange(num_nodes):
            try:
                shortest_paths[i, j] = 1.0 / d[j]
            except (KeyError, ZeroDivisionError):
                shortest_paths[i, j] = np.inf
    return shortest_paths

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 _compute_all_pairs(self, graph, weight=None, normalize=False):
     lengths = nx.all_pairs_dijkstra_path_length(graph, weight=weight)
     max_length = max([max(lengths[i].values()) for i in lengths])
     if normalize:
         for i in lengths:
             for j in lengths[i]:
                 lengths[i][j] = float(lengths[i][j]) / max_length
     return lengths

def dijkstra_path(G):
    """Return the shortest Dijkstra (weighted) path between all pairs of
    vertices (averaged twice)
    """
    dijkstra_path = nx.all_pairs_dijkstra_path_length(G)
    summed_dpv = [sum(dpv.values()) for dpv in dijkstra_path.values()]
    average_dijkstra_path = sum(summed_dpv)/ (len(G.nodes())**2)
    return average_dijkstra_path

def roadnet_APSP( roadnet, length='length' ) :
    digraph = nx.MultiDiGraph()
    for i,j,key,data in roadnet.edges_iter( keys=True, data=True ) :
        edgelen = data.get( length, 1 )
        digraph.add_edge( i,j,key, weight=edgelen )
        if not data.get( 'oneway', False ) :
            digraph.add_edge( j,i,key, weight=edgelen )
    return nx.all_pairs_dijkstra_path_length( digraph )

def calc_influence(DiG,cf):
  sp = nx.all_pairs_dijkstra_path_length(DiG,cf)
  for key in sp:
    d = sp[key]
    for idx in d:
      # add influence to expect node
      dd = d[idx]/cf
      G.node[idx]['density'] += (1.0-dd*dd)*3/4