def run_nx(n, niter):
    pb = progressbar.ProgressBar(maxval=niter).start()
    g = nx.barabasi_albert_graph(n, 2)
    start = time.time()
    for i in range(niter):
        nx.all_pairs_shortest_path_length(g)
        pb.update(i)
    pb.finish()
    end = time.time()
    return (start, end)

def closenessCentrality(A):  
    H = nx.from_numpy_matrix(A);
    length = list(nx.all_pairs_shortest_path_length(H));
    print(length)
    distanceMatrix = [];
    rows = len(length);
    for i in range(0, rows):
        x = length[i];
        y = x[1];
        for j in range(0, rows):
            distanceMatrix.append(y[j]);
      
    a = np.array(distanceMatrix);
    a = a.reshape(rows, rows);
    sum = 0;
    result1 = [];
    rows = a.shape[0];
    cols = a.shape[1];
    for r in range(0, rows):
        sum = 0;
        for c in range(0, cols):
            if(r != c):
                sum += a[r][c];
        result1.append((rows - 1) / sum);
    return result1   

def create_hc(G, t=1.0):
    """
    Creates hierarchical cluster of graph G from distance matrix
    Maksim Tsvetovat ->> Generalized HC pre- and post-processing to work on labelled graphs and return labelled clusters
    The threshold value is now parameterized; useful range should be determined experimentally with each dataset
    """

    """Modified from code by Drew Conway"""
    
    ## Create a shortest-path distance matrix, while preserving node labels
    labels=G.nodes()    
    path_length=nx.all_pairs_shortest_path_length(G)
    distances=numpy.zeros((len(G),len(G))) 
    i=0   
    for u,p in path_length.items():
        j=0
        for v,d in p.items():
            distances[i][j]=d
            distances[j][i]=d
            if i==j: distances[i][j]=0
            j+=1
        i+=1
    
    # Create hierarchical cluster
    Y=distance.squareform(distances)
    Z=hierarchy.complete(Y)  # Creates HC using farthest point linkage
    # This partition selection is arbitrary, for illustrive purposes
    membership=list(hierarchy.fcluster(Z,t=t))
    # Create collection of lists for blockmodel
    partition=defaultdict(list)
    for n,p in zip(list(range(len(G))),membership):
        partition[p].append(labels[n])
    return list(partition.values())

def path_lengths(G):
    """Compute array of all shortest path lengths for the given graph.

    The length of the output array is the number of unique pairs of nodes that
    have a connecting path, so in general it is not known in advance.

    This assumes the graph is undirected, as for any pair of reachable nodes,
    once we've seen the pair we do not keep the path length value for the
    inverse path.
    
    Parameters
    ----------
    G : an undirected graph object.
    """

    assert_no_selfloops(G)
    
    length = nx.all_pairs_shortest_path_length(G)
    paths = []
    seen = set()
    for src,targets in length.iteritems():
        seen.add(src)
        neigh = set(targets.keys()) - seen
        paths.extend(targets[targ] for targ in neigh)
    
    
    return np.array(paths) 

def calc_distance_matrix(G, max_distance=None):
    """Returns a matrix containing the shortest distance
    between all nodes in a network

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

    max_distance : float or None, optional (default='None')
       The maximum possible distance value in the network.
       If None, max_distance is the longest shortest path between
       two nodes of the network (the graph eccentricity)

    Returns
    -------
    dist_matrix : NumPy array
      An NxN numpy array.

    Notes
    -----
    Along the diagonal, the values are all 0.
    Unconnected nodes have a distance of max_distance to other nodes.
    """

    # Network (collaborator) Distance
    dist_matrix = nx.all_pairs_shortest_path_length(G)
    dist_matrix = DataFrame(dist_matrix, index=G.nodes(), columns=G.nodes())
    if max_distance is None:
        max_distance = float(dist_matrix.max().max())
    dist_matrix = dist_matrix.fillna(max_distance)
    # The unconnected ones are infinitely far from the rest
    diag_idx = np.diag_indices(len(dist_matrix), ndim=2)
    dist_matrix.values[diag_idx] = 0
    return dist_matrix

def create_hr(G):
   """
   Create heirarchical cluster of a graph G from distance matrix
   """
   # create shortest path matrix
   labels=G.nodes()
   path_length = nx.all_pairs_shortest_path_length(G)

def od_pairs_from_topology(topology):
    """
    Calculate all possible origin-destination pairs of the topology. 
    This function does not simply calculate all possible pairs of the topology
    nodes. Instead, it only returns pairs of nodes connected by at least
    a path. 

    Parameters
    ----------
    topology : Topology or DirectedTopology
        The topology whose OD pairs are calculated

    Returns
    -------
    od_pair : list
        List containing all origin destination tuples.
    
    Examples
    --------
    >>> import fnss
    >>> topology = fnss.ring_topology(3)
    >>> fnss.od_pairs_from_topology(topology)
    [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]
    """
    if topology.is_directed():
        routes = nx.all_pairs_shortest_path_length(topology)
        return [(o, d) for o in routes for d in routes[o] if o != d]
    else:
        conn_comp = nx.connected_components(topology)
        return [(o, d) for G in conn_comp for o in G for d in G if o != d]

def get_distance_dict(filename):
    g = nx.read_edgelist(filename)
    print "Read in edgelist file ", filename
    print nx.info(g)
    path_length = nx.all_pairs_shortest_path_length(g)
    print len(path_length.keys())
    print path_length

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 CheckAllHostConnectivity (pairs, g):
  matrix = nx.all_pairs_shortest_path_length(g)
  connected = 0
  for (a, b) in pairs:
    if b in matrix[a]:
      connected += 1
  return connected

 def nodal_matrix(self):
     """
     Returns a matrix containing the nodal 'distance' between all labelled nodes.
     
     EXAMPLES::
     
         >>> network = PhyloNetwork(eNewick="(((1,2), 3), 4);")
         >>> network.nodal_matrix()
         ... array([[0, 1, 2, 3],
         ...       [1, 0, 2, 3],
         ...       [1, 1, 0, 2], 
         ...       [1, 1, 1, 0])
         
     """
     n = len(self.taxa())
     matrix = numpy.zeros((n, n), int)
     dicdist = all_pairs_shortest_path_length(self)
     for i in range(n):
         ti = self.taxa()[i]
         for j in range(i, n):
             tj = self.taxa()[j]
             lcsa = self.LCSA(ti, tj)
             matrix[i, j] = dicdist[lcsa][self.node_by_taxa(ti)]
             matrix[j, i] = dicdist[lcsa][self.node_by_taxa(tj)]
     return matrix

    def first_return_times( self, k ):
        """Computes:
        
        length = shortest path lengths <= k 

        length[i][j] = length of shortest path i->j, if <= k, using
	NX.all_pairs_shortest_path_length

        length[i] is a dict keyed by neighbors of node i, with values
	length of path to j

        Returns dictionary of return times <= k, length dictionary
        described above.
        """
	return_times = dict()

	# length = shortest path lengths <= k
	# length[i][j] = length of shortest path i->j, if <= k
        # length[i] a dict keyed by neighbors of node i, with values
        # length of path to j
	length = nx.all_pairs_shortest_path_length( self.graph, k )
	for i in G.nodes_iter():
		# nodes = list of successors j which return to i
		nodes = filter(lambda j: length[j].has_key(i),G.successors(i))
		# distances for each successor j
		distances = [length[j][i]+1 for j in nodes]
		if distances:
			return_times[i] = min(distances)

	return return_times, length

def inter_node_distances(graph):
    """Compute the shortest path lengths between all nodes in graph.

    This performs the same operation as NetworkX's
    all_pairs_shortest_path_lengths with two exceptions: Here, self
    paths are excluded from the dictionary returned, and the distance
    between disconnected nodes is set to infinity.  The latter
    difference is consistent with the Brain Connectivity Toolbox for
    Matlab.

    Parameters
    ----------
    graph: networkx Graph
        An undirected graph.

    Returns
    -------
    lengths: dictionary
        Dictionary of shortest path lengths keyed by source and target.

    """
    lengths = nx.all_pairs_shortest_path_length(graph)
    node_labels = sorted(lengths)
    for src in node_labels:
        lengths[src].pop(src)
        for targ in node_labels:
            if src != targ:
                try:
                    lengths[src][targ]
                except KeyError:
                    lengths[src][targ] = np.inf
    return lengths

def local_efficiency(G):
    """Compute array of local efficiency for the given graph.

    Local efficiency: returns a list of paths that represent the nodal
    efficiencies across all nodes with their direct neighbors"""

    assert_no_selfloops(G)

    nodepaths = []
    length = nx.all_pairs_shortest_path_length(G)
    for n in G:
        nneighb = set(nx.neighbors(G,n))

        paths = []
        for nei in nneighb:
            other_neighbors = nneighb - set([nei])
            nei_len = length[nei]
            paths.extend( [nei_len[o] for o in other_neighbors] )

        if paths:
            p = 1.0 / np.array(paths,float)
            nodepaths.append(p.mean())
        else:
            nodepaths.append(0.0)
                
    return np.array(nodepaths)

def get_distance_matrix_from_graph(network, filename = None, floyd = True):
  """ Returns and optionally stores the distance matrix for a given network. 
  By default the networkX BFS implementation is used.
      
  Parameters
  ----------
  network : a NetworkX graph (ATTENTION: nodes need to be sequentially numbered starting at 1!)
  filename : destination for storing the matrix (optional)
  floyd : set to true to use floyd warshall instead of BFS
  
  Returns
  -------
  A Numpy matrix storing all pairs shortest paths for the given network (or the nodes in the given nodelist).
  """

  n = nx.number_of_nodes(network)
  if floyd:
    D = nx.floyd_warshall_numpy(network)
  else:
    D_dict = nx.all_pairs_shortest_path_length(network)
    D = numpy.zeros((n,n))
    for row, col_dict in D_dict.iteritems():
        for col in col_dict:
            D[row-1,col-1] = col_dict[col]
    
  if filename:
    numpy.savetxt(filename, D, fmt='%s', delimiter=",", newline="\n")

  return D

def features_matrix(graph, anchors, use_dist=True, use_pgrs=True,
                    use_pgr=True, use_comm=False, use_comm_centr=False):
    node_feats = []
    n = len(graph)
    if use_dist:
        dists = nx.all_pairs_shortest_path_length(graph)
    if use_pgr:
        pageranks = nx.pagerank_numpy(graph)
    if use_pgrs:
        pgr_anchor = [anchored_pagerank(graph, anchor) for anchor in anchors]
    if use_comm_centr:
        communicability_centrality = nx.communicability_centrality(graph)
    if use_comm:
        communicability = nx.communicability(graph)

    for node in graph.nodes():
        assert node == len(node_feats)
        feats = []
        if use_dist:
            feats += [dists[node][anchor] for anchor in anchors]
        if use_pgrs:
            feats += [pgr[node]*n for pgr in pgr_anchor]
        if use_pgr:
            feats.append(pageranks[node]*n)
        if use_comm_centr:
            feats.append(communicability_centrality[node])
        if use_comm:
            feats += [communicability[node][anchor] for anchor in anchors]


        node_feats.append(np.array(feats))
    return node_feats

    def hcluster(self):
        """

        .. plot::
            :include-source:
            :width: 50%

            from cno import XCNOGraph, cnodata
            c = XCNOGraph(cnodata("PKN-ToyPB.sif"), cnodata("MD-ToyPB.csv"))
            c.hcluster()

        .. warning:: experimental
        """
        from scipy.cluster import hierarchy
        from scipy.spatial import distance
        path_length=nx.all_pairs_shortest_path_length(self.to_undirected())
        n = len(self.nodes())
        distances=np.zeros((n,n))
        nodes = self.nodes()
        for u,p in path_length.iteritems():
            for v,d in p.iteritems():
                distances[nodes.index(u)-1][nodes.index(v)-1] = d
        sd = distance.squareform(distances)
        hier = hierarchy.average(sd)
        pylab.clf();
        hierarchy.dendrogram(hier)

        pylab.xticks(pylab.xticks()[0], nodes)

def first_return_times( k, backwards=False ):
	"""
	RMF: UPDATE

	Look for k-recurrent vertices in the graph of the DiGraph. A
	k-recurrent vertex is a vertex v for which the path v -> v is
	of length <= k.
	
	Optional Parameters
	---------
	
	k : maximum length of path (k+1)
	
	See nx.all_pairs_shortest_path_length(G,k)
	"""
        if backwards:
            G = self.reverse()
            self.backward_return_times = dict()
            rt = self.backward_return_times
        else:
            G = self
            self.forward_return_times = dict()
            rt = self.forward_return_times
	# length = shortest path lengths <= k
	# length[i][j] = length of shortest path i->j, if <= k
        # length[i] a dict keyed by neighbors of node i, with values
        # length of path to j
	length = nx.all_pairs_shortest_path_length( G, k ) 
	for i in G.nodes_iter():
            # nodes = list of successors j which return to i
            nodes = filter( lambda j: length[j].has_key(i), G.successors(i) )
            # distances for each successor j
            distances = [length[j][i]+1 for j in nodes]
            if distances:
                rt[i] = min( distances )

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 path_lengthsSPARSE(G):
    """Compute array of all shortest path lengths for the given graph.

    XXX - implementation using scipy.sparse.  This might be faster for very
    sparse graphs, but so far for our cases the overhead of handling the sparse
    matrices doesn't seem to be worth it.  We're leaving it in for now, in case
    we revisit this later and it proves useful.

    The length of the output array is the number of unique pairs of nodes that
    have a connecting path, so in general it is not known in advance.

    This assumes the graph is undirected, as for any pair of reachable nodes,
    once we've seen the pair we do not keep the path length value for the
    inverse path.
    
    Parameters
    ----------
    G : an undirected graph object.
    """

    assert_no_selfloops(G)
    
    length = nx.all_pairs_shortest_path_length(G)

    nnod = G.number_of_nodes()
    paths_mat = sparse.dok_matrix((nnod,nnod))
    
    for src,targets in length.iteritems():
        for targ,val in targets.items():
            paths_mat[src,targ] = val

    return sparse.triu(paths_mat,1).data