def test_zero_weight(self):
        G = nx.DiGraph()
        edges = [(1,2,-2), (2,3,-4), (1,5,1), (5,4,0), (4,3,-5), (2,5,-7)]
        G.add_weighted_edges_from(edges)
        dist = nx.floyd_warshall_numpy(G)
        assert_equal(int(numpy.min(dist)), -14)

        G = nx.MultiDiGraph()
        edges.append( (2,5,-7) )
        G.add_weighted_edges_from(edges)
        dist = nx.floyd_warshall_numpy(G)
        assert_equal(int(numpy.min(dist)), -14)

def initialize_rope_from_cloud(xyzs, plotting=False):
    xyzs = xyzs.reshape(-1,3)
    if len(xyzs) > 500: xyzs = xyzs[::len(xyzs)//500]

    pdists = ssd.squareform(ssd.pdist(xyzs,'sqeuclidean'))
    G = nx.Graph()
    for (i_from, row) in enumerate(pdists):
        to_inds = np.flatnonzero(row[:i_from] < MAX_DIST**2)
        for i_to in to_inds:
            G.add_edge(i_from, i_to, weight = pdists[i_from, i_to])

    A = nx.floyd_warshall_numpy(G)
    A[np.isinf(A)] = 0
    (i_from_long, i_to_long) = np.unravel_index(A.argmax(), A.shape)

    nodes = G.nodes();
    path = nx.shortest_path(G, source=nodes[i_from_long], target=nodes[i_to_long])
    xyz_path = xyzs[path,:]
    xyzs_unif = curves.unif_resample(xyz_path,N_CTRL_PTS,tol=.005)
    labels = np.ones(len(xyzs_unif)-1,'int')
    labels[[0,-1]] = 2

    if plotting:
        import enthought.mayavi.mlab as mlab
        mlab.plot3d(*xyzs_unif.T, tube_radius=.001)
        mlab.points3d(*xyzs.T, scale_factor=.01)
        mlab.show()

    return xyzs_unif, labels

def contacts2distances(contacts):
    """ Infer distances from contact matrix
    """
    # create graph
    graph = nx.Graph()
    graph.add_nodes_from(range(contacts.shape[0]))

    for row in range(contacts.shape[0]):
        for col in range(contacts.shape[1]):
            freq = contacts[row, col]
            if freq != 0:
                graph.add_edge(col, row, weight=1/freq)

    # find shortest paths
    spath_mat = nx.floyd_warshall_numpy(graph, weight='weight')

    # create distance matrix
    distances = np.zeros(contacts.shape)
    for row in range(contacts.shape[0]):
        for col in range(contacts.shape[1]):
            if spath_mat[row, col] == float('inf'):
                distances[row, col] = 1000000
            else:
                distances[row, col] = spath_mat[row, col]

    return distances

 def test_weighted_numpy(self):
     XG4=nx.Graph()
     XG4.add_weighted_edges_from([ [0,1,2],[1,2,2],[2,3,1],
                                   [3,4,1],[4,5,1],[5,6,1],
                                   [6,7,1],[7,0,1] ])
     dist = nx.floyd_warshall_numpy(XG4)
     assert_equal(dist[0,2],4)

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 test_cycle_numpy(self):
     try:
         import numpy
     except ImportError:
         raise SkipTest('numpy not available.')
     dist = nx.floyd_warshall_numpy(nx.cycle_graph(7))
     assert_equal(dist[0,3],3)
     assert_equal(dist[0,4],3)

 def test_weight_parameter_numpy(self):
     XG4 = nx.Graph()
     XG4.add_edges_from([ (0, 1, {'heavy': 2}), (1, 2, {'heavy': 2}),
                          (2, 3, {'heavy': 1}), (3, 4, {'heavy': 1}),
                          (4, 5, {'heavy': 1}), (5, 6, {'heavy': 1}),
                          (6, 7, {'heavy': 1}), (7, 0, {'heavy': 1}) ])
     dist = nx.floyd_warshall_numpy(XG4, weight='heavy')
     assert_equal(dist[0, 2], 4)

 def _compare(self, g1, g2):
     """Compute the kernel value between the two graphs. 
     
     Parameters
     ----------
     g1 : ndarray
         Adjacency matrix of the first graph.
     g2 : ndarray
         Adjacency matrix of the second graph.
         
     Returns
     -------        
     k : The similarity value between g1 and g2.
     """
     if self.binary_edges:
         g1 = np.where(g1 > self.th, 1, 0)
         g2 = np.where(g2 > self.th, 1, 0)
     else:
         g1 = np.where(g1 > self.th, g1, 0)
         g2 = np.where(g2 > self.th, g2, 0)
     
     g1 = nx.from_numpy_matrix(g1)
     g2 = nx.from_numpy_matrix(g2)
     
     #Diagonal superior matrix of the floyd warshall shortest paths
     fwm1 = np.array(nx.floyd_warshall_numpy(g1))
     fwm1 = np.where(fwm1==np.inf, 0, fwm1)
     fwm1 = np.where(fwm1==np.nan, 0, fwm1)
     fwm1 = np.triu(fwm1, k=1)
     bc1 = np.bincount(fwm1.reshape(-1).astype(int))
     
     fwm2 = np.array(nx.floyd_warshall_numpy(g2))
     fwm2 = np.where(fwm2==np.inf, 0, fwm2)
     fwm2 = np.where(fwm2==np.nan, 0, fwm2)
     fwm2 = np.triu(fwm2, k=1)
     bc2 = np.bincount(fwm2.reshape(-1).astype(int))
     
     #Copy into arrays with the same length the non-zero shortests paths
     v1 = np.zeros(max(len(bc1),len(bc2)) - 1)
     v1[range(0,len(bc1)-1)] = bc1[1:]
     
     v2 = np.zeros(max(len(bc1),len(bc2)) - 1)
     v2[range(0,len(bc2)-1)] = bc2[1:]
     
     return np.sum(v1 * v2)

def mds_embed(graph):

    sorted_node_list = sorted(list(graph.nodes()), key=len)
    dmat = nx.floyd_warshall_numpy(graph, nodelist=sorted_node_list)

    gmds = MDS(n_jobs=-2, dissimilarity="precomputed")
    embed_pts = gmds.fit_transform(dmat)

    return (embed_pts, dmat, sorted_node_list)

    def compare(self, g_1, g_2, verbose=False):
        """Compute the kernel value (similarity) between two graphs. 
        
        Parameters
        ----------
        g1 : networkx.Graph
            First graph.
        g2 : networkx.Graph
            Second graph.
        alpha : interger < 1
            A rule of thumb for setting it is to take the largest power of 10
            which is samller than 1/d^2, being d the largest degree in the 
            dataset of graphs.    
            
        Returns
        -------        
        k : The similarity value between g1 and g2.
        """
        #Diagonal superior matrix of the floyd warshall shortest paths
#        pdb.set_trace()
        fwm1 = np.array(nx.floyd_warshall_numpy(g_1))
        fwm1 = np.where(fwm1==np.inf, 0, fwm1)
        fwm1 = np.where(fwm1==np.nan, 0, fwm1)
        fwm1 = np.triu(fwm1, k=1)
        bc1  = np.bincount(fwm1.reshape(-1).astype(int))
#        print bc1
        
        fwm2 = np.array(nx.floyd_warshall_numpy(g_2))
        fwm2 = np.where(fwm2==np.inf, 0, fwm2)
        fwm2 = np.where(fwm2==np.nan, 0, fwm2)
        fwm2 = np.triu(fwm2, k=1)
        bc2  = np.bincount(fwm2.reshape(-1).astype(int))
#        print bc2
#        pdb.set_trace()
        
        #Copy into arrays with the same length the non-zero shortests paths
        v1 = np.zeros(max(len(bc1),len(bc2)) - 1)
        v1[range(0,len(bc1)-1)] = bc1[1:]
        
        v2 = np.zeros(max(len(bc1),len(bc2)) - 1)
        v2[range(0,len(bc2)-1)] = bc2[1:]
        
        return np.sum(v1 * v2)

 def test_weighted_numpy(self):
     try:
         import numpy
     except ImportError:
         raise SkipTest('numpy not available.')
     XG3=nx.Graph()
     XG3.add_weighted_edges_from([ [0,1,2],[1,2,12],[2,3,1],
                                   [3,4,5],[4,5,1],[5,0,10] ])
     dist = nx.floyd_warshall_numpy(XG3)
     assert_equal(dist[0,3],15)

def _cal_dist2center(G, Centeroids):
    """ Calculate the distances to cluster centers
    """  
    D_Matrix = nx.floyd_warshall_numpy(G)  
    Dict = {}
    for i in Centeroids:
        Dict[i] = []
        for j in range(len(G.nodes())):
            Dict[i].append(D_Matrix[i,j])
    return(Dict) 

def Dis_Clus(G):
    """adding one row to distance matrix 
    The new row shows nodes clusters
    each node is a cluster at initial"""   
    D_Matrix = nx.floyd_warshall_numpy(G) 
    nodes_label = []
    for i in range(len(G.nodes())):
         nodes_label.append(set(G.nodes()[i]))
         
    A = np.vstack([D_Matrix, nodes_label])  
    return(A)

 def test_weight_parameter_numpy(self):
     try:
         import numpy
     except ImportError:
         raise SkipTest('numpy not available.')
     XG4 = nx.Graph()
     XG4.add_edges_from([ (0, 1, {'heavy': 2}), (1, 2, {'heavy': 2}),
                          (2, 3, {'heavy': 1}), (3, 4, {'heavy': 1}),
                          (4, 5, {'heavy': 1}), (5, 6, {'heavy': 1}),
                          (6, 7, {'heavy': 1}), (7, 0, {'heavy': 1}) ])
     dist = nx.floyd_warshall_numpy(XG4, weight='heavy')
     assert_equal(dist[0, 2], 4)

 def _get_all_distances(self):
     if not self._distances is None:
         return self._distances
     nodes = self._frame_graph.nodes(data=True)
     frame_ids, frame_names = zip(*[(i, n['obj'].name) for i, n in nodes])
     # calculate all pairwise distances
     np_distances = nx.floyd_warshall_numpy(self._frame_graph,
                                            nodelist=frame_ids)
     # pack up into a nice DataFrame keyed on frame.name
     self._distances = pd.DataFrame(np_distances,
                                    index=frame_names,
                                    columns=frame_names)
     return self._distances

def get_clustering_results(graph, k):
    adj_matrix = networkx.adjacency_matrix(graph).toarray()
    dist_matrix = networkx.floyd_warshall_numpy(graph)
    # k = KDeterminant().get_best_k(matrix)
    return {
        # "AP dist euclidean": AP(dist_matrix, 'euclidean'),
        # "AP dist precomputed": AP(dist_matrix, 'precomputed'),
        # "AP adj euclidean": AP(adj_matrix, 'euclidean'),
        # "AP adj precomputed": AP(adj_matrix, 'precomputed')
        "Agglomerative": Agglomerative(dist_matrix, k),
        "K-means": K_means(dist_matrix, k),
        "Spectral": Spectral(adj_matrix, k)
    }

    def compute_distancematrix(self):
        """
        compute the normalized distance matrix.
        """
        self.distmat = nx.floyd_warshall_numpy(self.graph)

        if np.isinf(self.distmat).any():
            print "Warning: the graph is disconnected."
            self.maxdist = self.distmat[np.isfinite(self.distmat)].max()  # find the max among the finite elements
            df = np.nan_to_num(self.distmat)  # Replace INFINITY entries with some large finite float
            self.distmat = (df - df.min()) / (self.maxdist - self.distmat.min())  # this is ok for large floats
        else:
            self.maxdist = self.distmat.max()
            self.distmat = (self.distmat - self.distmat.min()) / (self.maxdist - self.distmat.min())

    def compare(self, g_1, g_2, verbose=False):
        """Compute the kernel value (similarity) between two graphs.

        Parameters
        ----------
        g1 : networkx.Graph
            First graph.
        g2 : networkx.Graph
            Second graph.

        Returns
        -------
        k : The similarity value between g1 and g2.
        """
        # Diagonal superior matrix of the floyd warshall shortest
        # paths:
        fwm1 = np.array(nx.floyd_warshall_numpy(g_1))
        fwm1 = np.where(fwm1 == np.inf, 0, fwm1)
        fwm1 = np.where(fwm1 == np.nan, 0, fwm1)
        fwm1 = np.triu(fwm1, k=1)
        bc1 = np.bincount(fwm1.reshape(-1).astype(int))

        fwm2 = np.array(nx.floyd_warshall_numpy(g_2))
        fwm2 = np.where(fwm2 == np.inf, 0, fwm2)
        fwm2 = np.where(fwm2 == np.nan, 0, fwm2)
        fwm2 = np.triu(fwm2, k=1)
        bc2 = np.bincount(fwm2.reshape(-1).astype(int))

        # Copy into arrays with the same length the non-zero shortests
        # paths:
        v1 = np.zeros(max(len(bc1), len(bc2)) - 1)
        v1[range(0, len(bc1)-1)] = bc1[1:]

        v2 = np.zeros(max(len(bc1), len(bc2)) - 1)
        v2[range(0, len(bc2)-1)] = bc2[1:]

        return np.sum(v1 * v2)

def generateAllPairsDistance(g, max_weight=27):
    '''
    Given connectivity graph g, this will return
    a numpy matrix that represents the all-pairs shortest path lengths
    using floyd-warshall algorithm. Since the edge weights of g represent
    affinities, a copy will be created that changes edges to be distances
    by subtracting the edge weight from the max_weight.
    g' has edge weights: W'(i,j) = max_weight - W(i,j) if i<>j, else 0.
    D = floyd_warshall_all_pairs(g')
    '''
    g2 = generateDistanceGraph(g, max_weight)
            
    print "Computing all-pairs shortest path distances..."
    D = nx.floyd_warshall_numpy(g2)
    return D

def initialize_rope(xyzs, plotting=False):
    pdists = ssd.squareform(ssd.pdist(xyzs))
    for (i_from, row) in enumerate(pdists):
        to_inds = np.flatnonzero(row[:i_from] < MAX_DIST)
        for i_to in to_inds:
            G.add_edge(i_from, i_to, weight = pdists[i_from, i_to])

    A = nx.floyd_warshall_numpy(G)
    A[np.isinf(A)] = 0
    (i_from_long, i_to_long) = np.unravel_index(A.argmax(), A.shape)
    path = nx.shortest_path(G, source=i_from_long, target=i_to_long)
    xyz_path = xyz[path,:]
    xyzs_unif = curves.unif_resample(total_path,N_CTRL_PTS,tol=.002)
    labels = np.ones(len(xyzs_unif),'int')
    labels[[1,-1]] = 2
    return xyzs_unif, labels