main part of sort and conquer algorithm proposed by Ghosh et al

blog_vg_sort_and_conquer.py

def sort_and_conquer(x):
  '''Sort and conquer algorithm proposed by Ghosh et al.
  
    Parameters:
      x: numpy.array
        A 1d time series.
  '''
  n = x.size
  sortd = np.argsort(x)[::-1]
  graph = sparse.lil_matrix((n, n))
  for i in np.arange(n):
    current = sortd[i]
    connected = graph.rows[current]
    left = -1
    right = n
    for j in connected:
      if j < current:
        left = max(left, j)
      else:
        right = min(right, j)
    wvisibility(x, left, right, current, graph)
  return sparse.csr_matrix(graph)