sort pairwise distance matrix

sort_pdist.py

# like https://gmarti.gitlab.io/ml/2017/09/07/how-to-sort-distance-matrix.html
# but using just 4 lines of code thanks to 'optimal_ordering' argument 
# added to scipy.cluster.hierarchy.linkage

import matplotlib.pyplot as plt
import numpy as np
from scipy.cluster.hierarchy import linkage

# distance matrix
m = np.zeros((500, 500))
m[:100, :100] = 1
m[100:150, 100:150] = 1
m[180:350, 180:350] = 1
m[400:490, 400:490] = 1
m[490:, 490:] = 1
m = 1 - m
m[np.arange(500), np.arange(500)] = 0

plt.figure()
plt.imshow(m)

# shuffle
perm = np.random.permutation(len(m))
m = m[perm][:, perm]

# reorder
y = m[np.triu_indices(len(m), k=1)]
Z = linkage(y, method='single', optimal_ordering=True)
perm = np.ravel(Z[:, :2]).astype(np.int32)
perm = perm[perm < len(m)]
m = m[perm][:, perm]

plt.figure()
plt.imshow(m)