From 8c8f255d45d0aa95e7890c7ccf292472fdfb1119 Mon Sep 17 00:00:00 2001
From: Matthew Fernandez <matthew.fernandez@gmail.com>
Date: Wed, 14 Sep 2022 18:46:05 -0700
Subject: [PATCH] sparse: remove unused 'SparseMatrix_distance_matrix_khops'

---
 lib/sparse/SparseMatrix.c | 100 --------------------------------------
 lib/sparse/SparseMatrix.h |   1 -
 2 files changed, 101 deletions(-)

diff --git a/lib/sparse/SparseMatrix.c b/lib/sparse/SparseMatrix.c
index 256d95f29..4f1edfe8f 100644
--- a/lib/sparse/SparseMatrix.c
+++ b/lib/sparse/SparseMatrix.c
@@ -2413,103 +2413,3 @@ int SparseMatrix_distance_matrix(SparseMatrix D0, int weighted, double **dist0){
   free(list);
   return flag;
 }
-
-SparseMatrix SparseMatrix_distance_matrix_khops(int khops, SparseMatrix D0, int weighted){
-  /*
-    Input:
-    khops: number of hops allow. If khops < 0, this will give a dense distances. Otherwise it gives a sparse matrix that represent the k-neighborhood graph
-    D: the graph. If weighted, the entry values is used.
-    weighted: whether to treat the graph as weighted
-    Output:
-    DD: of dimension nxn. DD[i,j] gives the shortest path distance, subject to the fact that the short oath must be of <= khops.
-    return: flag. if not zero, the graph is not connected, or out of memory.
-  */
-  SparseMatrix D = D0, B, C;
-  int m = D->m, n = D->n;
-  int *levelset_ptr = NULL, *levelset = NULL, *mask = NULL;
-  double *dist = NULL;
-  int nlist, *list = NULL;
-  int flag = 0, i, j, k, itmp, nlevel;
-  double dmax, dtmp;
-
-  if (!SparseMatrix_is_symmetric(D, false)){
-    D = SparseMatrix_symmetrize(D, false);
-  }
-
-  assert(m == n);
- 
-  B = SparseMatrix_new(n, n, 1, MATRIX_TYPE_REAL, FORMAT_COORD);
-
-  if (!weighted){
-    for (k = 0; k < n; k++){
-      SparseMatrix_level_sets_khops(khops, D, k, &nlevel, &levelset_ptr, &levelset, &mask, TRUE);
-      for (i = 0; i < nlevel; i++) {
-	for (j = levelset_ptr[i]; j < levelset_ptr[i+1]; j++){
-	  itmp = levelset[j]; dtmp = i;
-	  if (k != itmp) B = SparseMatrix_coordinate_form_add_entry(B, k, itmp, &dtmp);
-	}
-      }
-     }
-  } else {
-    list = gv_calloc(n, sizeof(int));
-    dist = gv_calloc(n, sizeof(double));
-    /*
-    Dijkstra_khops(khops, D, 60, dist, &nlist, list, &dmax);
-    for (j = 0; j < nlist; j++){
-      fprintf(stderr,"{%d,%d}=%f,",60,list[j],dist[list[j]]);
-    }
-    fprintf(stderr,"\n");
-    Dijkstra_khops(khops, D, 94, dist, &nlist, list, &dmax);
-    for (j = 0; j < nlist; j++){
-      fprintf(stderr,"{%d,%d}=%f,",94,list[j],dist[list[j]]);
-    }
-    fprintf(stderr,"\n");
-    graphviz_exit(1);
-
-    */
-
-    for (k = 0; k < n; k++){
-      SparseMatrix_level_sets_khops(khops, D, k, &nlevel, &levelset_ptr, &levelset, &mask, FALSE);
-      assert(nlevel-1 <= khops);/* the first level is the root */
-      flag = Dijkstra_masked(D, k, dist, &nlist, list, &dmax, mask);
-      assert(!flag);
-      for (i = 0; i < nlevel; i++) {
-	for (j = levelset_ptr[i]; j < levelset_ptr[i+1]; j++){
-	  assert(mask[levelset[j]] == i+1);
-	  mask[levelset[j]] = -1;
-	}
-      }
-      for (j = 0; j < nlist; j++){
-	itmp = list[j]; dtmp = dist[itmp];
-	if (k != itmp) B = SparseMatrix_coordinate_form_add_entry(B, k, itmp, &dtmp);
-      }
-   }
-  }
-
-  C = SparseMatrix_from_coordinate_format(B);
-  SparseMatrix_delete(B);
-
-  free(levelset_ptr);
-  free(levelset);
-  free(mask);
-  free(dist);
-
-  if (D != D0) SparseMatrix_delete(D);
-  free(list);
-  /* I can not find a reliable way to make the matrix symmetric. Right now I use a mask array to
-     limit consider of only nodes with in k hops, but even this is not symmetric. e.g.,
-     . 10  10    10  10
-     .A---B---C----D----E
-     .           2 |    | 2
-     .             G----F
-     .               2
-     If we set hops = 4, and from A, it can not see F (which is 5 hops), hence distance(A,E) =40
-     but from E, it can see all nodes (all within 4 hops), so distance(E, A)=36.
-     .
-     may be there is a better way to ensure symmetric, but for now we just symmetrize it
-  */
-  D = SparseMatrix_symmetrize(C, false);
-  SparseMatrix_delete(C);
-  return D;
-
-}
diff --git a/lib/sparse/SparseMatrix.h b/lib/sparse/SparseMatrix.h
index a418f9237..527e1738e 100644
--- a/lib/sparse/SparseMatrix.h
+++ b/lib/sparse/SparseMatrix.h
@@ -106,7 +106,6 @@ SparseMatrix SparseMatrix_sort(SparseMatrix A);
 SparseMatrix SparseMatrix_set_entries_to_real_one(SparseMatrix A);
 
 int SparseMatrix_distance_matrix(SparseMatrix A, int weighted,  double **dist_matrix);
-SparseMatrix SparseMatrix_distance_matrix_khops(int khops, SparseMatrix A, int weighted);
 
 SparseMatrix SparseMatrix_from_dense(int m, int n, double *x);
 
-- 
2.40.0