All-Pairs-Shortest-Path computation based on Floyd's
algorithm {@cdk.cite FLO62}. It takes an nxn
matrix C of edge costs and produces an nxn matrix A of lengths of shortest
paths.

@param costMatrix edge cost matrix
@return the topological distance matrix
552089
public static int[][] computeFloydAPSP(double costMatrix[][]) {
        int nrow = costMatrix.length;
        int[][] distMatrix = new int[nrow][nrow];
        //logger.debug("Matrix size: " + n);
        for (int i = 0; i < nrow; i++) {
            for (int j = 0; j < nrow; j++) {
                if (costMatrix[i][j] == 0) {
                    distMatrix[i][j] = 0;
                } else {
                    distMatrix[i][j] = 1;
                }
            }
        }
        return computeFloydAPSP(distMatrix);
    }
621500
def compute_adjacency_matrix(X, method='auto', **kwargs):
    """"""
    if method == 'auto':
        if X.shape[0] > 10000:
            method = 'cyflann'
        else:
            method = 'kd_tree'
    return Adjacency.init(method, **kwargs).adjacency_graph(X.astype('float'))
1157354
public static DenseMatrix matrix(double[] A) {
        if (nlmatrixZeros != null) {
            try {
                return (DenseMatrix) nlmatrixArray.newInstance(A);
            } catch (Exception e) {
                logger.error("Failed to call NLMatrix(double[]): {}", e);
            }
        }

        return new JMatrix(A);
    }
643048
protected function pairwiseDistances(Matrix $samples) : Matrix
    {
        $distances = [];

        foreach ($samples as $a) {
            $temp = [];

            foreach ($samples as $b) {
                $temp[] = $this->kernel->compute($a, $b);
            }

            $distances[] = $temp;
        }

        return Matrix::quick($distances);
    }
944532
public double[][] buildBondMatrix() {
        int i, j, k, m;
        for (i = 0; i < nodeNumber; i++) {
            for (j = 1; j <= layerNumber; j++) {
                bondMatrix[i][j - 1] = 0.0;
                for (k = 0; k < nodeNumber; k++) {
                    if (j == 1) {
                        if (apspMatrix[i][k] == j) {
                            bondMatrix[i][j - 1] += adjaMatrix[i][k];
                        }
                    } else {
                        if (apspMatrix[i][k] == j) {
                            for (m = 0; m < nodeNumber; m++) {
                                if (apspMatrix[i][m] == (j - 1)) {
                                    bondMatrix[i][j - 1] += adjaMatrix[k][m];
                                }
                            }
                        }
                    }
                }
            }
        }
        return bondMatrix;
    }
202855
public org.tensorflow.framework.CostGraphDef.NodeOrBuilder getNodeOrBuilder(
      int index) {
    return node_.get(index);
  }
823928
def from_edge_pairs(pairs, num_vertices=None, symmetric=False, weights=None):
  '''
  '''
  if not symmetric:
    if weights is None:
      return EdgePairGraph(pairs, num_vertices=num_vertices)
    row, col = np.asarray(pairs).T
    row, weights = np.broadcast_arrays(row, weights)
    shape = None if num_vertices is None else (num_vertices, num_vertices)
    adj = ss.coo_matrix((weights, (row, col)), shape=shape)
    return SparseAdjacencyMatrixGraph(adj)
  # symmetric case
  G = SymmEdgePairGraph(pairs, num_vertices=num_vertices)
  if weights is None:
    return G
  # Convert to sparse adj graph with provided edge weights
  s = G.matrix('coo').astype(float)
  # shenanigans to assign edge weights in the right order
  flat_idx = np.ravel_multi_index(s.nonzero(), s.shape)
  r, c = np.transpose(pairs)
  rc_idx = np.ravel_multi_index((r,c), s.shape)
  cr_idx = np.ravel_multi_index((c,r), s.shape)
  order = np.argsort(flat_idx)
  flat_idx = flat_idx[order]
  s.data[order[np.searchsorted(flat_idx, rc_idx)]] = weights
  s.data[order[np.searchsorted(flat_idx, cr_idx)]] = weights
  return SparseAdjacencyMatrixGraph(s)
227397
public Matrix getIplus() {
        Matrix Iplus = new Matrix(size, size);
        int i, j;
        for (i = 0; i < size; i++)
            for (j = 0; j < size; j++)
                Iplus.matrix[i][j] = 0d;
        for (i = 1; i < size; i++)
            Iplus.matrix[i - 1][i] = Math.sqrt(J * J + J - (J - i + 1) * (J - i + 1) + (J - i + 1));
        return Iplus;
    }
1248122
public Assignments cluster(Matrix matrix, Properties props) { 
        if (matrix.rows() != matrix.columns()) 
            throw new IllegalArgumentException("Input matrix is not square. " +
                "Matrix is expected to be a square matrix whose values (i,j) " +
                "denote an edge from row i to row j");
        if (!(matrix instanceof SparseMatrix)) {
            throw new IllegalArgumentException("Input matrix must be a " +
                "sparse matrix.");
        }
        SparseMatrix sm = (SparseMatrix)matrix;

        String inMemProp =
            props.getProperty(KEEP_SIMILARITY_MATRIX_IN_MEMORY_PROPERTY);
        boolean keepSimMatrixInMem = (inMemProp != null) 
            ? Boolean.parseBoolean(inMemProp) : true;

        // IMPLEMENTATION NOTE: Ahn et al. used single-linkage HAC, which can be
        // efficiently implemented in O(n^2) time as a special case of HAC.
        // However, we currently don't optimize for this special case and
        // instead use our HAC class.  Because of the complexity of the edge
        // similarity function, we build our own similarity matrix and then pass
        // it in, rather than passing in the edge matrix directly.

        final int rows = sm.rows();
        numRows = rows;
        LOGGER.fine("Generating link similarity matrix for " + rows + " nodes");

        //  Rather than create an O(row^3) matrix for representing the edges,
        // compress the edge matrix by getting a mapping for each edge to a row
        // in the new matrix.
        final List<Edge> edgeList = new ArrayList<Edge>();
        this.edgeList = edgeList;

        for (int r = 0; r < rows; ++r) {
            SparseDoubleVector row = sm.getRowVector(r);
            int[] edges = row.getNonZeroIndices();
            for (int col : edges) {
                // Always add edges from the upper triangular
                if (r > col)
                    edgeList.add(new Edge(r, col));
                // Otherwise, we only add the edge from the lower triangular if
                // it wasn't present in the upper.  This avoids counting
                // duplicate edges.
                else if (r < col && sm.get(col, r) == 0)
                    edgeList.add(new Edge(r, col));
            }
        }

        final int numEdges = edgeList.size();
        LOGGER.fine("Number of edges to cluster: " + numEdges);
        
        Matrix edgeSimMatrix = 
            getEdgeSimMatrix(edgeList, sm, keepSimMatrixInMem);
        
        LOGGER.fine("Computing single linkage link clustering");

        final List<Merge> mergeOrder = 
            new HierarchicalAgglomerativeClustering().
                buildDendrogram(edgeSimMatrix, ClusterLinkage.SINGLE_LINKAGE);
        this.mergeOrder = mergeOrder;

        LOGGER.fine("Calculating partition densitities");

        // Set up a concurrent map that each thread will update once it has
        // calculated the densitites of each of its partitions.  This map is
        // only written to once per thread.
        final ConcurrentNavigableMap<Double,Integer> partitionDensities 
            = new ConcurrentSkipListMap<Double,Integer>();
        
        // Register a task group for calculating all of the partition
        // densitities
        Object key = workQueue.registerTaskGroup(mergeOrder.size());
        for (int p = 0; p < mergeOrder.size(); ++p) {
            final int part = p;
            workQueue.add(key, new Runnable() {
                    public void run() {
                        // Get the merges for this particular partitioning of
                        // the links
                        List<Merge> mergeSteps = mergeOrder.subList(0, part);
                        
                        // Convert the merges to a specific cluster labeling
                        MultiMap<Integer,Integer> clusterToElements = 
                            convertMergesToAssignments(mergeSteps, numEdges);

                        // Based on the link partitioning, calculate the
                        // partition density for each cluster
                        double partitionDensitySum = 0d;
                        for (Integer cluster : clusterToElements.keySet()) {
                            Set<Integer> linkPartition = 
                                clusterToElements.get(cluster);
                            int numLinks = linkPartition.size();
                            BitSet nodesInPartition = new BitSet(rows);
                            for (Integer linkIndex : linkPartition) {
                                Edge link = edgeList.get(linkIndex);
                                nodesInPartition.set(link.from);
                                nodesInPartition.set(link.to);
                            }
                            int numNodes = nodesInPartition.cardinality();
                            // This reflects the density of this particular
                            // cluster
                            double partitionDensity =
                                (numLinks - (numNodes - 1d))
                                / (((numNodes * (numNodes - 1d)) / 2d)
                                   - (numLinks - 1));                
                            partitionDensitySum += partitionDensity;
                        }
                        // Compute the density for the total partitioning
                        // solution
                        double partitionDensity = 
                            (2d / numEdges) * partitionDensitySum;
                        LOGGER.log(Level.FINER, "Partition solution {0} had "
                                   + "density {1}",
                                   new Object[] { part, partitionDensity });
                        
                        // Update the thread-shared partition density map with
                        // this task's calculation
                        partitionDensities.put(partitionDensity, part);
                        
                    }
                });
        }

        // Wait for all the partition densities to be calculated
        workQueue.await(key);

        Map.Entry<Double,Integer> densest = partitionDensities.lastEntry();
        LOGGER.fine("Partition " + densest.getValue() + 
                    " had the highest density: " + densest.getKey());
        int partitionWithMaxDensity = densest.getValue();

        // Select the solution with the highest partition density and assign
        // nodes accordingly
        MultiMap<Integer,Integer> bestEdgeAssignment =
            convertMergesToAssignments(
                mergeOrder.subList(0, partitionWithMaxDensity), numEdges);

        List<Set<Integer>> nodeClusters = new ArrayList<Set<Integer>>(rows);
        for (int i = 0; i < rows; ++i) 
            nodeClusters.add(new HashSet<Integer>());
        
        // Ignore the original partition labeling, and use our own cluster
        // labeling to ensure that the IDs are contiguous.
        int clusterId = 0;

        // For each of the partitions, add the partion's cluster ID to all the
        // nodes that are connected by one of the partition's edges
        for (Integer cluster : bestEdgeAssignment.keySet()) {
            Set<Integer> edgePartition = bestEdgeAssignment.get(cluster);
            for (Integer edgeId : edgePartition) {
                Edge e = edgeList.get(edgeId);
                nodeClusters.get(e.from).add(clusterId);
                nodeClusters.get(e.to).add(clusterId);
            }
            // Update the cluster id
            clusterId++;
        }

        int numClusters = 0;
        Assignment[] nodeAssignments = new Assignment[rows];
        for (int i = 0; i < nodeAssignments.length; ++i) {
            nodeAssignments[i] = 
                new SoftAssignment(nodeClusters.get(i));
        }
        return new Assignments(numClusters, nodeAssignments, matrix);
    }
428995
def _distance_matrix_generic(x, centering, exponent=1):
    """"""
    _check_valid_dcov_exponent(exponent)

    x = _transform_to_2d(x)

    # Calculate distance matrices
    a = distances.pairwise_distances(x, exponent=exponent)

    # Double centering
    a = centering(a, out=a)

    return a
142511
private boolean incrementalDistanceMatrixComputation(int from,int to,Bounds i) {
		logger.fine("Propagating (quad) with (#TPs,#cons) = (" + this.MAX_USED + "," + this.theNetwork.getConstraints().length + ") (call num.: " + (++quadPropCount) + ")");

		if (distance[to][from] != APSPSolver.INF && sum(i.max,distance[to][from]) < 0) return false;
		if (distance[from][to] != APSPSolver.INF && sum(-i.min,distance[from][to]) < 0) return false;
		
//		System.out.println("a)" + sum(i.max,distance[to][from]));
//		System.out.println("b)" + sum(-i.min,distance[from][to]));
		
		long sum1;
		long sum2;
		long sum3;
		long sum4;
		long temp;
		
		for (int u = 0; u < MAX_USED+1; u++) {
			if (tPoints[u].isUsed()) {
				for (int v = 0; v < MAX_USED+1;v++) {
					if (tPoints[v].isUsed()) {
						//min{distance[u][v];(distance[u][from]+i.max+distance[to][v]);(distance[u][to]-i.minl+distance[from][v])}
						sum1 = sum(distance[u][to],-i.min);
						sum2 = sum(sum1,distance[from][v]);
						sum3 = sum(distance[u][from],i.max);
						sum4 = sum(sum3,distance[to][v]);
						temp = Math.min(sum2,sum4);
												
						if (distance[u][v] > temp) {
							//long oldD = distance[u][v];
							distance[u][v] = temp;
							if (u == v && distance[u][v] != 0) {
								//logger.info("==================> Updated distance[" + u + "][" + v + "] from " + oldD + " to " + temp);
								//throw new Error("Found negative cycle in incremental propagation while adding (from,to,i) (" + from + "," + to + "," + i + ")");
								return false;
							}
						}
					}
				}
			}
		}
		return true;
	}
1060679
public DoubleVector[] chooseSeeds(int numCentroids, Matrix dataPoints) {
        int[] centroids = new int[numCentroids];
        // Select the first centroid randomly.
        DoubleVector[] centers = new DoubleVector[numCentroids];
        int centroidIndex = (int) Math.round(
                Math.random()*(dataPoints.rows()-1));
        centers[0] = dataPoints.getRowVector(centroidIndex);

        // Compute the distance each data point has with the first centroid.
        double[] distances = new double[dataPoints.rows()];
        computeDistances(distances, false, dataPoints, centers[0]);

        // For each of the remaining centroids, select one of the data points,
        // p, with probability
        // p(dist(p, last_centroid)^2/sum_p(dist(p, last_centroid)^2))
        // This is an attempt to pick the data point which is furthest away from
        // the previously selected data point.
        for (int i = 1; i < numCentroids; ++i) {
            double sum = distanceSum(distances);
            double probability = Math.random();
            centroidIndex = chooseWithProbability(distances, sum, probability);
            centers[i] = dataPoints.getRowVector(centroidIndex);
            computeDistances(distances, true, dataPoints, centers[i]);
        }

        return centers;
    }
227425
protected static void initializeDistanceMatrix(MatrixParadigm mat, DistanceQuery<?> dq, Linkage linkage) {
    final DBIDArrayIter ix = mat.ix, iy = mat.iy;
    final double[] matrix = mat.matrix;
    final boolean issquare = dq.getDistanceFunction().isSquared();
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Distance matrix computation", matrix.length, LOG) : null;
    int pos = 0;
    for(ix.seek(0); ix.valid(); ix.advance()) {
      final int x = ix.getOffset();
      assert (pos == MatrixParadigm.triangleSize(x));
      for(iy.seek(0); iy.getOffset() < x; iy.advance()) {
        matrix[pos++] = linkage.initial(dq.distance(ix, iy), issquare);
      }
      if(prog != null) {
        prog.setProcessed(pos, LOG);
      }
    }
    // Avoid logging errors in case scratch space was too large:
    if(prog != null) {
      prog.setProcessed(matrix.length, LOG);
    }
    LOG.ensureCompleted(prog);
  }
937483
private Matrix getThisSideMatrix(Matrix B)
    {
        if(this.canBeMutated())
            return this.clone();
        else//so far, only other option in JSAT is a dense matrix
        {
            DenseMatrix dm = new DenseMatrix(rows(), cols());
            dm.mutableAdd(this);
            return dm;
        }
    }
462156
public static DenseMatrix matrix(int nrows, int ncols, double value) {
        if (nlmatrixOnes != null) {
            try {
                return (DenseMatrix) nlmatrixOnes.newInstance(nrows, ncols, value);
            } catch (Exception e) {
                logger.error("Failed to call NLMatrix(int, int, double): {}", e);
            }
        }

        return new JMatrix(nrows, ncols, value);
    }
487570
protected static <I> double[][] computeSquaredDistanceMatrix(final List<I> col, PrimitiveDistanceFunction<? super I> dist) {
    final int size = col.size();
    double[][] imat = new double[size][size];
    boolean squared = dist.isSquared();
    FiniteProgress dprog = LOG.isVerbose() ? new FiniteProgress("Computing distance matrix", (size * (size - 1)) >>> 1, LOG) : null;
    for(int x = 0; x < size; x++) {
      final I ox = col.get(x);
      for(int y = x + 1; y < size; y++) {
        final I oy = col.get(y);
        double distance = dist.distance(ox, oy);
        distance *= squared ? -.5 : (-.5 * distance);
        imat[x][y] = imat[y][x] = distance;
      }
      if(dprog != null) {
        dprog.setProcessed(dprog.getProcessed() + size - x - 1, LOG);
      }
    }
    LOG.ensureCompleted(dprog);
    return imat;
  }
1271099
public double[][] buildTrialNodeMatrix(double[] weight) {
        int i, j, k;
        for (i = 0; i < nodeNumber; i++) {
            nodeMatrix[i][0] = weight[i + 1];
            for (j = 1; j <= layerNumber; j++) {
                nodeMatrix[i][j] = 0.0;
                for (k = 0; k < nodeNumber; k++) {
                    if (apspMatrix[i][k] == j) {
                        nodeMatrix[i][j] += weight[k + 1];
                    }
                }
            }
        }
        return nodeMatrix;
    }