From 8665fb2e2a84d824c8d5b6570f826626c37fb371 Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Tue, 8 Jun 2021 19:47:01 -0700 Subject: [PATCH] remove unused SparseMatrix_k_centers --- lib/sparse/SparseMatrix.c | 141 -------------------------------------- lib/sparse/SparseMatrix.h | 3 - 2 files changed, 144 deletions(-) diff --git a/lib/sparse/SparseMatrix.c b/lib/sparse/SparseMatrix.c index ad859df2e..59241a642 100644 --- a/lib/sparse/SparseMatrix.c +++ b/lib/sparse/SparseMatrix.c @@ -2872,147 +2872,6 @@ SparseMatrix SparseMatrix_complement(SparseMatrix A, int undirected){ return B; } -int SparseMatrix_k_centers(SparseMatrix D0, int weighted, int K, int root, int **centers, int centering, real **dist0){ - /* - Input: - D: the graph. If weighted, the entry values is used. - weighted: whether to treat the graph as weighted - K: the number of centers - root: the start node to find the k center. - centering: whether the distance should be centered so that sum_k dist[n*k+i] = 0 - Output: - centers: the list of nodes that form the k-centers. If centers = NULL on input, it will be allocated. - dist: of dimension k*n, dist[k*n: (k+1)*n) gives the distance of every node to the k-th center. - return: flag. if not zero, the graph is not connected, or out of memory. - */ - SparseMatrix D = D0; - int m = D->m, n = D->n; - int *levelset_ptr = NULL, *levelset = NULL, *mask = NULL; - int aggressive = FALSE; - int connectedQ, end1, end2; - enum {K_CENTER_DISCONNECTED = 1, K_CENTER_MEM}; - real *dist_min = NULL, *dist_sum = NULL, dmax, dsum; - real *dist = NULL; - int nlist, *list = NULL; - int flag = 0, i, j, k, nlevel; - int check_connected = FALSE; - - if (!SparseMatrix_is_symmetric(D, FALSE)){ - D = SparseMatrix_symmetrize(D, FALSE); - } - - assert(m == n); - - dist_min = MALLOC(sizeof(real)*n); - dist_sum = MALLOC(sizeof(real)*n); - for (i = 0; i < n; i++) dist_min[i] = -1; - for (i = 0; i < n; i++) dist_sum[i] = 0; - if (!(*centers)) *centers = MALLOC(sizeof(int)*K); - if (!(*dist0)) *dist0 = MALLOC(sizeof(real)*K*n); - if (!weighted){ - dist = MALLOC(sizeof(real)*n); - SparseMatrix_pseudo_diameter_unweighted(D, root, aggressive, &end1, &end2, &connectedQ); - if (check_connected && !connectedQ) { - flag = K_CENTER_DISCONNECTED; - goto RETURN; - } - root = end1; - for (k = 0; k < K; k++){ - (*centers)[k] = root; - // fprintf(stderr,"k = %d, root = %d\n",k, root+1); - SparseMatrix_level_sets(D, root, &nlevel, &levelset_ptr, &levelset, &mask, TRUE); - if (check_connected) assert(levelset_ptr[nlevel] == n); - for (i = 0; i < nlevel; i++) { - for (j = levelset_ptr[i]; j < levelset_ptr[i+1]; j++){ - (*dist0)[k*n+levelset[j]] = i; - if (k == 0){ - dist_min[levelset[j]] = i; - } else { - dist_min[levelset[j]] = MIN(dist_min[levelset[j]], i); - } - dist_sum[levelset[j]] += i; - } - } - - /* root = argmax_i min_roots dist(i, roots) */ - dmax = dist_min[0]; - dsum = dist_sum[0]; - root = 0; - for (i = 0; i < n; i++) { - if (!check_connected && dist_min[i] < 0) continue;/* if the graph is disconnected, then we can not count on every node to be in level set. - Usee dist_min<0 to identify those not in level set */ - if (dmax < dist_min[i] || (dmax == dist_min[i] && dsum < dist_sum[i])){/* tie break with avg dist */ - dmax = dist_min[i]; - dsum = dist_sum[i]; - root = i; - } - } - } - } else { - SparseMatrix_pseudo_diameter_weighted(D, root, aggressive, &end1, &end2, &connectedQ); - if (check_connected && !connectedQ) return K_CENTER_DISCONNECTED; - root = end1; - list = MALLOC(sizeof(int)*n); - - for (k = 0; k < K; k++){ - //fprintf(stderr,"k = %d, root = %d\n",k, root+1); - (*centers)[k] = root; - dist = &((*dist0)[k*n]); - flag = Dijkstra(D, root, dist, &nlist, list, &dmax); - if (flag){ - flag = K_CENTER_MEM; - goto RETURN; - } - if (check_connected) assert(nlist == n); - for (i = 0; i < n; i++){ - if (k == 0){ - dist_min[i] = dist[i]; - } else { - dist_min[i] = MIN(dist_min[i], dist[i]); - } - dist_sum[i] += dist[i]; - } - - /* root = argmax_i min_roots dist(i, roots) */ - dmax = dist_min[0]; - dsum = dist_sum[0]; - root = 0; - for (i = 0; i < n; i++) { - if (!check_connected && dist_min[i] < 0) continue;/* if the graph is disconnected, then we can not count on every node to be in level set. - Usee dist_min<0 to identify those not in level set */ - if (dmax < dist_min[i] || (dmax == dist_min[i] && dsum < dist_sum[i])){/* tie break with avg dist */ - dmax = dist_min[i]; - dsum = dist_sum[i]; - root = i; - } - } - } - dist = NULL; - } - - if (centering){ - for (i = 0; i < n; i++) dist_sum[i] /= k; - for (k = 0; k < K; k++){ - for (i = 0; i < n; i++){ - (*dist0)[k*n+i] -= dist_sum[i]; - } - } - } - - RETURN: - if (levelset_ptr) FREE(levelset_ptr); - if (levelset) FREE(levelset); - if (mask) FREE(mask); - - if (D != D0) SparseMatrix_delete(D); - if (dist) FREE(dist); - if (dist_min) FREE(dist_min); - if (dist_sum) FREE(dist_sum); - if (list) FREE(list); - return flag; - -} - SparseMatrix SparseMatrix_from_dense(int m, int n, real *x){ /* wrap a mxn matrix into a sparse matrix. the {i,j} entry of the matrix is in x[i*n+j], 0<=i