Duplicated weights in K-nn approximation of Fermat distance

[facusapienza21]

When creating the k-nearest neighbors graph for the k-nn approximation of the Fermat distance, we compute the k-nn of each node and create the graph by doing

  def create_adj_matrix(self, distances):
      
      k = self.k
      n = distances.shape[0]
      
      rows = []
      columns = []
      values = []
      
      for i in range(n):
          smallest_values_and_columns = heapq.nsmallest(k, zip(distances[i].tolist(), list(range(n))))
          vs, cs = zip(*smallest_values_and_columns)

          rows.extend([i]*k)
          columns.extend(cs)
          values.extend(vs)
      
      return csr_matrix((values+values, (rows+columns, columns+rows)), shape=(n, n))

The last line of the code, after the return statement, duplicates some of the edges that results in not a redundant edge, but instead add both weights in the same edge. For example,

import fermat 
import numpy as np
from fermat.path_methods.dijkstra_method import DijkstraMethod
distances = np.array([[0,1,10], [1,0,10], [10, 10, 0]])

DM = DijkstraMethod(alpha=2, k=2)
DM.create_adj_matrix(distances).toarray()

will return a distance matrix with a 2 for the distance between the first two nodes, since the first and second node are both 2-nn of the other.

I currently solve this issue by replacing

csr_matrix((values+values, (rows+columns, columns+rows)), shape=(n, n))

by

return csr_matrix((values, (rows, columns)), shape=(n, n))

This change corresponds to commit 2aac722