2 Test warm-start calculation of the APSP matrix by Algorithm 1 in directed graph.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8c341f4-72ec-41d9-8094-82d124d0d245",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4374739c",
   "metadata": {},
   "outputs": [],
   "source": [
    "exec(open(\"./funcs/tool_funcs.py\").read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d29ac9bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortest_path_n_to_r(distance_matrix, shortest_path_matrix, n, r):\n",
    "    max_jump_list = []\n",
    "    for t in range(n):\n",
    "        m_jump =  distance_matrix[n,t] + shortest_path_matrix[t,r]\n",
    "        max_jump_list.append(m_jump)\n",
    "    return np.min(max_jump_list)\n",
    "\n",
    "def shortest_path_r_to_n(distance_matrix, shortest_path_matrix, n, r):\n",
    "    max_jump_list = []\n",
    "    for t in range(n):\n",
    "        m_jump =  shortest_path_matrix[r,t] + distance_matrix[t, n] \n",
    "        max_jump_list.append(m_jump)\n",
    "    return np.min(max_jump_list)\n",
    "\n",
    "     \n",
    "def cal_n_shortest_path(distance_matrix, shortest_path_matrix, n):\n",
    "    for r in range(n):\n",
    "        shortest_path_matrix[n,r] = shortest_path_n_to_r(distance_matrix, shortest_path_matrix, n, r)\n",
    "        shortest_path_matrix[r,n] = shortest_path_r_to_n(distance_matrix, shortest_path_matrix, n, r)\n",
    "        \n",
    "    for i in range(n):        \n",
    "        for j in range(n):\n",
    "            if i < j:\n",
    "                shortest_path_matrix[i,j] =  update_shortest_path_ij(distance_matrix, shortest_path_matrix, n, i, j)\n",
    "                shortest_path_matrix[j,i] =  update_shortest_path_ij(distance_matrix, shortest_path_matrix, n, j, i)\n",
    "                \n",
    "def update_shortest_path_ij(distance_matrix, shortest_path_matrix, n, i, j):\n",
    "    m1 = shortest_path_matrix[i,j]\n",
    "    m2 =  shortest_path_matrix[i,n] + shortest_path_matrix[n,j] \n",
    "    return np.min((m1,m2))\n",
    "\n",
    "def cal_shortest_path_matrix_algo_1_python(distance_matrix):\n",
    "    \n",
    "  \n",
    "    N = len(distance_matrix)\n",
    "   \n",
    "    shortest_path_matrix = np.zeros((N,N))\n",
    "\n",
    "    shortest_path_matrix[0,1] = distance_matrix[0,1]\n",
    "    shortest_path_matrix[1,0] = distance_matrix[1,0]\n",
    " \n",
    "    for kk in range(2,N):\n",
    "        cal_n_shortest_path(distance_matrix, shortest_path_matrix, kk)\n",
    "    return shortest_path_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6f5a1886",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2846295f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6154269a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  0. 612. 457. 440.  32. 132. 630.   2. 880. 742.]\n",
      " [396.   0. 125. 946. 404. 382. 227. 546. 794.  66.]\n",
      " [777. 669.   0. 549. 210. 786.  41. 980. 868. 696.]\n",
      " [214. 536. 228.   0. 459. 801. 661. 938. 781. 346.]\n",
      " [390. 890. 999. 668.   0. 774. 159. 710. 922. 123.]\n",
      " [ 25. 846.  63. 477. 429.   0. 542. 365. 563. 699.]\n",
      " [571. 856. 193. 296. 125. 702.   0. 200. 101. 744.]\n",
      " [366. 499.  54. 178. 319. 774. 386.   0. 125.  41.]\n",
      " [664. 339. 518. 928. 737. 860. 725. 510.   0. 190.]\n",
      " [111. 446. 375. 641. 938. 299. 667. 520. 706.   0.]]\n"
     ]
    }
   ],
   "source": [
    "\n",
    "X_num_nodes = 300\n",
    "X_plus_num_nodes = 301\n",
    " \n",
    " \n",
    "X_plus_distance_matrix = create_distance_matrix(X_plus_num_nodes)\n",
    "\n",
    "\n",
    "print(X_plus_distance_matrix[:10, :10])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "175bcb36",
   "metadata": {},
   "outputs": [],
   "source": [
    "X_distance_matrix = np.zeros((X_num_nodes,X_num_nodes))\n",
    "for i in range(X_num_nodes):  \n",
    "    for j in range(X_num_nodes): \n",
    "        X_distance_matrix[i,j] = X_plus_distance_matrix[i,j]\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "fba6fb9d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(300, 300)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_distance_matrix.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b22f1fdb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(301, 301)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_plus_distance_matrix.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "3823d649",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  0. 612. 457. 440.  32.]\n",
      " [396.   0. 125. 946. 404.]\n",
      " [777. 669.   0. 549. 210.]\n",
      " [214. 536. 228.   0. 459.]\n",
      " [390. 890. 999. 668.   0.]]\n"
     ]
    }
   ],
   "source": [
    "print(X_distance_matrix[:5, :5])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "6a413018",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  0. 612. 457. 440.  32.]\n",
      " [396.   0. 125. 946. 404.]\n",
      " [777. 669.   0. 549. 210.]\n",
      " [214. 536. 228.   0. 459.]\n",
      " [390. 890. 999. 668.   0.]]\n"
     ]
    }
   ],
   "source": [
    "print(X_plus_distance_matrix[:5, :5])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b22da0f0",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "dfdc1859",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cold start calculation of the APSP matrix by Floyd-Warshall algorithm, time_used: 28.937s.\n"
     ]
    }
   ],
   "source": [
    "# Test cold-start calculation of the APSP matrix by Floyd-Warshall algorithm.\n",
    "\n",
    "\n",
    "start = time.time()\n",
    "X_plus_APSP_matrix_Floyd_Warshall_python = floyd_warshall(X_plus_distance_matrix)\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 APSP matrix by Floyd-Warshall algorithm, time_used: {time_used}s.\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ed0297df",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "X_APSP_matrix = floyd_warshall(X_distance_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "14c191a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(300, 300)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_APSP_matrix.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "ba32e1a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_APSP_matrix_algo_1_warm_start(X_plus_distance_matrix, X_APSP_matrix):\n",
    "\n",
    "    N = len(X_APSP_matrix)\n",
    "    \n",
    "    N_plus_one = N + 1\n",
    "   \n",
    "    X_plus_APSP_matrix = np.zeros((N_plus_one, N_plus_one))\n",
    "    \n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            X_plus_APSP_matrix[i,j] = X_APSP_matrix[i,j]\n",
    "            \n",
    "    cal_n_shortest_path(X_plus_distance_matrix, X_plus_APSP_matrix, N)\n",
    " \n",
    "    return X_plus_APSP_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "b27d936a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Warm-start calculation of the APSP matrix by Algorithm 1, time_used: 0.686s.\n"
     ]
    }
   ],
   "source": [
    "# Test warm-start calculation of the APSP matrix by Algorithm 1.\n",
    " \n",
    "start = time.time()\n",
    "X_plus_APSP_matrix_algo_1_warm = cal_APSP_matrix_algo_1_warm_start(X_plus_distance_matrix, X_APSP_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 APSP matrix by Algorithm 1, time_used: {time_used}s.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "213687ac",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "\n",
    "print(np.allclose(X_plus_APSP_matrix_Floyd_Warshall_python, X_plus_APSP_matrix_algo_1_warm))\n",
    "print(np.sum(np.abs(X_plus_APSP_matrix_Floyd_Warshall_python - X_plus_APSP_matrix_algo_1_warm)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "676ea46f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Therefore, we can conclude warm-start of Algorithm 1 is faster than cold-start of Floyd-Warshall algorithm,\n",
    "# for calculating the All Pairs Shortest Path (APSP) matrix.\n"
   ]
  },
  {
   "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
}