test Algorithm 1 - warm-start.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d8c341f4-72ec-41d9-8094-82d124d0d245",
   "metadata": {},
   "outputs": [],
   "source": [
    "exec(open(\"./funcs/mmj_functions.py\").read())\n",
    "exec(open(\"./funcs/variant_of_Floyd_Warshall.py\").read())\n",
    "exec(open(\"./funcs/Prim_Minimum_Spanning_Tree.py\").read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "34c6d6cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "2baeabee-a859-49f8-a070-cf2135ae5563",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "test_data_145 = pickle.load(  open( \"./data/test_data_145.p\", \"rb\" ) ) \n",
    " \n",
    "X = test_data_145[18]\n",
    "    \n",
    "# plt.scatter(X[:,0],X[:,1], s= 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2846295f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_n_mmj_new(X_plus_distance_matrix, X_plus_mmj_matrix, n):\n",
    "    for i in range(n):\n",
    "        X_plus_mmj_matrix[n,i] = X_plus_mmj_matrix[i,n] = mmj_n_to_r(X_plus_distance_matrix, X_plus_mmj_matrix, n, i)\n",
    " \n",
    "    for i in range(n):        \n",
    "        for j in range(n):\n",
    "            if i < j:\n",
    "                X_plus_mmj_matrix[i,j] = X_plus_mmj_matrix[j,i] = update_mmj_ij(X_plus_distance_matrix, X_plus_mmj_matrix, n, i, j)\n",
    "\n",
    "def cal_mmj_matrix_algo_1_warm_start(X_plus, X_mmj_matrix):\n",
    "    \n",
    "    X_plus_distance_matrix = pairwise_distances(X_plus)\n",
    "    X_plus_distance_matrix = np.round(X_plus_distance_matrix, 15)\n",
    "\n",
    "    N = len(X_plus) - 1\n",
    "   \n",
    "    X_plus_mmj_matrix = np.zeros((N + 1,N + 1))\n",
    "    \n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            X_plus_mmj_matrix[i,j] = X_mmj_matrix[i,j]\n",
    "            \n",
    "    cal_n_mmj_new(X_plus_distance_matrix, X_plus_mmj_matrix, N)\n",
    " \n",
    "    return X_plus_mmj_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c308cd1d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(500, 2)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6154269a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b33c3634",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.45842121, 0.76526635]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_pt =  np.random.random((1,2))\n",
    "new_pt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "51b96311",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check new point does not belong to X\n",
    "\n",
    "for ii in X:\n",
    "    if np.allclose(ii, new_pt) or np.sum(np.abs(ii - new_pt)) < 1e-10:\n",
    "        print(\"new_pt is in X!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fc1e1438",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(501, 2)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_plus = np.concatenate((X, new_pt), axis=0)\n",
    "X_plus.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "dfdc1859",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cold start calculation of the APPD matrix by Floyd-Warshall algorithm, time_used: 106.715s.\n"
     ]
    }
   ],
   "source": [
    "# Test cold-start calculation of the APPD matrix by variant of the Floyd-Warshall algorithm.\n",
    "\n",
    "\n",
    "start = time.time()\n",
    "X_plus_mmj_matrix_Floyd_Warshall_python = cal_mmj_variant_of_Floyd_Warshall_python(X_plus)\n",
    "end = time.time()\n",
    "time_used = end - start\n",
    "time_used = np.round(time_used, 3)\n",
    "print(f\"Cold start calculation of the APPD matrix by Floyd-Warshall algorithm, time_used: {time_used}s.\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed0297df",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "459e830b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cold start calculation of the APPD matrix by MST_shortest_path algorithm, time_used: 25.984s.\n"
     ]
    }
   ],
   "source": [
    "# Test cold-start calculation of the APPD matrix by MST_shortest_path algorithm.\n",
    "\n",
    "start = time.time()\n",
    "X_plus_mmj_matrix_MST_shortest_path = cal_mmj_matrix_by_shortest_path_on_minimum_spanning_tree(X_plus)\n",
    "end = time.time()\n",
    "time_used = end - start\n",
    "time_used = np.round(time_used, 3)\n",
    "print(f\"Cold start calculation of the APPD matrix by MST_shortest_path algorithm, time_used: {time_used}s.\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "b27d936a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Warm-start calculation of the APPD matrix by Algorithm 1, time_used: 3.153s.\n"
     ]
    }
   ],
   "source": [
    "# Test warm-start calculation of the APPD matrix by Algorithm 1.\n",
    "\n",
    "X_mmj_matrix = cal_mmj_matrix_by_algo_4_Calculation_and_Copy(X)\n",
    "\n",
    "start = time.time()\n",
    "X_plus_mmj_matrix_algo_1_warm = cal_mmj_matrix_algo_1_warm_start(X_plus, X_mmj_matrix)\n",
    "end = time.time()\n",
    "time_used = end - start\n",
    "time_used = np.round(time_used, 3)\n",
    "\n",
    "print(f\"Warm-start calculation of the APPD matrix by Algorithm 1, time_used: {time_used}s.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "213687ac",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "1.7459200751801518e-11\n"
     ]
    }
   ],
   "source": [
    "\n",
    "print(np.allclose(X_plus_mmj_matrix_Floyd_Warshall_python, X_plus_mmj_matrix_algo_1_warm))\n",
    "print(np.sum(np.abs(X_plus_mmj_matrix_Floyd_Warshall_python - X_plus_mmj_matrix_algo_1_warm)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "909762f9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "2.137301446936135e-11\n"
     ]
    }
   ],
   "source": [
    "print(np.allclose(X_plus_mmj_matrix_MST_shortest_path, X_plus_mmj_matrix_algo_1_warm))\n",
    "print(np.sum(np.abs(X_plus_mmj_matrix_MST_shortest_path - X_plus_mmj_matrix_algo_1_warm)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "676ea46f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Therefore, we can conclude warm-start of Algorithm 1 is faster than cold-start of other algorithms.\n",
    "# This is especially useful when the graph is a directed dense graph, where we cannot use\n",
    "# Algorithm 4 (MMJ distance by Calculation and Copy)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "697a90fb",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64106fde",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "abeea006",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}