02-StabilityOfClustering.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stability of Clustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Single Linkage Hierarchical Clustering Metric"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $(X,d_X)$ be a finite metric space. Recall that we defined the *Single Linkage Hierarchical Clustering metric* $u_X$ on $X$ by\n",
    "$$\n",
    "u_X(x,x') = \\inf\\{\\epsilon > 0 \\mid \\mbox{ there exists and $\\epsilon$-chain joining $x$ to $x'$}\\},\n",
    "$$\n",
    "where an $\\epsilon$-chain joining $x$ to $x'$ is a sequence \n",
    "$$\n",
    "x = x_1,x_2,\\ldots,x_n = x'\n",
    "$$\n",
    "such that $d_X(x_i,x_{i+1}) \\leq \\epsilon$ for all $i = 1,\\ldots,n-1$. \n",
    "\n",
    "It is easy to see that $u_X$ has the properties:\n",
    "- $u_X(x,x') \\geq 0$ and is equal to 0 if and only if $x = x'$, and\n",
    "- $u_X(x,x') = u_X(x',x)$\n",
    "- It takes slightly more work to show that $u_X$ satisfies the *strong triangle inequality*. That is, for all $x,x',x'' \\in X$, \n",
    "$$\n",
    "u_X(x,x'') \\leq \\max \\{u_X(x,x'),u_X(x',x'')\\}.\n",
    "$$\n",
    "This means that $u_X$ defines an *ultrametric* on $X$. \n",
    "\n",
    "One can represent $u_X$ using a *dendrogram*, which is the standard way to visualize hierarchical clustering, which we saw examples of last time. Let's look at a couple more examples..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the lecture notes, we did the following example 'by hand': let $X = \\{0,1,3,4,7,8\\}$, endowed with Euclidean distance $d_X$. Let's check that the output of the algorithm is the same as what I drew in the notes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0]\n",
      " [1]\n",
      " [3]\n",
      " [4]\n",
      " [7]\n",
      " [8]]\n"
     ]
    }
   ],
   "source": [
    "X = np.array([0,1,3,4,7,8]).reshape(6,1) # Datapoints\n",
    "# Each row should be a point in a Euclidean space, so the matrix should have shape 6x1 in this example.\n",
    "y = [0,1,3,4,7,8] # Labels for plotting.\n",
    "print(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAlMAAAEyCAYAAADeAVWKAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAARgElEQVR4nO3df4zkd33f8dcbnxNSDKGJr8U6+zhU3D9CU5ZwcklR1VOTKgZFWCqudFzDLyVayQQ1rugfJEqJ6kaqkKqQJnawtrJrQ3KElLj02jqN0pBr4I84nK01YBzQKVHqk21x2MTGAYwOvfvHDNVq2WPn7jN7M7v3eEijnZnv52bfWo28T39m5rvV3QEA4OK8YNEDAADsZmIKAGCAmAIAGCCmAAAGiCkAgAFiCgBgwL5FfeOrr766Dx06tKhvDwAwswcffPDL3b1/q2MLi6lDhw7l1KlTi/r2AAAzq6q/PN8xL/MBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAgG1jqqpeWFV/WlUPV9UjVfVvt1jzvVX10ao6XVUPVNWhnRgWAGDZzLIz9XySf9Ldr06ykuTGqnrdpjU/neQr3f3KJB9I8v75jgkAsJy2jameeG5688rppTctuynJvdPrH0vyY1VVc5sSAGBJzfTnZKrqiiQPJnllkju6+4FNSw4keSxJuvtcVT2T5AeTfHmOszJgbS05fnzRUwB70bFjyerqoqeAxZnpDejd/a3uXklybZIbqurvbVqy1S7U5t2rVNVqVZ2qqlNnz5698Gm5aMePJ+vri54C2GvW1/2PGlzQHzru7r+qqpNJbkzyuQ2HziS5LsmZqtqX5PuTPL3Fv19LspYkhw8f/o7YYmetrCQnTy56CmAvOXJk0RPA4s3yab79VfXS6fXvS/LjSf5s07ITSd4+vX5zkk90t1gCAPa8WXamrkly7/R9Uy9I8jvd/T+q6rYkp7r7RJK7kny4qk5nsiN1dMcmBgBYItvGVHd/Jslrtrj/fRuufyPJP5/vaAAAy88Z0AEABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAHbxlRVXVdVf1RVj1bVI1X1c1usOVJVz1TV+vTyvp0ZFwBgueybYc25JO/p7oeq6sVJHqyqP+juz29a98nu/sn5jwgAsLy23Znq7ie6+6Hp9a8meTTJgZ0eDABgN7ig90xV1aEkr0nywBaHf7SqHq6q36uqV81hNgCApTfLy3xJkqq6KsnvJrm1u5/ddPihJC/v7ueq6o1JPp7k+i0eYzXJapIcPHjwoocGAFgWM+1MVdWVmYTUb3X3fZuPd/ez3f3c9Pr9Sa6sqqu3WLfW3Ye7+/D+/fsHRwcAWLxZPs1XSe5K8mh3/8p51rxsui5VdcP0cZ+a56AAAMtolpf5Xp/krUk+W1Xr0/t+IcnBJOnuO5PcnOSWqjqX5OtJjnZ378C8AABLZduY6u5PJalt1tye5PZ5DQUAsFs4AzoAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBg25iqquuq6o+q6tGqeqSqfm6LNVVVv1ZVp6vqM1X1IzszLgDActk3w5pzSd7T3Q9V1YuTPFhVf9Ddn9+w5g1Jrp9e/kGSD06/AgDsadvuTHX3E9390PT6V5M8muTApmU3JflQT/xJkpdW1TVznxYAYMnMsjP1/1XVoSSvSfLApkMHkjy24faZ6X1PDMwGcGHW1pLjxxc9xeVl/VcnX4/cutg5LjfHjiWrq4uegqmZY6qqrkryu0lu7e5nNx/e4p/0Fo+xmmQ1SQ4ePHgBYwLM4PjxZH09WVlZ9CSXjZMrIuqSW1+ffBVTS2OmmKqqKzMJqd/q7vu2WHImyXUbbl+b5PHNi7p7Lclakhw+fPg7Ygtg2MpKcvLkoqeAnXPkyKInYJNZPs1XSe5K8mh3/8p5lp1I8rbpp/pel+SZ7vYSHwCw582yM/X6JG9N8tmqmu4t5heSHEyS7r4zyf1J3pjkdJKvJXnn/EcFAFg+28ZUd38qW78nauOaTvKz8xoKAGC3cAZ0AIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABiwbUxV1d1V9aWq+tx5jh+pqmeqan16ed/8xwQAWE77ZlhzT5Lbk3zou6z5ZHf/5FwmAgDYRbbdmeruP07y9CWYBQBg15nXe6Z+tKoerqrfq6pXnW9RVa1W1amqOnX27Nk5fWsAgMWZR0w9lOTl3f3qJL+e5OPnW9jda919uLsP79+/fw7fGgBgsYZjqruf7e7nptfvT3JlVV09PBkAwC4wHFNV9bKqqun1G6aP+dTo4wIA7Abbfpqvqj6S5EiSq6vqTJJfSnJlknT3nUluTnJLVZ1L8vUkR7u7d2xiAIAlsm1Mdfdbtjl+eyanTgAAuOw4AzoAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBg25iqqrur6ktV9bnzHK+q+rWqOl1Vn6mqH5n/mAAAy2mWnal7ktz4XY6/Icn108tqkg+OjwUAsDtsG1Pd/cdJnv4uS25K8qGe+JMkL62qa+Y1IADAMts3h8c4kOSxDbfPTO97Yg6PvXTWHlzL8c8eX/QYF2z9yV9Nkhy559YFT3Jxjv3wsay+dnXRY1w+1taS47vveZ719cnXI0cWOsZFO3YsWfU8v2Q8zxdjDz7P5xFTtcV9veXCqtVMXgrMwYMH5/CtL73jnz2e9SfXs/KylUWPckFW3rs7IypJ1p+c/IdDTF1Cx49P/oO9srue57tu3o2+/Qtyj/2SWWqe55feHn2ezyOmziS5bsPta5M8vtXC7l5LspYkhw8f3jK4doOVl63k5DtOLnqMy8aRe44seoTL08pKcvLkoqe4fOzWXYbdzvP80tqjz/N5nBrhRJK3TT/V97okz3T3nnyJDwBgs213pqrqI0mOJLm6qs4k+aUkVyZJd9+Z5P4kb0xyOsnXkrxzp4YFAFg228ZUd79lm+Od5GfnNhEAwC7iDOgAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMCAmWKqqm6sqi9U1emqeu8Wx99RVWeran16+Zn5jwoAsHz2bbegqq5IckeSf5rkTJJPV9WJ7v78pqUf7e5378CMAABLa5adqRuSnO7uP+/ubyb57SQ37exYAAC7wywxdSDJYxtun5net9mbq+ozVfWxqrpuLtMBACy5WWKqtrivN93+70kOdfffT/K/k9y75QNVrVbVqao6dfbs2QubFABgCc0SU2eSbNxpujbJ4xsXdPdT3f389OZ/SvLarR6ou9e6+3B3H96/f//FzAsAsFRmialPJ7m+ql5RVd+T5GiSExsXVNU1G26+Kcmj8xsRAGB5bftpvu4+V1XvTvL7Sa5Icnd3P1JVtyU51d0nkvzLqnpTknNJnk7yjh2cGQBgaWwbU0nS3fcnuX/Tfe/bcP3nk/z8fEcDAFh+zoAOADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMmCmmqurGqvpCVZ2uqvducfx7q+qj0+MPVNWheQ8KALCMto2pqroiyR1J3pDkh5K8pap+aNOyn07yle5+ZZIPJHn/vAcFAFhGs+xM3ZDkdHf/eXd/M8lvJ7lp05qbktw7vf6xJD9WVTW/MQEAltMsMXUgyWMbbp+Z3rflmu4+l+SZJD84jwEBAJbZvhnWbLXD1BexJlW1mmR1evO5qvrCDN9/KdU7bbxdan7mC2CD+dLzM7/0/Mwvvd35M3/5+Q7MElNnkly34fa1SR4/z5ozVbUvyfcneXrzA3X3WpK1Gb4nAMCuMMvLfJ9Ocn1VvaKqvifJ0SQnNq05keTt0+s3J/lEd3/HzhQAwF6z7c5Ud5+rqncn+f0kVyS5u7sfqarbkpzq7hNJ7kry4ao6ncmO1NGdHBoAYFmUDSQAgIvnDOgAAAPEFADAADEFADBATM2oqp7bdPlWVf36oufa66rqUFXdX1Vfqaonq+r26ek32CFV9QNV9V+r6q+r6i+r6tiiZ9rLqurdVXWqqp6vqnsWPc/loqp+s6qeqKpnq+qLVfUzi57pclFV11fVN6rqNxc9y7yIqRl191XfviT520m+nuS/LHisy8FvJPlSkmuSrCT5x0netdCJ9r47knwzk+f5v0jywap61WJH2tMeT/LLSe5e9CCXmX+f5FB3vyTJm5L8clW9dsEzXS7uyOS0S3uGmLo4N2fyC/6Tix7kMvCKJL/T3d/o7ieT/K8kfrHvkKp6UZI3J/k33f1cd38qk/PIvXWxk+1d3X1fd388yVOLnuVy0t2PdPfz3745vfydBY50Waiqo0n+KskfLnqWeRJTF+ftST7kxKSXxH9McrSq/kZVHUjyhkyCip3xd5N8q7u/uOG+hyNg2YOq6jeq6mtJ/izJE0nuX/BIe1pVvSTJbUnes+hZ5k1MXaCqOpjJS033LnqWy8T/yeQX+bOZ/NmiU0k+vtCJ9rarMvlD5Rs9k+TFC5gFdlR3vyuT5/Y/SnJfkue/+79g0L9Lcld3P7boQeZNTF24tyX5VHf/xaIH2euq6gWZnHn/viQvSnJ1kr+Z5P2LnGuPey7JSzbd95IkX13ALLDjuvtb05ezr01yy6Ln2auqaiXJjyf5wKJn2Qli6sK9LXalLpUfyOQPaN/e3c9391NJ/nOSNy52rD3ti0n2VdX1G+57dZJHFjQPXCr74j1TO+lIkkNJ/m9VPZnkXyd5c1U9tMih5kVMXYCq+odJDsSn+C6J7v5ykr9IcktV7auql2byfrWHFzvZ3tXdf53JTuBtVfWiqnp9kpuSfHixk+1d0+f2CzP526dXVNULnf5jZ1XV36qqo1V1VVVdUVU/keQtST6x6Nn2sLVMYnVlerkzyf9M8hOLHGpexNSFeXuS+7rbSx6Xzj9LcmOSs0lOJzmX5F8tdKK9711Jvi+TT6x+JMkt3W1nauf8YianWnlvkp+aXv/FhU6093UmL+mdSfKVJP8hya3d/d8WOtUe1t1f6+4nv33J5C0F3+jus4uebR78oWMAgAF2pgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAG/D82+5duLgQ7LgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from scipy.cluster.hierarchy import dendrogram, linkage  \n",
    "\n",
    "plt.figure(figsize=(10,5))\n",
    "linked = linkage(X)\n",
    "dendrogram(linked, labels = y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try a new example. Let $X \\subset \\mathbb{R}^2$ be the finite metric space $X = \\{(0,0),(2,0),(3,0),(0,3),(1,3),(3,3)\\}$, endowed with Euclidean distance. \n",
    "\n",
    "First, work out the dendrogram of $(X,u_X)$ 'by hand'. (Don't cheat by running the code below!)\n",
    "\n",
    "**** Break ****\n",
    "\n",
    "Now we can check our work computationally."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0]\n",
      " [2 0]\n",
      " [3 0]\n",
      " [0 3]\n",
      " [1 3]\n",
      " [3 3]]\n"
     ]
    }
   ],
   "source": [
    "X = np.array([[0,0],[2,0],[3,0],[0,3],[1,3],[3,3]])\n",
    "print(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAlMAAAEyCAYAAADeAVWKAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAARwElEQVR4nO3df4zk913f8dc7voMgnBCBr3HkHzloTNWkNJvk5AZFbVeFKo5F40qkknNpIBFoq4CBSPmjAUEoBgkhVQRB3Fhb2bLzY0NQSMMBRog2nCBIuDm7mziOk3CCUp9sK5c4+Ed+OL303T92Astmzzvnz6xndvfxkEaeme/nZt5ancbP+8zsd6q7AwDAU/OMeQ8AALCXiSkAgAFiCgBggJgCABggpgAABogpAIABh+b1xJdcckkfPXp0Xk8PADC1u+6663PdfWS7Y3OLqaNHj+bUqVPzenoAgKlV1V+f75i3+QAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGDAjjFVVc+sqv9ZVR+rqnur6he2WfPNVfX+qjpdVXdW1dHdGBYAYNFMszP1RJJ/1d0vTrKU5JqqevmWNT+S5Avd/YIkb0/yK7MdEwBgMe0YU73h8cnNw5NLb1l2XZLbJ9c/kOT7qqpmNiUAwIKa6utkquqiJHcleUGSm7r7zi1LLktyf5J097mqeiTJdyT53AxnZUGtriZra/OeAtiPjh9PVlbmPQU8uak+gN7dX+vupSSXJ7m6qv7JliXb7UJt3b1KVa1U1amqOnX27NkLn5aFtLaWrK/Pewpgv1lf9w819oYL+qLj7v6bqjqZ5Jokn9h06EySK5KcqapDSb4tycPb/PnVJKtJcuzYsW+ILfaupaXk5Ml5TwHsJ8vL854ApjPNb/MdqarnTK5/S5LvT/KpLctOJPnhyfXXJPlwd4slAGDfm2Zn6nlJbp98buoZSX6ru3+vqm5Mcqq7TyS5Jcm7q+p0Nnakrt+1iQEAFsiOMdXdH0/ykm3uf9um619J8u9mOxoAwOJzBnQAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGDAjjFVVVdU1R9X1X1VdW9V/dQ2a5ar6pGqWp9c3rY74wIALJZDU6w5l+Qt3X13VT0ryV1V9Ufd/ckt6/60u39g9iMCACyuHXemuvvB7r57cv2xJPcluWy3BwMA2Asu6DNTVXU0yUuS3LnN4e+tqo9V1R9U1YtmMBsAwMKb5m2+JElVXZzkt5O8ubsf3XL47iTP7+7Hq+raJB9KctU2j7GSZCVJrrzyyqc8NADAophqZ6qqDmcjpN7b3R/cery7H+3uxyfX70hyuKou2Wbdancf6+5jR44cGRwdAGD+pvltvkpyS5L7uvtXz7Pm0sm6VNXVk8f9/CwHBQBYRNO8zfeKJK9Pck9VrU/u+5kkVyZJd9+c5DVJ3lRV55J8Ocn13d27MC8AwELZMaa6+yNJaoc170jyjlkNBQCwVzgDOgDAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMGDHmKqqK6rqj6vqvqq6t6p+aps1VVW/XlWnq+rjVfXS3RkXAGCxHJpizbkkb+nuu6vqWUnuqqo/6u5PblrzqiRXTS7/LMk7J/8FANjXdtyZ6u4Hu/vuyfXHktyX5LIty65L8q7e8OdJnlNVz5v5tAAAC2aanam/VVVHk7wkyZ1bDl2W5P5Nt89M7ntwYLaFtHrXatbuWZv3GAtl/aFfS5Is3/bmOU+yeI5/z/GsvGxl3mOwF6yuJmteW/6e9Y3Xlix7bfkGx48nK15bFsXUMVVVFyf57SRv7u5Htx7e5o/0No+xkmQlSa688soLGHNxrN2zlvWH1rN06dK8R1kYS2/1Qred9YfWk0RMMZ21tWR9PVny2vJ1J5e8tmxrfeO1RUwtjqliqqoOZyOk3tvdH9xmyZkkV2y6fXmSB7Yu6u7VJKtJcuzYsW+Irb1i6dKlnHzDyXmPwYJbvm153iOw1ywtJSdPznsKFt3y8rwnYItpfpuvktyS5L7u/tXzLDuR5Icmv9X38iSPdPe+e4sPAGCraXamXpHk9UnuqarJ3mJ+JsmVSdLdNye5I8m1SU4n+VKSN85+VACAxbNjTHX3R7L9Z6I2r+kkPz6roQAA9gpnQAcAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAATvGVFXdWlWfrapPnOf4clU9UlXrk8vbZj8mAMBiOjTFmtuSvCPJu55kzZ929w/MZCIAgD1kx52p7v6TJA8/DbMAAOw5s/rM1PdW1ceq6g+q6kXnW1RVK1V1qqpOnT17dkZPDQAwP7OIqbuTPL+7X5zkN5J86HwLu3u1u49197EjR47M4KkBAOZrOKa6+9Hufnxy/Y4kh6vqkuHJAAD2gOGYqqpLq6om16+ePObnRx8XAGAv2PG3+arqfUmWk1xSVWeS/HySw0nS3TcneU2SN1XVuSRfTnJ9d/euTQwAsEB2jKnufu0Ox9+RjVMnAAAcOM6ADgAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADNgxpqrq1qr6bFV94jzHq6p+vapOV9XHq+qlsx8TAGAxTbMzdVuSa57k+KuSXDW5rCR55/hYAAB7w44x1d1/kuThJ1lyXZJ39YY/T/KcqnrerAYEAFhkh2bwGJcluX/T7TOT+x6cwWNDVu9azdo9a/Me44KtP7SeJFm+bXm+gzxFx7/neFZetjLvMWD3rK4ma3vvtSXrG68tWV6e6xhP2fHjycr+em2ZxQfQa5v7etuFVStVdaqqTp09e3YGT81BsHbP2t+GyV6ydOlSli5dmvcYT8n6Q+t7MmDhgqyt/V2Y7CVLSxuXvWh9fW8G7A5msTN1JskVm25fnuSB7RZ292qS1SQ5duzYtsEF21m6dCkn33By3mMcGHt1Nw0u2NJScvLkvKc4OPbqbtoOZrEzdSLJD01+q+/lSR7pbm/xAQAHwo47U1X1viTLSS6pqjNJfj7J4STp7puT3JHk2iSnk3wpyRt3a1gAgEWzY0x192t3ON5JfnxmEwEA7CHOgA4AMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAyYKqaq6pqq+nRVna6qt25z/A1Vdbaq1ieXH539qAAAi+fQTguq6qIkNyX510nOJPloVZ3o7k9uWfr+7r5hF2YEAFhY0+xMXZ3kdHf/ZXd/NclvJrlud8cCANgbpompy5Lcv+n2mcl9W/1gVX28qj5QVVfMZDoAgAU3TUzVNvf1ltu/m+Rod//TJP89ye3bPlDVSlWdqqpTZ8+evbBJAQAW0DQxdSbJ5p2my5M8sHlBd3++u5+Y3PyvSV623QN192p3H+vuY0eOHHkq8wIALJRpYuqjSa6qqu+sqm9Kcn2SE5sXVNXzNt18dZL7ZjciAMDi2vG3+br7XFXdkOQPk1yU5NbuvreqbkxyqrtPJPnJqnp1knNJHk7yhl2cGQBgYewYU0nS3XckuWPLfW/bdP2nk/z0bEcDAFh8zoAOADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMmCqmquqaqvp0VZ2uqrduc/ybq+r9k+N3VtXRWQ8KALCIdoypqrooyU1JXpXkhUleW1Uv3LLsR5J8obtfkOTtSX5l1oMCACyiaXamrk5yurv/sru/muQ3k1y3Zc11SW6fXP9Aku+rqprdmAAAi2mamLosyf2bbp+Z3Lftmu4+l+SRJN8xiwEBABbZoSnWbLfD1E9hTapqJcnK5ObjVfXpKZ5/IdUbbbw93fzMn35+5nNgU//p52f+9NubP/Pnn+/ANDF1JskVm25fnuSB86w5U1WHknxbkoe3PlB3ryZZneI5AQD2hGne5vtokquq6jur6puSXJ/kxJY1J5L88OT6a5J8uLu/YWcKAGC/2XFnqrvPVdUNSf4wyUVJbu3ue6vqxiSnuvtEkluSvLuqTmdjR+r63RwaAGBRlA0kAICnzhnQAQAGiCkAgAFiCgBggJi6AFX17VX136rqi1X111V1fN4z7WdVdUNVnaqqJ6rqtnnPcxBMvmfzlsnf78eq6n9V1avmPdd+V1Unq+orVfX45LJnz8G3V1TVe6rqwap6tKo+U1U/Ou+ZDoqqumry9/09855lVsTUhbkpyVeTPDfJ65K8s6peNN+R9rUHkvxSklvnPcgBcigb32bwL7NxvrifS/Jbvrz8aXFDd188ufyjeQ9zAPxykqPd/ewkr07yS1X1sjnPdFDclI3TLu0bYmpKVfWtSX4wyc919+Pd/ZFsnF/r9fOdbP/q7g9294eSfH7esxwU3f3F7v5P3f2/u/v/dffvJfmrJP4nw77S3fd29xNfvzm5/MM5jnQgVNX1Sf4myf+Y9yyzJKam991Jvtbdn9l038eS2Jli36qq52bj7/69857lAPjlqvpcVf1ZVS3Pe5iDoKr+S1V9KcmnkjyY5I45j7SvVdWzk9yY5C3znmXWxNT0Ls7GFzhv9kiSZ81hFth1VXU4yXuT3N7dn5r3PPvcf0zyXdn40vjVJL9bVXZJdll3/1g2XsP/eZIPJnniyf8Eg34xyS3dff+8B5k1MTW9x5M8e8t9z07y2BxmgV1VVc9I8u5sfEbwhjmPs+91953d/Vh3P9Hdtyf5syTXznuug6C7vzb52MblSd4073n2q6paSvL9Sd4+71l2wzRfdMyGzyQ5VFVXdfdfTO57cbz9wT5TVZWNr4h6bpJru/v/znmkg6iT1LyHOGAOxWemdtNykqNJ/s/GS0wuTnJRVb2wu186x7lmws7UlLr7i9nYBr6xqr61ql6R5Lps/OudXVBVh6rqmdn4TsiLquqZVeUfALvvnUn+cZJ/091fnvcw+11VPaeqXvn1v99V9bok/yIb34fKLqiqf1BV11fVxVV1UVW9Mslrk3x43rPtY6vZiNWlyeXmJL+f5JXzHGpWxNSF+bEk35Lks0nel+RN3W1navf8bJIvJ3lrkn8/uf6zc51on6uq5yf5D9l4sXto03mPXjfn0fazw9k4BcjZJJ9L8hNJ/m13O9fU7ulsvKV3JskXkvznJG/u7t+Z61T7WHd/qbsf+volGx+d+Up3n533bLPgi44BAAbYmQIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAY8P8BKmK20g1r1jQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(figsize=(10,5))\n",
    "linked = linkage(X)\n",
    "dendrogram(linked)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe that we have the same merging heights here as in the previous example, but that the dendrogram structures are different, due to the different clustering structures of the datasets. \n",
    "\n",
    "**Question:** Fix a set $X$ of $m$ points and consider an ultrametric $u_X$ taking a fixed set of $\\leq m-1$ heights. How many possible ultrametrics are there, considered up to isometry? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The previous two examples used finite metric spaces $(X,d_X)$ obtained as subsets of Euclidean spaces. However, our theory treats *general* finite metric spaces. \n",
    "\n",
    "Recall that we can represent a finite metric space by its *distance matrix*. For the previous example, we can construct its distance matrix as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.         2.         3.         3.         3.16227766 4.24264069]\n",
      " [2.         0.         1.         3.60555128 3.16227766 3.16227766]\n",
      " [3.         1.         0.         4.24264069 3.60555128 3.        ]\n",
      " [3.         3.60555128 4.24264069 0.         1.         3.        ]\n",
      " [3.16227766 3.16227766 3.60555128 1.         0.         2.        ]\n",
      " [4.24264069 3.16227766 3.         3.         2.         0.        ]]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAScAAAD4CAYAAACuRSAPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAUNUlEQVR4nO3df4xddZnH8feHAi1bFVbLapd2LQlEoyYiNkWC2SD+AmxgEzGBDSoG02gkYNbEyP6h0f+MibpG42ZUooiLGBBTWRDZQIMk/GqxVKC421UMXcDKT6lKoTOf/eOeqdPpzD1nOufO+U7P55WczL1zz/2eh4Y+/Z7vec55ZJuIiNIc1nUAEREzSXKKiCIlOUVEkZKcIqJISU4RUaTDRzHokVrqZSwfxdAH5cXjyoll0tLlL3YdQtEOP2yi6xAOcPyRz3cdwj6PPPoSTz49rvmM8d53LPdTT4832nfLtj032z5zPsebq5Ekp2Us5xS9cxRDH5TfXnpq1yEc4IRTftd1CEV75dI/dx3CAa5as6nrEPZZ995H5z3GU0+Pc8/N/9Bo3yUr/2fFvA84RyNJThFRPgMTlDdDnZTkFNFTxrzkZqd1XUhyiuixzJwiojjGjBd8+1qSU0SPTZDkFBGFMTCe5BQRJcrMKSKKY+ClgteccvtKRE8ZM95wa0LSEkm/lHTDDJ8tlXSNpB2S7pa0pm68JKeIvjKMN9waugzYPstnFwPP2D4B+ArwxbrBkpwiempQId5sqyNpFfA+4Nuz7HIu8L3q9bXAOyUNvTcwa04RvSXGaXzv8ApJm6e8H7M9NuX9V4FPAy+f5fvHAY8C2N4r6TngVcCTsx0wySmipwYL4o2T05O21870gaT1wC7bWySdPsv3ZzrQ0BPGRqd1ks6U9OtqMeszTb4TEWUb1Dmp0VbjNOAcSY8APwTOkHTVtH12AqsBJB0OHA08PWzQ2uQkaQnwDeAs4A3ABZLeUPe9iCjfhNVoG8b25bZX2V4DnA/cavvCabttBD5cvT6v2mfozKnJad06YIft3wBI+iGDxa2HGnw3Igo1OXMaFUlfADbb3gh8B/i+pB0MZkzn132/SXLat5BV2QmcMkMgG4ANAMv4mwbDRkSXjBhv+YK97U3Apur1Z6f8/gXgA3MZq0lyarSQVa3cjwG8Qq8st+w0IvapO2XrUpPktG8hq7IKeGw04UTEQjHiRS/pOoxZNUlO9wInSjoe+D8G54r/PNKoImLkBkWY5dZh1yanqmDqEuBmYAlwhe0HRx5ZRIzcKBfE56tREabtG4EbRxxLRCwgW4x7Ec+cIuLQNbHYZ04RcegZLIiXmwLKjSwiRmrRL4hHxKFrfJHXOUXEIWgUFeJtSnKK6LGJXK2LiNIMbvxNcoqIwhjx0iK/fSUiDkE2KcKMiBIpRZgRUR5T9syp3MgiYuTGOazRNoykZZLukXS/pAclfX6GfS6S9AdJW6vto3WxjWTm9OJxy/ntpaeOYuiDcvxn7uw6hAP8af26rkPYz4e+tLHrEPZz2zOv7zqEA1z4yOldh7DPb1/8ybzHMPXPB29oD3CG7d2SjgDukHST7bum7XeN7UuaDprTuoieGrSGmn8KqBoV7K7eHlFt834abk7rInqrWVuo6plPKyRtnrJt2G8kaYmkrcAu4Bbbd89wwPdL2ibpWkmrZ/h8P5k5RfSUmVOF+KxNNQFsjwMnSToGuF7Sm2w/MGWXnwJX294j6WMMWpOfMeyAmTlF9FhLTTX3sf0sg+4rZ077/VO291RvvwW8tW6sJKeInrLFhA9rtA0j6dhqxoSko4B3AQ9P22fllLfnANvr4stpXURPDRbEW7l9ZSXwvao7+GHAj2zfMK2p5qWSzgH2MmiqeVHdoElOEb3VzjPEbW8D3jLD76c21bwcuHwu4yY5RfTUYEE8t69ERIHyyJSIKE6LFeIjkeQU0WNpcBARxbHhpYkkp4gozOC0LskpIgo0l+rvhZbkFNFTpZcS1M7pJF0haZekB+r2jYjFpJ3bV0alyVG/y7Sb+CLi0DBRPUe8butC7Wmd7dslrRl9KBGxkAZX63rQGqp6+NQGgMOP+du2ho2IESm9CLO1k0nbY7bX2l67ZPnytoaNiBFa1Kd1EXFoKv1qXZJTRI+VXITZpJTgauBO4HWSdkq6ePRhRcSo2WKvD2u0daHJ1boLFiKQiFh4JZ/WlTuni4iRmlxzarIN07Dj71JJ10jaIenuJuVJSU4RPdZGcuKvHX/fDJwEnCnpbdP2uRh4xvYJwFeAL9YNmuQU0VOTdU7zTU4eqOv4ey6DXnUA1wLvlDR04CSniB6bQ53TfDv+Hgc8CmB7L/Ac8KphsaWUIKKnbNjb/GFz8+34O9Msafrsaj+ZOUX0WEtrTvvM1vEX2AmsBpB0OHA0g/51s0pyiuipttacmnT8BTYCH65enwfcanvozCmndRE95nbqnJp0/P0O8H1JOxjMmM6vGzTJKaLH2ript2HH3xeAD8xl3CSniJ6yy64QT3KK6C0xntZQEVGiltacRmIkyWnp8hc54ZTfjWLog/Kn9eu6DuEAy264p+sQ9nPx2BNdh1C86544uesQ9plDfdKs8jyniCiTB+tOpUpyiuixrh7B20SSU0RPOQviEVGqnNZFRJF6d7UuIspnJzlFRKFSShARRcqaU0QUx4iJXK2LiBIVPHFKcororSyIR0SxCp46JTlF9FjJM6dyV8MiYqQMTEyo0TaMpNWSbpO0ver4e9kM+5wu6TlJW6vtszONNVXtzEnSauBK4DXABDBm+9/qvhcRhTPQzsxpL/Ap2/dJejmwRdItth+att8vbK9vOmiT07qmB46IRaaNOifbjwOPV6+fl7SdQRPNeeWI2tM624/bvm/ywMDkgSNisXPDrabj7yRJaxg0O5je8RfgVEn3S7pJ0hvrQpvTgviwA1fBbgBY9uqXz2XYiOiE5rIgPrTjL4CklwHXAZ+0/cdpH98HvNb2bklnAz8BThw2XuMF8ZoDY3vM9lrba488+qimw0ZEl5rPnIaSdASD/PAD2z8+4DD2H23vrl7fCBwhacWwMRvNnOoOHBGLkME1V+KakCQGTTO32/7yLPu8Bvi9bUtax2Bi9NSwcZtcras9cEQsVq1crTsN+CDwK0lbq9/9K/APALb/nUEL8o9L2gv8BTi/jXbkMx64mppFxGLWztW6O6jJcra/Dnx9LuPWJqcmB46IRSq3r0REcdorwhyJJKeIHsvD5iKiTC1crRuVJKeIHlNmThFRnIYFll1JcoroLWVBPCIKlZlTRBRpousAZpfkFNFXqXOKiFLlal1ElKng5JQGBxFRpF7MnD70pY1dh3CAi8ee6DqE/bz370/qOoT9vLB+XdchHGD5p3Z2HULrcloXEeUxuX0lIgpV8Mwpa04RPSY324aO0ayppiR9TdIOSdsknVwXW2ZOEX3WzsypSW/Lsxh0WzkROAX4ZvVzVpk5RfRZC91XGva2PBe40gN3AcdIWjls3MycInqqySnbFCskbZ7yfsz22AFjzt7b8jjg0Snvd1a/e3y2AyY5RfRZ86t1822qOdOB5t19JSIOUW3VOTXobbkTWD3l/SrgsWFjZs0pos9aWHNq2NtyI/Ch6qrd24DnbM96SgeZOUX019zWnIZp0lTzRuBsYAfwZ+AjdYMmOUX02cI11TTwibmMm+QU0WMq+GFzWXOKiCJl5hTRZwXfW1ebnCQtA24Hllb7X2v7c6MOLCJGrL0F8ZFoMnPaA5xhe3dVy3CHpJuqEvSIWMwWc3KqVtl3V2+PqLaC/5MiorGC/yY3WhCXtKSqX9gF3GJ7+n0zSNogabOkzS8+95e244yIlonB1bomWxcaJSfb47ZPYlByvk7Sm2bYZ8z2Wttrjzz6qLbjjIi2NXyWU1frUnMqJbD9LLAJOHMk0UTEwmrh9pVRqU1Oko6VdEz1+ijgXcDDow4sIhZAwcmpydW6lcD3JC1hkMx+ZPuG0YYVEQthUZcS2N7G4OFREXGoWczJKSIOUS773rokp4g+y8wpIkq0qNecIuIQluQUEcXpsEygiTzPKaKnRHsV4pKukLRL0gOzfH66pOckba22z9aNmZlTRI+1uOb0XeDrwJVD9vmF7fVNB8zMKaLPWqoQt3078HSboSU5RfRZ8+S0YvKpI9W24SCOdqqk+yXdJOmNdTvntC6ir+b2xIHajr817gNeWz208mzgJ8CJw76QmVNEny3Qjb+2/2h7d/X6RuAISSuGfSczp4geW6jbVyS9Bvi9bUtax2Bi9NSw74wkOR1+2ASvXPrnUQx9UG575vVdh1C8F9av6zqE/Sy74Z6uQzjAjref2nUI++z505GtjNPW1TpJVwOnM1ib2gl8jsEjvSc7/p4HfFzSXuAvwPnVI8BnlZlTRF+1WIRp+4Kaz7/OoNSgsSSniD4ruEI8ySmipyYrxEuV5BTRY5ooNzslOUX0VeE3/iY5RfRYTusiokxJThFRosycIqJMSU4RUZx0X4mIEqXOKSLKNfz2tk4lOUX0WGZOEVGewoswGz9sTtISSb+UdMMoA4qIhaOJZlsX5jJzugzYDrxiRLFExAIr+Wpdo5mTpFXA+4BvjzaciFgwZrAg3mTrQNPTuq8CnwZmzbOSNkx2Znjh2RdaCS4iRmsBm2pK0tck7ZC0TdLJdWPWJidJ64FdtrcM28/2mO21ttcuO2ZZ3bARUYL2Ghx8FzhzyOdnMei2ciKwAfhm3YBNZk6nAedIegT4IXCGpKsafC8iCtZmO/IGTTXPBa70wF3AMZJWDhuzNjnZvtz2KttrgPOBW21fWB9uRBTNRhPNthYcBzw65f3O6nezSp1TRJ81zzsrJG2e8n7M9tgcjqS5Hn1Oycn2JmDTXL4TEeVawI6/O4HVU96vAh4b9oV0/I3oKwMTbrbN30bgQ9VVu7cBz9l+fNgXcloX0WcL11TzRuBsYAfwZ+AjdWMmOUX0WFs3/jZoqmngE3MZM8kposfSGioiylP4UwmSnCJ6alCEWW52SnKK6LOCn0qQ5BTRY5k5RUR5suYUEWVq7b65kUhyiuiznNZFRHHSVDMiitW3mdPxRz7PVWs2jWLog3LhI6d3HcIBrnui9imlC2r5p3Z2HcJ+drz91K5DOMDxn7mz6xD22eU/tTNQubkpM6eIPtNEued1SU4RfWVShBkR5RFOEWZEFCrJKSKKlOQUEcUpfM0pzxCP6DFNTDTaaseRzpT066qj72dm+PwiSX+QtLXaPlo3ZmZOEb3lVk7rJC0BvgG8m0GXlXslbbT90LRdr7F9SdNxM3OK6CszSE5NtuHWATts/8b2iww6g5873/CSnCL6bKLhVjXVnLJtmDJK026+75e0TdK1klbP8Pl+cloX0WNzqHMa1lSzSTffnwJX294j6WPA94Azhh0wM6eIPmvntK62m6/tp2zvqd5+C3hr3aBJThF9ZcP4RLNtuHuBEyUdL+lI4HwGHX73kbRyyttzgO11g+a0LqLPWrhaZ3uvpEuAm4ElwBW2H5T0BWCz7Y3ApZLOAfYCTwMX1Y3bKDlJegR4HhgH9g4594yIxaSlCnHbNzJoOT71d5+d8vpy4PK5jDmXmdM7bD85l8EjomAG8gzxiCiPweXev9J0QdzAzyVtmVbfsI+kDZM1EH94ary9CCNiNExbC+Ij0XTmdJrtxyT9HXCLpIdt3z51B9tjwBjA2jcvK3euGBF/VfBTCRrNnGw/Vv3cBVzPoFw9Iha7duqcRqI2OUlaLunlk6+B9wAPjDqwiBi1hompo+TU5LTu1cD1kib3/w/bPxtpVBExegYWc4MD278B3rwAsUTEQit4zSmlBBG95c6uxDWR5BTRVwYXXOeU5BTRZ6kQj4giZc0pIopjL+6rdRFxCMvMKSLKYzxe7n2wSU4RfZVHpkREsQouJcgzxCN6yoAn3Gir06Dj71JJ11Sf3y1pTd2YSU4RfeXqYXNNtiGmdPw9C3gDcIGkN0zb7WLgGdsnAF8BvlgXXpJTRI95fLzRVqNJx99zGfSqA7gWeKeqpwnMZiRrTlu27Xlyycodv2thqBVAC88t3zH/IQZaiqc1iadeazH9bxuDtBfPa+c7wPM8c/N/+doVDXdfJmnzlPdj1QMmYeaOv6dM+/6+fapuLc8Br2LIn8VIkpPtY9sYR9Lmkjq9JJ7hSosHyouppHhsn9nSUE06/jbZZz85rYuI+art+Dt1H0mHA0cz6F83qySniJiv2o6/1fsPV6/PA261h5enl17nNFa/y4JKPMOVFg+UF1Np8cxbw46/3wG+L2kHgxnT+XXjqiZ5RUR0Iqd1EVGkJKeIKFKRyamuFL6DeK6QtEtSES2xJK2WdJuk7ZIelHRZx/Esk3SPpPureD7fZTyTJC2R9EtJN3QdC4CkRyT9StLWaTVDMYPi1pyqUvj/Bt7N4PLjvcAFth/qMKZ/BHYDV9p+U1dxTIlnJbDS9n1VT8EtwD919WdUVfout71b0hHAHcBltu/qIp4pcf0LsBZ4he31XcZSxfMIsNZ2aYWqRSpx5tSkFH5BVa3Xh9ZkLCTbj9u+r3r9PLCdQQVuV/HY9u7q7RHV1um/epJWAe8Dvt1lHHHwSkxOM5XCd/YXr3TV3d1vAe7uOI4lkrYCu4BbbHcaD/BV4NNASc8EMfBzSVskbeg6mNKVmJzmXObeV5JeBlwHfNL2H7uMxfa47ZMYVAevk9TZ6a+k9cAu21u6imEWp9k+mcHd+5+olgtiFiUmpyal8L1Xre1cB/zA9o+7jmeS7WeBTUBb920djNOAc6o1nh8CZ0i6qsN4ALD9WPVzF3A9gyWMmEWJyalJKXyvVQvQ3wG22/5yAfEcK+mY6vVRwLuAh7uKx/bltlfZXsPg/59bbV/YVTwAkpZXFy+QtBx4D1DE1d9SFZecbO8FJkvhtwM/sv1glzFJuhq4E3idpJ2SLu4yHgYzgw8ymBFsrbazO4xnJXCbpG0M/nG5xXYRl+8L8mrgDkn3A/cA/2n7Zx3HVLTiSgkiIqDAmVNEBCQ5RUShkpwiokhJThFRpCSniChSklNEFCnJKSKK9P8vkffmgdi7BQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.metrics import pairwise_distances\n",
    "\n",
    "D = pairwise_distances(X)\n",
    "print(D)\n",
    "\n",
    "plt.imshow(D)\n",
    "plt.colorbar()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So any collection of points in some Euclidean space $\\mathbb{R}^n$ gives rise to a distance matrix, as above. This distance matrix can be used as input to the hierarchical clustering algorithm, but we need to convert to a 'non-redundant' form to pass into the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAlMAAAEyCAYAAADeAVWKAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAARwElEQVR4nO3df4zk913f8dc7voMgnBCBr3HkHzloTNWkNJvk5AZFbVeFKo5F40qkknNpIBFoq4CBSPmjAUEoBgkhVQRB3Fhb2bLzY0NQSMMBRog2nCBIuDm7mziOk3CCUp9sK5c4+Ed+OL303T92Astmzzvnz6xndvfxkEaeme/nZt5ancbP+8zsd6q7AwDAU/OMeQ8AALCXiSkAgAFiCgBggJgCABggpgAABogpAIABh+b1xJdcckkfPXp0Xk8PADC1u+6663PdfWS7Y3OLqaNHj+bUqVPzenoAgKlV1V+f75i3+QAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGDAjjFVVc+sqv9ZVR+rqnur6he2WfPNVfX+qjpdVXdW1dHdGBYAYNFMszP1RJJ/1d0vTrKU5JqqevmWNT+S5Avd/YIkb0/yK7MdEwBgMe0YU73h8cnNw5NLb1l2XZLbJ9c/kOT7qqpmNiUAwIKa6utkquqiJHcleUGSm7r7zi1LLktyf5J097mqeiTJdyT53AxnZUGtriZra/OeAtiPjh9PVlbmPQU8uak+gN7dX+vupSSXJ7m6qv7JliXb7UJt3b1KVa1U1amqOnX27NkLn5aFtLaWrK/Pewpgv1lf9w819oYL+qLj7v6bqjqZ5Jokn9h06EySK5KcqapDSb4tycPb/PnVJKtJcuzYsW+ILfaupaXk5Ml5TwHsJ8vL854ApjPNb/MdqarnTK5/S5LvT/KpLctOJPnhyfXXJPlwd4slAGDfm2Zn6nlJbp98buoZSX6ru3+vqm5Mcqq7TyS5Jcm7q+p0Nnakrt+1iQEAFsiOMdXdH0/ykm3uf9um619J8u9mOxoAwOJzBnQAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGDAjjFVVVdU1R9X1X1VdW9V/dQ2a5ar6pGqWp9c3rY74wIALJZDU6w5l+Qt3X13VT0ryV1V9Ufd/ckt6/60u39g9iMCACyuHXemuvvB7r57cv2xJPcluWy3BwMA2Asu6DNTVXU0yUuS3LnN4e+tqo9V1R9U1YtmMBsAwMKb5m2+JElVXZzkt5O8ubsf3XL47iTP7+7Hq+raJB9KctU2j7GSZCVJrrzyyqc8NADAophqZ6qqDmcjpN7b3R/cery7H+3uxyfX70hyuKou2Wbdancf6+5jR44cGRwdAGD+pvltvkpyS5L7uvtXz7Pm0sm6VNXVk8f9/CwHBQBYRNO8zfeKJK9Pck9VrU/u+5kkVyZJd9+c5DVJ3lRV55J8Ocn13d27MC8AwELZMaa6+yNJaoc170jyjlkNBQCwVzgDOgDAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMGDHmKqqK6rqj6vqvqq6t6p+aps1VVW/XlWnq+rjVfXS3RkXAGCxHJpizbkkb+nuu6vqWUnuqqo/6u5PblrzqiRXTS7/LMk7J/8FANjXdtyZ6u4Hu/vuyfXHktyX5LIty65L8q7e8OdJnlNVz5v5tAAAC2aanam/VVVHk7wkyZ1bDl2W5P5Nt89M7ntwYLaFtHrXatbuWZv3GAtl/aFfS5Is3/bmOU+yeI5/z/GsvGxl3mOwF6yuJmteW/6e9Y3Xlix7bfkGx48nK15bFsXUMVVVFyf57SRv7u5Htx7e5o/0No+xkmQlSa688soLGHNxrN2zlvWH1rN06dK8R1kYS2/1Qred9YfWk0RMMZ21tWR9PVny2vJ1J5e8tmxrfeO1RUwtjqliqqoOZyOk3tvdH9xmyZkkV2y6fXmSB7Yu6u7VJKtJcuzYsW+Irb1i6dKlnHzDyXmPwYJbvm153iOw1ywtJSdPznsKFt3y8rwnYItpfpuvktyS5L7u/tXzLDuR5Icmv9X38iSPdPe+e4sPAGCraXamXpHk9UnuqarJ3mJ+JsmVSdLdNye5I8m1SU4n+VKSN85+VACAxbNjTHX3R7L9Z6I2r+kkPz6roQAA9gpnQAcAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAAWIKAGCAmAIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAYIKYAAAaIKQCAATvGVFXdWlWfrapPnOf4clU9UlXrk8vbZj8mAMBiOjTFmtuSvCPJu55kzZ929w/MZCIAgD1kx52p7v6TJA8/DbMAAOw5s/rM1PdW1ceq6g+q6kXnW1RVK1V1qqpOnT17dkZPDQAwP7OIqbuTPL+7X5zkN5J86HwLu3u1u49197EjR47M4KkBAOZrOKa6+9Hufnxy/Y4kh6vqkuHJAAD2gOGYqqpLq6om16+ePObnRx8XAGAv2PG3+arqfUmWk1xSVWeS/HySw0nS3TcneU2SN1XVuSRfTnJ9d/euTQwAsEB2jKnufu0Ox9+RjVMnAAAcOM6ADgAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADNgxpqrq1qr6bFV94jzHq6p+vapOV9XHq+qlsx8TAGAxTbMzdVuSa57k+KuSXDW5rCR55/hYAAB7w44x1d1/kuThJ1lyXZJ39YY/T/KcqnrerAYEAFhkh2bwGJcluX/T7TOT+x6cwWNDVu9azdo9a/Me44KtP7SeJFm+bXm+gzxFx7/neFZetjLvMWD3rK4ma3vvtSXrG68tWV6e6xhP2fHjycr+em2ZxQfQa5v7etuFVStVdaqqTp09e3YGT81BsHbP2t+GyV6ydOlSli5dmvcYT8n6Q+t7MmDhgqyt/V2Y7CVLSxuXvWh9fW8G7A5msTN1JskVm25fnuSB7RZ292qS1SQ5duzYtsEF21m6dCkn33By3mMcGHt1Nw0u2NJScvLkvKc4OPbqbtoOZrEzdSLJD01+q+/lSR7pbm/xAQAHwo47U1X1viTLSS6pqjNJfj7J4STp7puT3JHk2iSnk3wpyRt3a1gAgEWzY0x192t3ON5JfnxmEwEA7CHOgA4AMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAyYKqaq6pqq+nRVna6qt25z/A1Vdbaq1ieXH539qAAAi+fQTguq6qIkNyX510nOJPloVZ3o7k9uWfr+7r5hF2YEAFhY0+xMXZ3kdHf/ZXd/NclvJrlud8cCANgbpompy5Lcv+n2mcl9W/1gVX28qj5QVVfMZDoAgAU3TUzVNvf1ltu/m+Rod//TJP89ye3bPlDVSlWdqqpTZ8+evbBJAQAW0DQxdSbJ5p2my5M8sHlBd3++u5+Y3PyvSV623QN192p3H+vuY0eOHHkq8wIALJRpYuqjSa6qqu+sqm9Kcn2SE5sXVNXzNt18dZL7ZjciAMDi2vG3+br7XFXdkOQPk1yU5NbuvreqbkxyqrtPJPnJqnp1knNJHk7yhl2cGQBgYewYU0nS3XckuWPLfW/bdP2nk/z0bEcDAFh8zoAOADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMmCqmquqaqvp0VZ2uqrduc/ybq+r9k+N3VtXRWQ8KALCIdoypqrooyU1JXpXkhUleW1Uv3LLsR5J8obtfkOTtSX5l1oMCACyiaXamrk5yurv/sru/muQ3k1y3Zc11SW6fXP9Aku+rqprdmAAAi2mamLosyf2bbp+Z3Lftmu4+l+SRJN8xiwEBABbZoSnWbLfD1E9hTapqJcnK5ObjVfXpKZ5/IdUbbbw93fzMn35+5nNgU//p52f+9NubP/Pnn+/ANDF1JskVm25fnuSB86w5U1WHknxbkoe3PlB3ryZZneI5AQD2hGne5vtokquq6jur6puSXJ/kxJY1J5L88OT6a5J8uLu/YWcKAGC/2XFnqrvPVdUNSf4wyUVJbu3ue6vqxiSnuvtEkluSvLuqTmdjR+r63RwaAGBRlA0kAICnzhnQAQAGiCkAgAFiCgBggJi6AFX17VX136rqi1X111V1fN4z7WdVdUNVnaqqJ6rqtnnPcxBMvmfzlsnf78eq6n9V1avmPdd+V1Unq+orVfX45LJnz8G3V1TVe6rqwap6tKo+U1U/Ou+ZDoqqumry9/09855lVsTUhbkpyVeTPDfJ65K8s6peNN+R9rUHkvxSklvnPcgBcigb32bwL7NxvrifS/Jbvrz8aXFDd188ufyjeQ9zAPxykqPd/ewkr07yS1X1sjnPdFDclI3TLu0bYmpKVfWtSX4wyc919+Pd/ZFsnF/r9fOdbP/q7g9294eSfH7esxwU3f3F7v5P3f2/u/v/dffvJfmrJP4nw77S3fd29xNfvzm5/MM5jnQgVNX1Sf4myf+Y9yyzJKam991Jvtbdn9l038eS2Jli36qq52bj7/69857lAPjlqvpcVf1ZVS3Pe5iDoKr+S1V9KcmnkjyY5I45j7SvVdWzk9yY5C3znmXWxNT0Ls7GFzhv9kiSZ81hFth1VXU4yXuT3N7dn5r3PPvcf0zyXdn40vjVJL9bVXZJdll3/1g2XsP/eZIPJnniyf8Eg34xyS3dff+8B5k1MTW9x5M8e8t9z07y2BxmgV1VVc9I8u5sfEbwhjmPs+91953d/Vh3P9Hdtyf5syTXznuug6C7vzb52MblSd4073n2q6paSvL9Sd4+71l2wzRfdMyGzyQ5VFVXdfdfTO57cbz9wT5TVZWNr4h6bpJru/v/znmkg6iT1LyHOGAOxWemdtNykqNJ/s/GS0wuTnJRVb2wu186x7lmws7UlLr7i9nYBr6xqr61ql6R5Lps/OudXVBVh6rqmdn4TsiLquqZVeUfALvvnUn+cZJ/091fnvcw+11VPaeqXvn1v99V9bok/yIb34fKLqiqf1BV11fVxVV1UVW9Mslrk3x43rPtY6vZiNWlyeXmJL+f5JXzHGpWxNSF+bEk35Lks0nel+RN3W1navf8bJIvJ3lrkn8/uf6zc51on6uq5yf5D9l4sXto03mPXjfn0fazw9k4BcjZJJ9L8hNJ/m13O9fU7ulsvKV3JskXkvznJG/u7t+Z61T7WHd/qbsf+volGx+d+Up3n533bLPgi44BAAbYmQIAGCCmAAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYICYAgAY8P8BKmK20g1r1jQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import scipy.spatial.distance as ssd\n",
    "\n",
    "distArray = ssd.squareform(D) \n",
    "\n",
    "plt.figure(figsize=(10,5))\n",
    "linked = linkage(distArray)\n",
    "dendrogram(linked)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On the other hand, a general distance matrix does not need to arise from a collection of points in $\\mathbb{R}^n$. Consider the matrix defined below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1 2 3]\n",
      " [1 0 3 4]\n",
      " [2 3 0 5]\n",
      " [3 4 5 0]]\n"
     ]
    }
   ],
   "source": [
    "D = np.array([[0, 1, 2, 3],\n",
    "              [1, 0, 3, 4],\n",
    "              [2, 3, 0, 5],\n",
    "              [3, 4, 5, 0]])\n",
    "\n",
    "print(D)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question:** How can we tell that `D` is really a distance matrix?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 0, 0, 0],\n",
       "       [0, 0, 0, 0],\n",
       "       [0, 0, 0, 0],\n",
       "       [0, 0, 0, 0]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D - D.T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This distance matrix is *non-Euclidean*; i.e., there is no way to embed four points into $\\mathbb{R}^n$ (for any $n$) such that the distance matrix of the result is equal to `D`.\n",
    "\n",
    "**Exercise:** See if you can *prove* that this matrix is non-Euclidean. In general, this is a difficult task, but it's not so hard to see for this simple example!\n",
    "\n",
    "We can still pass this non-Euclidean distance matrix into the hierarchical clustering algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAlMAAAEyCAYAAADeAVWKAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAQQ0lEQVR4nO3dW6zlZXnH8d8Dg4eIhyhTIZzGVEyrtY46oRrTdFJrRGPlQpogiadodmMl1cQbNKkH0qTxRhurlWwDAS3jIUrN1GKMjU7UC6kzuAERNROrZQLEESwHtdixTy/2qt3d7mEveNew1h4+n2SH9f//373Wc7FDvvOuU3V3AAB4aE6Y9wAAAFuZmAIAGCCmAAAGiCkAgAFiCgBggJgCABiwbV4PfMopp/SOHTvm9fAAAFM7cODAT7p7+0bX5hZTO3bsyP79++f18AAAU6uqHx3tmqf5AAAGiCkAgAFiCgBggJgCABggpgAABogpAIABYgoAYMCmMVVVj6mqf62qG6rq5qp67wZrHl1Vn6qqg1V1XVXtOBbDAgAsmml2pu5P8sfd/ZwkO5OcV1UvWLfmjUl+2t1PT/KBJO+b7ZgAAItp05jqVfdNDk+a/PS6ZecnuWpy+zNJXlxVNbMpAQAW1FRfJ1NVJyY5kOTpST7c3detW3J6kluTpLuPVNXdSZ6S5CcznPW4t7yc7Nkz7ymAWbnoomRpad5TAMfaVC9A7+5fdffOJGckObeqfm/dko12odbvXqWqlqpqf1XtP3z48IOf9ji3Z0+ysjLvKYBZWFnxjyN4pHhQX3Tc3f9RVfuSnJfk22suHUpyZpJDVbUtyROT3LXB7y8nWU6SXbt2/UZskezcmezbN+8pgFG7d897AuDhMs27+bZX1ZMmtx+b5E+SfHfdsr1JXje5fUGSL3e3WAIAjnvT7EydluSqyeumTkjy6e7+fFVdmmR/d+9NcnmSj1fVwazuSF14zCYGAFggm8ZUd9+Y5LkbnH/Xmtv/meTPZjsaAMDi8wnoAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAgE1jqqrOrKqvVNUtVXVzVb11gzW7q+ruqlqZ/Lzr2IwLALBYtk2x5kiSt3f39VX1+CQHqupL3f2ddeu+1t2vmP2IAACLa9Odqe6+vbuvn9y+N8ktSU4/1oMBAGwFD+o1U1W1I8lzk1y3weUXVtUNVfWFqnrWDGYDAFh40zzNlySpqpOTfDbJ27r7nnWXr09ydnffV1UvT/K5JOdscB9LSZaS5KyzznrIQwMALIqpdqaq6qSshtTV3X3N+uvdfU933ze5fW2Sk6rqlA3WLXf3ru7etX379sHRAQDmb5p381WSy5Pc0t3vP8qaUyfrUlXnTu73zlkOCgCwiKZ5mu9FSV6T5KaqWpmce2eSs5Kkuy9LckGSN1fVkSS/SHJhd/cxmBcAYKFsGlPd/fUktcmaDyX50KyGAgDYKnwCOgDAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMGDTmKqqM6vqK1V1S1XdXFVv3WBNVdUHq+pgVd1YVc87NuMCACyWbVOsOZLk7d19fVU9PsmBqvpSd39nzZqXJTln8vMHST4y+S8AwHFt052p7r69u6+f3L43yS1JTl+37PwkH+tV30jypKo6bebTAgAsmGl2pn6tqnYkeW6S69ZdOj3JrWuOD03O3T4wG3AUyweWs+emPfMegwewcsffJkl2X/m2OU/CA7no2Rdl6flL8x6DLW7qmKqqk5N8Nsnbuvue9Zc3+JXe4D6WkiwlyVlnnfUgxgTW2nPTnqzcsZKdp+6c9ygcxc5LRNSiW7ljJUnEFMOmiqmqOimrIXV1d1+zwZJDSc5cc3xGktvWL+ru5STLSbJr167fiC1gejtP3Zl9r9837zFgy9p95e55j8BxYpp381WSy5Pc0t3vP8qyvUleO3lX3wuS3N3dnuIDAI570+xMvSjJa5LcVFUrk3PvTHJWknT3ZUmuTfLyJAeT/DzJG2Y/KgDA4tk0prr769n4NVFr13SSt8xqKACArcInoAMADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAgE1jqqquqKofV9W3j3J9d1XdXVUrk593zX5MAIDFtG2KNVcm+VCSjz3Amq919ytmMhEAwBay6c5Ud381yV0PwywAAFvOrF4z9cKquqGqvlBVzzraoqpaqqr9VbX/8OHDM3poAID5mUVMXZ/k7O5+TpK/S/K5oy3s7uXu3tXdu7Zv3z6DhwYAmK/hmOrue7r7vsnta5OcVFWnDE8GALAFDMdUVZ1aVTW5fe7kPu8cvV8AgK1g03fzVdUnkuxOckpVHUry7iQnJUl3X5bkgiRvrqojSX6R5MLu7mM2MQDAAtk0prr71Ztc/1BWPzoBAOARxyegAwAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAAzaNqaq6oqp+XFXfPsr1qqoPVtXBqrqxqp43+zEBABbTNDtTVyY57wGuvyzJOZOfpSQfGR8LAGBr2DSmuvurSe56gCXnJ/lYr/pGkidV1WmzGhAAYJFtm8F9nJ7k1jXHhybnbp/BfQMwaPnAcvbctGfeYyyclTtWkiS7r9w930EWzEXPvihLz1+a9xhbyixegF4bnOsNF1YtVdX+qtp/+PDhGTw0AJvZc9OeX4cD/2fnqTuz89Sd8x5joazcsSK8H4JZ7EwdSnLmmuMzkty20cLuXk6ynCS7du3aMLgAmL2dp+7Mvtfvm/cYLDi7dA/NLHam9iZ57eRdfS9Icnd3e4oPAHhE2HRnqqo+kWR3klOq6lCSdyc5KUm6+7Ik1yZ5eZKDSX6e5A3HalgAgEWzaUx196s3ud5J3jKziQAAthCfgA4AMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAyYKqaq6ryq+l5VHayqSza4/vqqOlxVK5OfN81+VACAxbNtswVVdWKSDyd5SZJDSb5ZVXu7+zvrln6quy8+BjMCACysaXamzk1ysLt/0N2/TPLJJOcf27EAALaGaWLq9CS3rjk+NDm33quq6saq+kxVnTmT6QAAFtw0MVUbnOt1x/+UZEd3/36Sf0ly1YZ3VLVUVfurav/hw4cf3KQAAAtompg6lGTtTtMZSW5bu6C77+zu+yeHH03y/I3uqLuXu3tXd+/avn37Q5kXAGChTBNT30xyTlU9raoeleTCJHvXLqiq09YcvjLJLbMbEQBgcW36br7uPlJVFyf5YpITk1zR3TdX1aVJ9nf33iR/WVWvTHIkyV1JXn8MZwYAWBibxlSSdPe1Sa5dd+5da26/I8k7ZjsaAMDi8wnoAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAwQEwBAAwQUwAAA8QUAMAAMQUAMEBMAQAMEFMAAAPEFADAgKliqqrOq6rvVdXBqrpkg+uPrqpPTa5fV1U7Zj0oAMAi2jSmqurEJB9O8rIkz0zy6qp65rplb0zy0+5+epIPJHnfrAcFAFhE0+xMnZvkYHf/oLt/meSTSc5ft+b8JFdNbn8myYurqmY3JgDAYpompk5Pcuua40OTcxuu6e4jSe5O8pRZDAgAsMi2TbFmox2mfghrUlVLSZYmh/dV1femePxHHHt6TKve4I+F6fl7YVr+VjZ09tEuTBNTh5Kcueb4jCS3HWXNoaraluSJSe5af0fdvZxkeYrHBADYEqZ5mu+bSc6pqqdV1aOSXJhk77o1e5O8bnL7giRf7u7f2JkCADjebLoz1d1HquriJF9McmKSK7r75qq6NMn+7t6b5PIkH6+qg1ndkbrwWA4NALAoygYSAMBD5xPQAQAGiCkAgAFiCgBggJhaEFX1D1V1e1XdU1Xfr6o3zXsmFtPkuzAvr6ofVdW9VfWtqnrZvOdiMVXVk6vqH6vqZ5O/mYvmPROLqaourqr9VXV/VV0573m2kmk+Z4qHx98keWN3319Vv5NkX1V9q7sPzHswFs62rH7jwB8l+fckL0/y6ap6dnf/cJ6DsZA+nOSXSZ6aZGeSf66qG7r75vmOxQK6LclfJ3lpksfOeZYtxc7Ugujum7v7/v89nPz89hxHYkF198+6+z3d/cPu/u/u/nySf0vy/HnPxmKpqscleVWSv+ru+7r761n9XMDXzHcyFlF3X9Pdn0ty57xn2WrE1AKpqr+vqp8n+W6S25NcO+eR2AKq6qlJnpHETgPrPSPJr7r7+2vO3ZDkWXOaB45LYmqBdPdfJHl8kj9Mck2S+x/4N3ikq6qTklyd5Kru/u6852HhnJzVL55f6+6s/n8GmBExtWC6+1eTrfgzkrx53vOwuKrqhCQfz+rrYS6e8zgspvuSPGHduSckuXcOs8BxS0wtrm3xmimOoqoqq1/j9NQkr+ru/5rzSCym7yfZVlXnrDn3nHhKGGZKTC2Aqvqtqrqwqk6uqhOr6qVJXp3ky/OejYX1kSS/m+RPu/sX8x6GxdTdP8vqSwYurarHVdWLkpyf1R1N+H+qaltVPSar38N7YlU9pqq8638KvptvAVTV9iSfyeq/GE9I8qMkH+zuj851MBZSVZ2d5IdZfU3dkTWX/ry7r57LUCysqnpykiuSvCSr79K6pLv3zHcqFlFVvSfJu9edfm93v+fhn2ZrEVMAAAM8zQcAMEBMAQAMEFMAAAPEFADAADEFADBATAEADBBTAAADxBQAwAAxBQAw4H8AwVRR7QLwiKkAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "distArray = ssd.squareform(D) \n",
    "\n",
    "plt.figure(figsize=(10,5))\n",
    "linked = linkage(distArray)\n",
    "dendrogram(linked)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The distance matrix `D` can be realized as the distance matrix of a graph. I'll create and render the graph using the `networkx` package, imported at the beginning as `nx`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/needham/opt/anaconda3/lib/python3.7/site-packages/networkx/drawing/nx_pylab.py:579: MatplotlibDeprecationWarning: \n",
      "The iterable function was deprecated in Matplotlib 3.1 and will be removed in 3.3. Use np.iterable instead.\n",
      "  if not cb.iterable(width):\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3daXhV9b328XtPGQgJYUwgAUMSMpABBUSojEctggMVAdm7nOd08LFetLXVVqvCi/NcBopaq7aV2uG0PZc2aShOVFFEEaQi9RSFzAlJRAgQIMGYBDJnPy+UHNMd5mT/9/D9XJdv9l7ZuYOam99a6/9fFrfb7RYAAEHCajoAAADeRPEBAIIKxQcACCoUHwAgqFB8AICgQvEBAIIKxQcACCoUHwAgqFB8AICgQvEBAIIKxQcACCoUHwAgqFB8AICgQvEBAIIKxQcACCp2k9+8rrlNG/fUqKy2UY2tnYoKsystNkpLp8Rr+OBQk9EAAAHKYuJBtPsONeiZ7ZXaUXFCktTW2d3zXpjdKrekuakjtXJOsiaNjfZ2PABAAPN68T2/+4DWbC5Ta2eXzvWdLRYpzG7TqoVpWjE9wWv5AACBzaunOj8vvVK1dHSf91i3W2rp6NKazaWSRPkBAPqF1ya+fYcatPx3u9XS0dXzmruzQ/Vvrlfrgb3qbm2WPXq0hs75PwpPmtrra8MdNuXfNV3Z8Zz2BABcHq/d1fnM9kq1dnb1es3d3SV75AjFutZp7L35ip69QideeVSdDcd6Hdfa2aX12yu9FRUAEMC8Unx1zW3aUXHC45qeNSRM0bO+Lnt0jCwWqwYlT5N9SIzaanuXnNstvVN+QvXNbd6ICwAIYF4pvo17ai7ouK5Tn6rj5GGFjBzn8Z5F0sYPL+xzAAA4G6/c3FJW29hryUJf3F2dqtv0Mw3Ouk6O4WM93m/t7FbZ0aaBiggAGAC+uF7bK8XX2Np5zvfd7m7VvfqEZLNr2A13n+NzOvo7GgBgAJx7vXatnnyrwth6ba/c1fnD/I/08t4jfb7ndrtVv/lpdX52TKOW/qesjrP/DSD603ItHFan7OxsZWVlKSUlRQ6HY6BiAwAuga+v1/ZK8T27o0pPvlXR5+nO+jd+pfbjHytmeY6sIeFn/YwQm0Xzx3RoxIm9KiwsVEFBgQ4dOqTU1FRlZWX1lGFWVpbGjBkji8UykD8SAKAPF7Ne+4xwh1WrFqZ7rfy8Unx1zW269tFtHsXX+dlxHf71tySbQxarref1YTd+V4Mz5vU6NtRu1a6f/Fuvc8KnT59WSUmJCgoKesqwsLBQXV1dHmWYmZmpwYMHD+wPCgBBrK/12pLUuOdvOlX4ttpPHFBE+hyNuPlej6/15nptry1gv+u5f2pr6bFzjr1nY7FI8yfG6NkVU89/sKRjx455lGFpaalGjx7dqwyzs7OVnJwsm812/g8FAJzT2X7Pny7fJVksavn4Q7k72vssvov9PX85jO7ccqH6428CnZ2dqqys7FWGhYWFqq2tVXp6eq8yzMrKUkxMzCV/LwAINmc7s/dln777nLoa6/osPqnvM3sDwWt7dU4aG61VC9Mu8dxv2mWPv3a7XWlpaUpLS9PSpUt7Xm9qalJxcXFPGW7atEkFBQVyOBweZThx4kQNGjTosnIAQCC60PXa53JmvfZ3ZiddfqBz8Oom1WcuXPrS3T6RkZGaPn26pk+f3vOa2+3WkSNHespw27Zteuqpp1RRUaFx48b1KsPs7GyNHz9eVivP9AUQvC5kvfb5eGu9ttcfRLtieoKy46O1fnul3ik/IYs+/2HPOPM8vnmpI7VybrKRjaktFovi4uIUFxenBQsW9Lze0dGh8vLyntOk//Vf/6XCwkLV19crIyOjVxlmZWVp+PDhXs8OACacb732hX/OwK/XNvIE9uz4aD27Yqrqm9u08cMalR1tUmNrh6LCHEobHaklk33zCewOh0OZmZnKzMyU0+nseb2hoUFFRUU91w83bNigwsJCRUREeJRhenq6QkN972cDgMsRFdY/dRIVNvBrs40U3xnDB4cO+Llcb4iOjtbMmTM1c+bMntfcbrcOHjzYU4abN2/WunXrVF1drcTERI/TpePGjWPtIQC/NTbSJru61dnHFtDu7i7pzD/ubrk72yWrrdcyNunzM35poyMHPKvXn8Ae7Nra2lRWVuax3KK5uVmZmZm9lltkZWUpOppnEALwTU1NTXrllVeUm5ur9z8qUvR//Epui+fysIadf9Zn7+X1em3ItU5Fz/p6r9e8dVcnxecj6uvre64dninD4uJiDR061ON0aWpqKlu1ATCira1Nr7/+uvLy8rRlyxbNmjVLLpdLt956q+59sdRr67UvB8Xnw7q7u/Xxxx97rD385JNPlJKS4rHcIi4ujtOlAPpdV1eX3nnnHeXl5enll19Wdna2nE6nbr/99l438Zler32hKD4/1NLS0murtjPF2NHR4VGGmZmZiowc+HPmAAKL2+3WBx98oLy8POXn5ys+Pl5Op1N33HGH4uLizvp17NUJrzp27FhPEZ4pw9LSUsXExPS5VZvdbvTeJgA+qLi4WHl5ecrLy5PD4ZDL5dLy5cuVkpJywZ/B0xlgVFdXV89WbV8+ZXrkyBGlpaV5XD+MiYnhdCkQZA4cOKC//OUvysvL08mTJ7V8+XK5XC5deeWVl/z7oKCmwWfXa1N8Qaq5uVnFxcW9yrCgoEA2m83jdGlGRgZbtQEB5vjx4/rrX/+q3NxcVVRUaMmSJXI6nZo5c2a/7kTli+u1KT70cLvdOnr0qEcZlpeXa+zYsR5rDxMTE9mqDfAjjY2Neumll5Sbm6t//OMfuuWWW+R0OnXDDTcE1Z3iFB/Oq6OjQ/v37/dYe1hXV6eJEyd6XD8cMWKE6cgAvtDa2qrXXntNeXl52rp1q+bNmyeXy6Wbb745aM/kUHy4ZJ999lmvrdrOXEcMDw/vc6u2sLAw05GBoNDZ2alt27YpNzdXmzZt0uTJk+V0OrV48WINHTrUdDzjKD70K7fbrUOHDnmUYWVlpcaPH9+rDLOysnTFFVdwuhToB263W++//77y8vK0YcMGjR8/Xk6nU8uWLdPo0aNNx/MpFB+8oq2tTeXl5R5rDxsbG/vcqo2/lQLn53a7VVhY2LP8ICIiomf5QVKS/++DPFAoPhh18uRJj7WHRUVFio6O9rh2mJqaqpCQENORAeOqq6t7yq65ubln+UFWVhbLkS4AxQef093drQMHDnisPTxw4IAmTJjgsdwiPj6e/9kR8Gpra7Vhwwbl5uaqurpay5Ytk8vl0vTp07lccJEoPviNlpYWlZaWeiy3aGtr63OrtqioKNORgcvS0NCgF198Ubm5udqzZ48WLVokp9Op6667jp2XLgPFB7934sQJjzIsKSnRqFGjPNYeTpgwgV8Y8GmnT5/Wq6++qry8PG3btk3XX3+9XC6XFi5cqPDwcNPxAgLFh4DU1dWl6upqj7WHhw8fVmpqqsdyi9jYWE6XwpiOjg699dZbys3N1auvvqpp06bJ6XTqtttu05AhQ0zHCzgUH4LKqVOn+tyqTZJHGWZkZCgiIsJwYgSq7u5uvffee8rNzdULL7ygCRMmyOl0aunSpYqJiTEdL6BRfAh6brdbtbW1HmsPy8rKFBcX57H2MCkpSTab51OmgfNxu93au3ev8vLy9Je//EXR0dE9yw8SEhJMxwsaFB9wFp2dnb22ajtTjMePH+9zq7aRI0eajgwftX///p7lB21tbXI6nXI6ncrMzDQdLShRfMBFamxs7Nmq7ctTYmhoqEcZTpw4ka3agtThw4eVn5+vvLw81dTUaNmyZXI6nbrmmmu4nmwYxQf0A7fbrZqaGo8y3L9/vxISEjyWWyQkJLD2KgCdPHlSL7zwgnJzc7Vv3z7ddtttcjqdmjt3LncT+xCKDxhA7e3tKi8v97iZ5rPPPlNGRobH9cNhw4aZjoyLdOrUKW3atEl5eXnasWOH5s+fL5fLpRtvvJFp30dRfIABn376qYqKinqVYVFRkaKiojzWHqalpbFVm49pb2/Xli1blJeXp82bN+srX/mKnE6nvva1rykyMtJ0PJwHxQf4CLfbrU8++cRj7eHHH3+spKQkj+UWY8eO5VqRF3V3d+vdd99Vbm6uXnzxRaWnp8vlcmnJkiXc2ORnKD7Ax7W2tnps1VZYWKjTp0/3uVUbC577j9vt1p49e3qWH4waNUoul0t33HGHxo0bZzoeLhHFB/ipuro6jzIsLi7WiBEjPK4dpqSkyOFwmI7sN8rKynqWH7jd7p7lB+np6aajoR9QfEAA6e7u7rVV25lirKmpUUpKisdyi9GjR/vF6dK65jZt3FOjstpGNbZ2KirMrrTYKC2dEq/hg0P75XscOnRI+fn5ys3NVW1trZYvXy6n06mpU6f6xZ8RLhzFBwSB06dP92zVdqYMCwoK1N3d7VGGGRkZGjx4sOnIkqR9hxr0zPZK7ag4IUlq6+zueS/MbpVb0tzUkVo5J1mTxkZf9OfX1dVp48aNys3NVXFxsRYvXiyXy6XZs2ezO08Ao/iAIOV2u3Xs2DGPtYelpaUaM2aMx/XD5ORkr5bB87sPaM3mMrV2dulcv6UsFinMbtOqhWlaMT3hvJ/b1NSkV155RXl5eXrvvfe0YMECuVwuzZ8/n7tngwTFB6CXzs5OVVZWeqw9PHbsmNLT0z2WW4waNarfM3xeeqVq6eg+/8FfCHdYtWphep/l19bWpjfeeEO5ubnasmWLZs2aJafTqVtvvdVnplt4D8UH4II0NTWpuLjYY7mFw+HwKMOJEyde8rPj9h1q0PLf7VZLR1ev17tamlS/+Wm1HvhI1vAoDZ3zH4rImNvrmHCHTfl3TVd2fLS6urq0fft25ebm6uWXX1ZWVpZcLpduv/12DR8+/FL/GBAAKD4Al8ztduvIkSMeZVhRUaFx48Z5rD0cP378ebdqu+u5f2pr6TGP05snXnlMcrs1fOE9aj9WreMb/59iVzyukJFX9BxjsUhXx4ZoTPVrys/PV1xcXM/yg7i4uIH4I4AfovgA9LuOjg6PrdoKCwtVX1+vzMxMj+UWZyawuuY2Xfvotl43sUhSd3urDj21XGPufEaOYZ8XWN3fnpAtcriGzv1G72/e1SHnoGJ907VUKSkp3vhx4WfYNRVAv3M4HMrMzFRmZqacTmfP6w0NDb22asvPz1dhYaEGDx6srKwsOSYtVJctUVLv5QOdJw/LYrX2lJ4kOUaNV9vBQo/vHRYaqoR/W66UlKQB+/ng3yg+AF4THR2tmTNnaubMmT2vud1uHTx4UAUFBXr6gwZ1dnqumevuaJEldFCv16yhg9Td3uJxbGtnt8qONvV/eAQMnosCwCiLxaIrrrhCt9xyi8Ylp/V5jNURLndb75Jzt52WNaTvG2gaWzv6PScCB8UHwGdEhfV9Eso+LE7u7i51nDzc81r78Y/l+NKNLb0/h+3ZcHYUHwCfkRYbpVC7568la0iYBqXOUMPOP6u7vVWtNSU6XfkPRWTM8zg2zG5V2mgeDYSzo/gA+IwlU+LP+t6wr66Uu7NdNb/8uuo2Pa7hX13ZaynDGW5JSyaf/XMAbm4B4DNGDA7VnJSRfa7js4VHatTtq8/59RaLNC91ZL9tXI3AxMQHwKd8d26ywuyXtidomN2mlXOT+zkRAg3FB8CnTBobrVUL0xTuuLhfT5/v1Zmm7PiLf0oDggunOgH4nDMbTQ/E0xkAtiwD4LMKahq0fnul3ik/IYs+X5x+RqjdotbWNs1KHqYHbprEpIcLRvEB8Hn1zW3a+GGNyo42qbG1Q1FhDqWNjlTV1j+r4ViNfvvb35qOCD9C8QHwW/X19UpJSdHevXs1duxY03HgJ7i5BYDfGj58uL797W/r8ccfNx0FfoSJD4Bfq62t1cSJE1VSUqLY2FjTceAHmPgA+LXY2FitWLFCP//5z01HgZ9g4gPg9w4dOqQrr7xSFRUVPQ+1Bc6GiQ+A3xs7dqxuv/12Pf3006ajwA8w8QEICNXV1Zo2bZqqqqo0ZMgQ03Hgw5j4AASExMRELVy4UM8884zpKPBxTHwAAkZpaanmzp2r6upqRUREmI4DH8XEByBgpKena86cOfrNb35jOgp8GBMfgICyb98+LViwQNXV1QoLCzMdBz6IiQ9AQJk0aZKuvvpq/eEPfzAdBT6KiQ9AwPnggw+0dOlS7d+/XyEhIabjwMcw8QEIONOmTVNaWpqef/5501Hgg5j4AASknTt36pvf/KbKyspkt/PMbfwvJj4AAWnWrFmKi4tTfn6+6SjwMUx8AALW1q1b9YMf/EBFRUWyWvl7Pj7HfwkAAtb111+vyMhIvfTSS6ajwIdQfAAClsVi0erVq5WTkyNObuEMig9AQLv55pvldru1efNm01HgIyg+AAHNYrFo1apVeuSRR5j6IIniAxAEFi9erM8++0zbtm0zHQU+gOIDEPBsNpsefvhh5eTkmI4CH0DxAQgKTqdTn3zyif7+97+bjgLDKD4AQcFut+uhhx7SmjVrTEeBYSxgBxA02tralJycrJdeeklTp041HQeGMPEBCBqhoaF64IEHmPqCHBMfgKDS0tKixMREvfnmm8rKyjIdBwYw8QEIKuHh4brvvvu0du1a01FgCBMfgKDT1NSkpKQk7dy5U6mpqabjwMuY+AAEncjISH3/+9/XunXrTEeBAUx8AIJSQ0ODkpOT9c9//lMJCQmm48CLmPgABKXo6GjdfffdevTRR01HgZcx8QEIWnV1dUpNTVVBQYHi4uJMx4GXUHwAgtqPf/xjdXZ26qmnnjIdBV5C8QEIakePHlVGRoZKS0sVExNjOg68gGt8AILa6NGj5XK59OSTT5qOAi9h4gMQ9A4ePKirrrpK+/fv17Bhw0zHwQBj4gMQ9MaNG6fbbrtNv/jFL0xHgRcw8QGApMrKSs2YMUNVVVWKiooyHQcDiIkPACQlJydr/vz5Wr9+vekoGGBMfADwhZKSEs2bN0/V1dWKiIgwHQcDhIkPAL4wceJEzZo1S7/73e9MR8EAYuIDgC/56KOPdPPNN6uqqkphYWGm42AAMPEBwJdcddVVuuqqq/SnP/3JdBQMECY+APgX77//vpxOp/bv3y+Hw2E6DvoZEx8A/IsZM2YoOTlZf/7zn01HwQBg4gOAPmzfvl133XWXSktLZbPZTMdBP2LiA4A+zJkzR6NGjdJf//pX01HQz5j4AOAs3njjDd1///3at2+frFbmhEDBv0kAOIv58+crLCxMmzZtMh0F/YjiA4CzsFgsWr16tXJycsTJscBB8QHAOdxyyy1qb2/Xli1bTEdBP6H4AOAcrFarVq1apUceeYSpL0BQfABwHkuWLFFdXZ22b99uOgr6AcUHAOdhs9n08MMPKycnx3QU9AOKDwAugMvlUnV1tXbt2mU6Ci4TxQcAF8DhcOjBBx/UmjVrTEfBZWIBOwBcoLa2NiUlJWnTpk2aPHmy6Ti4REx8AHCBQkNDdf/99zP1+TkmPgC4CKdPn1ZiYqLefvttZWRkmI6DS8DEBwAXYdCgQbr33nu1du1a01FwiZj4AOAiNTY2KikpSbt27dKECRNMx8FFYuIDgIsUFRWl733ve1q3bp3pKLgETHwAcAlOnjypCRMm6MMPP9QVV1xhOg4uAhMfAFyCYcOG6a677tJjjz1mOgouEhMfAFyi48ePKy0tTUVFRRozZozpOLhAFB8AXIZ7771XVqtVTzzxhOkouEAUHwBchsOHDysrK0vl5eUaOXKk6Ti4AFzjA4DLEBcXpzvuuENPPfWU6Si4QEx8AHCZDhw4oKlTp2r//v0aOnSo6Tg4DyY+ALhMCQkJuvXWW/WrX/3KdBRcACY+AOgHFRUVmjlzpqqqqhQZGWk6Ds6BiQ8A+kFKSoquv/56Pfvss6aj4DyY+ACgnxQVFemGG25QVVWVBg0aZDoOzoKJDwD6SWZmpmbMmKHf//73pqPgHJj4AKAf7dmzR4sWLVJVVZVCQ0NNx0EfmPgAoB9NmTJF2dnZ+u///m/TUXAWTHwA0M927dqlFStWqLy8XA6Hw3Qc/AsmPgDoZ1/5yleUkJCgvLw801HQByY+ABgA27Zt08qVK1VcXCybzWY6Dr6EiQ8ABsC8efM0bNgwvfDCC6aj4F8w8QHAANm8ebMefPBB7d27V1Yrc4av4N8EAAyQBQsWyG6369VXXzUdBV9C8QHAALFYLFq9erVycnLEyTXfQfEBwAD62te+plOnTmnr1q2mo+ALFB8ADCCr1apVq1YpJyfHdBR8geIDgAG2bNkyHT16VO+++67pKBDFBwADzm6366GHHmLq8xEsZwAAL2hvb9eECRO0YcMGXXPNNabjBDUmPgDwgpCQEP3kJz/RmjVrTEcJekx8AOAlra2tSkpK0muvvaYrr7zSdJygxcQHAF4SFhamH//4x1q7dq3pKEGNiQ8AvOjUqVNKTEzU9u3blZ6ebjpOUGLiAwAvioiI0A9/+EOmPoOY+ADAyxobG5WUlKTdu3crKSnJdJygw8QHAF4WFRWllStXat26daajBCUmPgAwoL6+XikpKfroo480btw403GCChMfABgwfPhw3XnnnXr88cdNRwk6THwAYMixY8eUnp6ukpISxcbGmo4TNJj4AMCQmJgY/fu//7ueeOIJ01GCChMfABhUU1Oj7OxsVVRUaMSIEabjBAUmPgAwKD4+XkuXLtXTTz9tOkrQYOIDAMOqq6s1bdo0VVZWKjo62nScgMfEBwCGJSYm6qabbtIzzzxjOkpQYOIDAB9QVlam2bNnq7q6WoMHDzYdJ6Ax8QGAD0hLS9O8efP0m9/8xnSUgMfEBwA+oqCgQDfeeKOqqqoUHh5uOk7AYuIDAB+RnZ2tq6++Wn/4wx9MRwloTHwA4EM++OADLVmyRJWVlQoJCTEdJyAx8QGAD5k2bZrS09P13HPPmY4SsJj4AMDH/P3vf9c3vvENlZWVyW63m44TcJj4AMDHzJw5U/Hx8crPzzcdJSAx8QGAD3rrrbd0zz33qKioSFYrM0p/4k8TAHzQddddp6ioKL344oumowQcig8AfJDFYtHq1auVk5MjTsz1L4oPAHzUTTfdJEl67bXXDCcJLBQfAPgopr6BQfEBgA9bvHixGhsb9fbbb5uOEjAoPgDwYVarVQ8//LBycnJMRwkYFB8A+Ljly5fr0KFD2rlzp+koAYHiAwAfZ7fb9dBDD2nNmjWmowQEFrADgB9ob29XcnKyXnjhBV199dWm4/g1Jj4A8AMhISF64IEHmPr6ARMfAPiJlpYWJSYmasuWLcrOzjYdx28x8QGAnwgPD9ePfvQjrV271nQUv8bEBwB+pLm5WYmJidq5c6dSU1NNx/FLTHwA4EcGDx6se+65Rz/96U9NR/FbTHwA4GcaGhqUnJys//mf/9H48eNNx/E7THwA4Geio6N1991369FHHzUdxS8x8QGAH6qrq1Nqaqr27dun+Ph403H8ChMfAPihESNG6Fvf+pZ+9rOfmY7id5j4AMBP1dbWKiMjQyUlJYqJiTEdx28w8QGAn4qNjZXL5dKTTz5pOopfYeIDAD928OBBXXXVVaqoqNDw4cNNx/ELTHwA4MfGjRunxYsX6xe/+IXpKH6DiQ8A/FxVVZWuueYaVVVVaciQIabj+DwmPgDwc0lJSVqwYIHWr19vOopfYOIDgABQUlKiefPmqbq6WhEREabj+DQmPgAIABMnTtTs2bP129/+1nQUn8fEBwABYu/evbrppptUVVWlsLAw03F8FhMfAASIK6+8UpMnT9Yf//hH01F8GhMfAASQ3bt3a/ny5dq/f78cDofpOD6JiQ8AAsj06dM1YcIEPf/886aj+CwmPgAIMDt27NCdd96psrIy2Ww203F8DhMfAASY2bNnKzY2Vhs2bDAdxScx8QFAANqyZYt+9KMfqaCgQFYrM86X8acBAAHoq1/9qsLDw/XKK6+YjuJzKD4ACEAWi0WrV69WTk6OOLHXG8UHAAHqlltuUUdHh9544w3TUXwKxQcAAcpqtWrVqlV65JFHmPq+hOIDgAC2ZMkSnTx5Utu3bzcdxWdQfAAQwGw2mx5++GHl5OSYjuIzKD4ACHBOp1Mff/yxdu3aZTqKT6D4ACDAORwOPfjgg0x9X2ABOwAEgba2NiUnJ+vll1/WlClTTMcxiokPAIJAaGio7r//fq1Zs8Z0FOOY+AAgSJw+fVqJiYl66623lJmZaTqOMUx8ABAkBg0apPvuu09r1641HcUoJj4ACCJNTU1KTEzUe++9p5SUFNNxjGDiA4AgEhkZqe9///tat26d6SjGMPEBQJD59NNPlZycrD179ighIcF0HK9j4gOAIDN06FB95zvf0WOPPWY6ihFMfAAQhE6cOKHU1FQVFRVpzJgxpuN4FcUHAEHqvvvukyT9/Oc/N5zEuyg+AAhSR44cUWZmpsrLyzVy5EjTcbyGa3wAEKTGjBmj5cuX68knnzQdxauY+AAgiB04cEBTpkxRZWWlhg4dajqOVzDxAUAQS0hI0KJFi/TLX/7SdBSvYeIDgCBXUVGha6+9VtXV1YqMjDQdZ8Ax8QFAkEtJSdENN9ygX//616ajeAUTHwBAxcXFuu6661RdXa1BgwaZjjOgmPgAAMrIyNC1116r3//+96ajDDgmPgCAJOnDDz/UokWLVFlZqdDQUNNxBgwTHwBAkjR58mRlZ2frT3/6k+koA4qJDwDQ4/3335fL5VJFRYUcDofpOAOCiQ8A0GPGjBlKTExUbm6u6SgDhokPANDLO++8o7vvvlslJSWy2Wym4/Q7Jj4AQC9z587ViBEjtHHjRtNRBgQTHwDAw+uvv64HHnhA+/btk9UaWDNSYP00AIB+ceONNyokJER/+9vfTEfpdxQfAMCDxWLR6tWrlZOTo0A7MUjxAQD6tGjRIrW0tOjNN980HaVfUXwAgD5ZrVatWrVKjzzySEBNfRQfAOCsli1bpuPHj+vdd981HaXfcFcnAOCc/vjHPyo3N1dbt25VXXObNu6pUVltoxpbOxUVZldabJSWTonX8MH+sb8nxQcAOKeOjg5NuOY6Xf2N1So40UdZfxoAAAMBSURBVCVJauvs7nk/zG6VW9Lc1JFaOSdZk8ZGG0p6YSg+AMA5Pb/7gP5zU6E6uyVZzn6FzGKRwuw2rVqYphXTE7yW72LZTQcAAPiu53cf0JrNpep0WyXLuY91u6WWji6t2VwqST5bfkx8AIA+7TvUoOW/262Wjq5er9f97WdqPbBP3R2tskUMVdT02xU5aX6vY8IdNuXfNV3Z8b532pPiAwD06a7n/qmtpcf0ry3RfuITOYaOkcXuUEf9IdXmPqRRS/9TobHJPcdYLNL8iTF6dsVUL6c+P5YzAAA81DW3aUfFCY/Sk6SQkVfIYj/zrD6LLLKo89OjvY5xu6V3yk+ovrlt4MNeJK7xAQA8bNxTc87367es16nCt+XubFNITJLCkzwnO4ukjR/W6DuzkwYo5aWh+AAAHspqG3stWfhXw+ev1LAbvqO2w2VqPVgoi83zae2tnd0qO9o0kDEvCac6AQAeGls7z3uMxWpT2NgMdTXVqemjzWf5nI7+jnbZKD4AgIeosIs4Idjd7XGN738/x3MSNI3iAwB4SIuNUqjdsyK6TjXoVMkOdbe3yN3dpZbqPTpVukNhV0zyODbMblXa6EhvxL0oXOMDAHhYMiVeT75V4fmGxaKmj15X/Zb1krtb9iGjNPS6/6tBKdM9DnVLWjI5fuDDXiSKDwDgYcTgUM1JGemxjs82aIhiv77uvF9vsUjzUkf65MbVnOoEAPTpu3OTFWa3XdLXhtltWjk3+fwHGkDxAQD6NGlstFYtTFO44+KqItxh1aqFaT65XZnEqU4AwDmc2Wh6zeYytXZ29bmTyxn+8nQG9uoEAJxXQU2D1m+v1DvlJ2TR54vTzzjzPL55qSO1cm6yz056Z1B8AIALVt/cpo0f1qjsaJMaWzsUFeZQ2uhILZnME9gBAPBJ3NwCAAgqFB8AIKhQfACAoELxAQCCCsUHAAgqFB8AIKhQfACAoELxAQCCCsUHAAgqFB8AIKhQfACAoELxAQCCCsUHAAgqFB8AIKhQfACAoPL/Af7M7xsIo7A3AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "G = nx.Graph() # Initializing the graph\n",
    "\n",
    "# Add weighted edges\n",
    "G.add_edge(0,1,weight = 1) \n",
    "G.add_edge(0,2,weight = 2)\n",
    "G.add_edge(0,3,weight = 3)\n",
    "\n",
    "# Draw the graph using the Kamada-Kawai graph layout algorithm\n",
    "nx.draw_kamada_kawai(G, with_labels = True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be precise, this is actually a *weighted graph*, where the edges have weights (or lengths) 1, 2 and 3, respectively. The metric takes the lengths of edges into account when measuring the lengths of paths between vertices.\n",
    "\n",
    "**Exercise:** Write down a precise definition of the geodesic metric for a weighted graph.\n",
    "\n",
    "**Exercise:** Check that the distance matrix `D` defined above is the distance matrix for this graph.\n",
    "\n",
    "**Exercise:** Play around with this code to figure out how to define your own weighted graphs. Once you create a weighted graph, you can compute its distance matrix using the function `nx.floyd_warshall_numpy`, and you can then look at the dendrogram for your graph. This is a good way to build intuition about non-Euclidean metrics and clustering!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQcAAAD8CAYAAAB6iWHJAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAANSUlEQVR4nO3df+xddX3H8efLtqL8RkpCVypoIGTEjSJYMSQLAcmAGLpkOMsSBQNpZmTiMhN1W1hmTMD9oYliXHCQgTGKAcc6w2IwQNRsMAopPzu0Y1loSgAB+anFL7z3xz2wr99+vm3pPffc77d9PpKb7zn3fO59f25KXpx7zrnnnapCkuZ6y7QnIGlhMhwkNRkOkpoMB0lNhoOkJsNBUtNY4ZDkHUluTfLz7u9h84x7Ncmm7rFhnJqShpFxrnNI8vfAM1V1ZZLPAYdV1Wcb416sqgPHmKekgY0bDo8Ap1fV40lWAHdU1fGNcYaDtMiMGw6/rKpDZ60/W1U7fLVIMgNsAmaAK6vq5nnebz2wHmAJS07en4P3eG4LVR20/7SnMDEzB2TaU5iI197+2rSnMDGv/M+2X1TVEa1tS3f14iQ/Ao5sbPrrNzGHd1bVtiTvBm5L8kBV/ffcQVV1NXA1wMF5R70/Z76JEovDzJqTpz2FiXnifftNewoTsf3El6c9hYl59IK/+d/5tu0yHKrqg/NtS/JEkhWzvlY8Oc97bOv+PprkDuAkYIdwkLRwjHsqcwNwYbd8IfAvcwckOSzJft3ycuA04OEx60qasHHD4UrgrCQ/B87q1klySpJ/7Mb8LrAxyX3A7YyOORgO0gK3y68VO1NVTwM7HBioqo3AJd3yvwO/N04dScPzCklJTYaDpCbDQVKT4SCpyXCQ1GQ4SGoyHCQ1GQ6SmgwHSU2Gg6Qmw0FSk+EgqclwkNRkOEhqMhwkNRkOkpoMB0lNhoOkpl7CIcnZSR5JsqXrfDV3+35Jbui235XkmD7qSpqcscMhyRLg68A5wAnABUlOmDPsYuDZqjoW+ArwpXHrSpqsPvYc1gBbqurRqnoF+C6wds6YtcB13fKNwJlJ9s72SNJeoo9wWAk8Nmt9a/dcc0xVzQDPAYf3UFvShIx1a/pOaw9gbgPO3RnzW70y38be21NSWgz62HPYCqyatX4UsG2+MUmWAocAz8x9o6q6uqpOqapTlrF39l2UFos+wuFu4Lgk70ryVmAdozZ5s81um3c+cFuN095b0sSN/bWiqmaSXAr8EFgCXFtVDyX5ArCxqjYA1wDfSrKF0R7DunHrSpqsPo45UFW3ALfMee7yWcu/Bj7cRy1Jw/AKSUlNhoOkJsNBUpPhIKnJcJDUZDhIajIcJDUZDpKaDAdJTYaDpCbDQVKT4SCpyXCQ1GQ4SGoyHCQ1GQ6SmgwHSU2Gg6Qmw0FS01C9Mi9K8lSSTd3jkj7qSpqcsW8wO6tX5lmM+lPcnWRDVT08Z+gNVXXpuPUkDaOPu0+/0SsTIMnrvTLnhsObUgftz8yak3uY3sKy9LZ7pj2Fidl+yeppT2EiPnLC3vtvdsVOtg3VKxPgj5Pcn+TGJKsa20myPsnGJBt/85uXepiapD3VRzjsTh/MfwWOqarfB37E/3fc/u0XzW6Ht+yAHqYmaU8N0iuzqp6uqu3d6jeBve/7grSXGaRXZpIVs1bPAzb3UFfSBA3VK/NTSc4DZhj1yrxo3LqSJmuoXpmfBz7fRy1Jw/AKSUlNhoOkJsNBUpPhIKnJcJDUZDhIajIcJDUZDpKaDAdJTYaDpCbDQVKT4SCpyXCQ1GQ4SGoyHCQ1GQ6SmgwHSU2Gg6SmvtrhXZvkySQPzrM9Sb7atcu7P8l7+6graXL62nP4J+DsnWw/Bziue6wHvtFTXUkT0ks4VNWPGd1Vej5rgetr5E7g0Dm3q5e0wAx1zGG3WubZDk9aOIYKh91pmWc7PGkBGSocdtkyT9LCMlQ4bAA+1p21OBV4rqoeH6i2pD3QS8erJN8BTgeWJ9kK/C2wDKCq/oFRN6xzgS3Ay8DH+6graXL6aod3wS62F/DJPmpJGoZXSEpqMhwkNRkOkpoMB0lNhoOkJsNBUpPhIKnJcJDUZDhIajIcJDUZDpKaDAdJTYaDpCbDQVKT4SCpyXCQ1GQ4SGoyHCQ1DdUO7/QkzyXZ1D0u76OupMnp5R6SjNrhXQVcv5MxP6mqD/VUT9KEDdUOT9Ii09eew+74QJL7GDWz+UxVPTR3QJL1jBrtsvTgw3jiffsNOL1hbL9k9bSnMDHv/tNN057CRHxx2wPTnsLEXLGTbUMdkLwXOLqqTgS+BtzcGjS7Hd7S/W2HJ03TIOFQVc9X1Yvd8i3AsiTLh6gtac8MEg5JjkySbnlNV/fpIWpL2jNDtcM7H/hEkhngV8C6rguWpAVqqHZ4VzE61SlpkfAKSUlNhoOkJsNBUpPhIKnJcJDUZDhIajIcJDUZDpKaDAdJTYaDpCbDQVKT4SCpyXCQ1GQ4SGoyHCQ1GQ6SmgwHSU2Gg6SmscMhyaoktyfZnOShJJc1xiTJV5NsSXJ/kveOW1fSZPVxD8kZ4C+r6t4kBwH3JLm1qh6eNeYc4Lju8X7gG91fSQvU2HsOVfV4Vd3bLb8AbAZWzhm2Fri+Ru4EDk2yYtzakian12MOSY4BTgLumrNpJfDYrPWt7BggJFmfZGOSjTMvv9Tn1CS9Sb2FQ5IDgZuAT1fV83M3N16yQ98K2+FJC0cv4ZBkGaNg+HZVfb8xZCuwatb6UYwa6kpaoPo4WxHgGmBzVX15nmEbgI91Zy1OBZ6rqsfHrS1pcvo4W3Ea8FHggSSv92D/K+Cd8EY7vFuAc4EtwMvAx3uoK2mCxg6Hqvop7WMKs8cU8Mlxa0kajldISmoyHCQ1GQ6SmgwHSU2Gg6Qmw0FSk+EgqclwkNRkOEhqMhwkNRkOkpoMB0lNhoOkJsNBUpPhIKnJcJDUZDhIajIcJDUN1Q7v9CTPJdnUPS4ft66kyRqqHR7AT6rqQz3UkzSAodrhSVpk+thzeMNO2uEBfCDJfYya2Xymqh5qvH49sB5g6fJD2H7iy31Ob0H4yAn3THsKE/PFbQ9MewoT8Ye/s3raU5igLfNuGaod3r3A0VV1IvA14ObWe8xuh/eWg2yHJ03TIO3wqur5qnqxW74FWJZkeR+1JU3GIO3wkhzZjSPJmq7u0+PWljQ5Q7XDOx/4RJIZ4FfAuq4LlqQFaqh2eFcBV41bS9JwvEJSUpPhIKnJcJDUZDhIajIcJDUZDpKaDAdJTYaDpCbDQVKT4SCpyXCQ1GQ4SGoyHCQ1GQ6SmgwHSU2Gg6Qmw0FSk+EgqamPG8y+Lcl/Jrmva4f3d40x+yW5IcmWJHd1/S0kLWB97DlsB87oelKsBs5OcuqcMRcDz1bVscBXgC/1UFfSBPXRDq9e70kBLOsec+8svRa4rlu+ETjz9VvVS1qY+mpqs6S7Lf2TwK1VNbcd3krgMYCqmgGeAw7vo7akyeglHKrq1apaDRwFrEnynjlDWnsJO/StSLI+ycYkG1974aU+piZpD/V6tqKqfgncAZw9Z9NWYBVAkqXAIcAzjdfbK1NaIPo4W3FEkkO75bcDHwT+a86wDcCF3fL5wG12vJIWtj7a4a0ArkuyhFHYfK+qfpDkC8DGqtrAqJfmt5JsYbTHsK6HupImqI92ePcDJzWev3zW8q+BD49bS9JwvEJSUpPhIKnJcJDUZDhIajIcJDUZDpKaDAdJTYaDpCbDQVKT4SCpyXCQ1GQ4SGoyHCQ1GQ6SmgwHSU2Gg6Qmw0FSk+EgqclwkNQ0VK/Mi5I8lWRT97hk3LqSJquPu0+/3ivzxSTLgJ8m+bequnPOuBuq6tIe6kkaQB93ny5gV70yJS0y6aO3TNez4h7gWODrVfXZOdsvAq4AngJ+BvxFVT3WeJ/1wPpu9XjgkbEnt/uWA78YsN5Q/FyLz5Cf7eiqOqK1oZdweOPNRp2v/hn486p6cNbzhwMvVtX2JH8G/ElVndFb4R4k2VhVp0x7Hn3zcy0+C+WzDdIrs6qerqrt3eo3gZP7rCupf4P0ykyyYtbqecDmcetKmqyhemV+Ksl5wAyjXpkX9VC3b1dPewIT4udafBbEZ+v1mIOkvYdXSEpqMhwkNe3z4ZDk7CSPJNmS5HPTnk9fklyb5MkkD+569OKRZFWS25Ns7i7Xv2zac+rD7vwMYfA57cvHHLqDqD8DzgK2AncDF1TVw1OdWA+S/AGjK1evr6r3THs+fenOfK2oqnuTHMTo4rs/Wuz/ZkkCHDD7ZwjAZY2fIQxmX99zWANsqapHq+oV4LvA2inPqRdV9WNGZ4b2KlX1eFXd2y2/wOi0+Mrpzmp8NbKgfoawr4fDSmD2Zdxb2Qv+Q9tXJDkGOAm4a7oz6UeSJUk2AU8Ct1bVVD/Xvh4OaTy3737PWkSSHAjcBHy6qp6f9nz6UFWvVtVq4ChgTZKpfh3c18NhK7Bq1vpRwLYpzUW7qftOfhPw7ar6/rTn07f5foYwtH09HO4GjkvyriRvBdYBG6Y8J+1Ed+DuGmBzVX152vPpy+78DGFo+3Q4VNUMcCnwQ0YHtr5XVQ9Nd1b9SPId4D+A45NsTXLxtOfUk9OAjwJnzLqz2LnTnlQPVgC3J7mf0f+0bq2qH0xzQvv0qUxJ89un9xwkzc9wkNRkOEhqMhwkNRkOkpoMB0lNhoOkpv8DJFogWiDabCIAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAGQAAAD4CAYAAAAaRkNsAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAHEUlEQVR4nO3d3YtUdRzH8c+n9WF1k4K0SFdSSKQl0ECM8CqLfCjyohuFuhK8EgyCsLv6ByICCaTEoFKkEiQsk0pE8NlMNDUWKVw2WB/K1PBht28XM8poo/7Wzm/mg7/PC5bd2RnOfuHNmT2zc357GBEwHfe1ewC7kYOIcRAxDiLGQcSMyLHRURwdnejKsel7wiVcxJW4zGb3ZQnSiS48zedybPqesDu+u+V9fsoS4yBiHESMg4hxEDEOIsZBxDiIGAcR4yBiHESMg4hxEDFJQUjOJ3mcZC/JlbmHKtkdg5DsALAKwAIAPQCWkOzJPVipUvaQ2QB6I+JERFwBsB7AorxjlSslyCQAJxtu99W/dwOSy0juI7nvKi5XNV9xUoI0e6vxP2fXRcTqiJgVEbNGYvT/n6xQKUH6AExuuN0NoD/POJYSZC+AaSSnkhwFYDGATXnHKtcdT3KIiEGSywFsAdABYE1EHMk+WaGSzjqJiM0ANmeexeBX6nIcRIyDiHEQMQ4ixkHEOIgYBxHjIGIcRIyDiHEQMVmWtA1NG41z7z+eY9N35YGFve0eIZn3EDEOIsZBxDiIGAcR4yBiHESMg4hxEDEOIsZBxDiIGAcR4yBiHERMyhrDNSQHSB5uxUClS9lD1gKYn3kOq7tjkIjYDuBsC2YxVPg7pHHR5+C5v6vabHEqC9K46HPEA2Or2mxxfJQlxkHEpBz2rgOwE8B0kn0kl+Yfq1wpq3CXtGIQq/FTlhgHEeMgYhxEjIOIcRAxDiLGQcQ4iBgHEeMgYhxETJZFn0+M+QO7Zn6eY9N3ZR5mtnuEZN5DxDiIGAcR4yBiHESMg4hxEDEOIsZBxDiIGAcR4yBiHESMg4hJOdl6MskfSB4leYTkilYMVqqU90MGAbwREQdIjgOwn+TWiPg582xFSllj+HtEHKh/fR7AUTS5jqFVY1i/Q0hOAfAUgN1N7ru+xvDUmaFqpitQchCS9wP4AsDrEfHXzfc3rjGc8FBHlTMWJfVq0SNRi/FpRHyZd6SypRxlEcBHAI5GxLv5Rypbyh4yB8BrAOaSPFj/WJh5rmKlrDHcgeYXKLYM/EpdjIOIcRAxDiLGQcQ4iBgHEeMgYhxEjIOIcRAxDiImyxrDXw6NxbyJOuv6tvQfbPcIN5g979b/tdV7iBgHEeMgYhxEjIOIcRAxDiLGQcQ4iBgHEeMgYhxEjIOIcRAxKWe/d5LcQ/Kn+hrDd1oxWKlS3g+5DGBuRFyorxPZQfLriNiVebYipZz9HgAu1G+OrH9EzqFKlrqCqoPkQQADALZGxG3XGF7F5arnLEZSkIgYioiZALoBzCb5ZJPHXF9jOBKjq56zGMM6yoqIPwFsg6+Nm03KUdYEkg/Wvx4D4HkAx3IPVqqUo6xHAXxMsgO1gBsi4qu8Y5Ur5SjrEGr/LMBawK/UxTiIGAcR4yBiHESMg4hxEDEOIsZBxDiIGAcR4yBisqwxHBzfhdOvPJNj03dJa43h7XgPEeMgYhxEjIOIcRAxDiLGQcQ4iBgHEeMgYhxEjIOIcRAxDiJmONeg6iD5I0mfaJ3RcPaQFahdMs8ySl3S1g3gRQAf5h3HUveQ9wC8CeCfWz2gcY3h4KWLlQxXopQVVC8BGIiI/bd7XOMawxGdXZUNWJrUq7S9TPJXAOtRu1rbJ1mnKljKtXDfiojuiJgCYDGA7yPi1eyTFcqvQ8QM6zSgiNiG2rJoy8R7iBgHEeMgYhxEjIOIcRAxDiLGQcQ4iBgHEeMgYhxEjIOIybLos2fiKex5+4Mcm77neQ8R4yBiHESMg4hxEDEOIsZBxDiIGAcR4yBiHESMg4hxEDEOIibpz+/1tSHnAQwBGIyIWTmHKtlw3g95NiJOZ5vEAPgpS05qkADwLcn9JJc1e0Djos9TZ4aqm7AwqU9ZcyKin+TDALaSPBYR2xsfEBGrAawGgFkzOn1p1ruUeqXP/vrnAQAbAczOOVTJUpZFd5Ecd+1rAC8AOJx7sFKlPGU9AmAjyWuP/ywivsk6VcFSLix5AsCMFsxi8GGvHAcR4yBiHESMg4hxEDEOIsZBxDiIGAcR4yBiHEQMI6p/L4nkKQC/VbCp8QCU3sevap7HImJCszuyBKkKyX1KZ7i0Yh4/ZYlxEDHqQVa3e4CbZJ9H+ndIidT3kOI4iBjJICTnkzxOspfkSoF51pAcIJn99Ce5ICQ7AKwCsABAD4AlJHvaOxXWApjfih8kFwS1syJ7I+JERFxB7RIZi9o5UP202bOt+FmKQSYBONlwu6/+vSIoBmGT7xVzbK4YpA/A5Ibb3QD62zRLyykG2QtgGsmpJEehdlWfTW2eqWXkgkTEIIDlALagdt3EDRFxpJ0zkVwHYCeA6ST7SC7N9rP8pxMtcntI6RxEjIOIcRAxDiLGQcQ4iJh/AVr6moCWwvLfAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "D = nx.floyd_warshall_numpy(G)\n",
    "plt.imshow(D)\n",
    "plt.show()\n",
    "\n",
    "plt.imshow(X)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gromov-Hausdorff Stability\n",
    "\n",
    "At a high level, we can think of the Single Linkage Hierarchical Clustering (SLHC) algorithm as defining a map\n",
    "\\begin{align*}\n",
    "\\mathrm{SLHC}:\\{\\mbox{finite metric spaces}\\} &\\to \\{\\mbox{finite ultrametric spaces}\\}\\\\\n",
    "(X,d_X) &\\mapsto (X,u_X),\n",
    "\\end{align*}\n",
    "where $u_X$ is the SLCH metric defined above.\n",
    "\n",
    "Intuitively, this map takes metric spaces which are 'similar' and produces ultrametric spaces which are also 'similar'. This can be made precise as follows.\n",
    "\n",
    "In lecture, we defined a way to compare finite metric spaces called *Gromov-Hausdorff distance*, denoted $d_\\mathrm{GH}$. In fact, we proved that Gromov-Hausdorff distance defines a metric on the space of isometry classes of compact metric spaces! We then have the following theorem, due to Carlsson and Mémoli.\n",
    "\n",
    "**Theorem.** Let $(X,d_X)$ and $(Y,d_Y)$ be finite metric spaces. Then\n",
    "$$\n",
    "d_\\mathrm{GH}((X,u_X),(Y,u_Y)) \\leq d_\\mathrm{GH}((X,d_X),(Y,d_Y)).\n",
    "$$\n",
    "\n",
    "This theorem has a quick corollary which will be useful on your homework.\n",
    "\n",
    "**Corollary.** Let $(X,d_X)$ be a finite metric space and let $I = [0,1]$ be the unit interval, endowed with Euclidean distance $d_I$. Then \n",
    "$$\n",
    "\\sup_{x,x' \\in X} u_X(x,x') \\leq d_\\mathrm{GH}((X,d_X),(I,d_I)).\n",
    "$$\n",
    "\n",
    "Let's break from the notebook to prove these results.\n",
    "\n",
    "**** Break ****"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}