test Algorithm 1 warm-start  in directed graph.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d8c341f4-72ec-41d9-8094-82d124d0d245",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "exec(open(\"./funcs/mmj_cal_functions.py\").read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "34c6d6cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "aab4299f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_mmj_variant_of_Floyd_Warshall_python_dis_matrix(distance_matrix):\n",
    "    n = len(distance_matrix)    \n",
    "    p = distance_matrix.copy()\n",
    " \n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            if i != j:\n",
    "                for k in range(n):\n",
    "                    if i != k and j != k:\n",
    "                        p[j,k] = min (p[j,k], max (p[j,i], p[i,k])) \n",
    "    return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a3a2c2d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_mmj_matrix_algo_1_python_dis_matrix(distance_matrix):\n",
    " \n",
    "    N = len(distance_matrix)\n",
    "   \n",
    "    mmj_matrix = np.zeros((N,N))\n",
    "\n",
    "    mmj_matrix[0,1] = distance_matrix[0,1]\n",
    "    mmj_matrix[1,0] = distance_matrix[1,0]\n",
    " \n",
    "    for kk in range(2,N):\n",
    "        cal_n_mmj(distance_matrix, mmj_matrix, kk)\n",
    "    return mmj_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2846295f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "2e4c391f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "\n",
    "# create distance matrix of a directed graph\n",
    "\n",
    "def create_distance_matrix(edges, num_nodes):\n",
    " \n",
    "    dist_matrix = np.full((num_nodes, num_nodes), np.inf)\n",
    " \n",
    "    np.fill_diagonal(dist_matrix, 0)\n",
    " \n",
    "    for u, v, w in edges:\n",
    "        dist_matrix[u, v] = w\n",
    "    \n",
    "    return dist_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6154269a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  0. 851. 388. 132. 988. 541. 444. 811. 626. 464.]\n",
      " [241.   0. 903. 565. 424. 175. 158. 736.  22. 696.]\n",
      " [843. 898.   0.  57. 210. 888. 795. 456. 675. 963.]\n",
      " [536. 759. 729.   0. 488. 505. 100. 587. 370. 743.]\n",
      " [644. 647. 508.  22.   0. 115. 973. 530.  69. 672.]\n",
      " [323. 284. 474.  63. 217.   0. 444. 395. 899. 488.]\n",
      " [279. 446. 534. 726. 678. 200.   0. 577. 691. 467.]\n",
      " [ 37. 638. 792. 764. 251. 164. 821.   0. 630. 408.]\n",
      " [448. 416. 724. 431. 709. 454. 354. 484.   0. 223.]\n",
      " [943. 491.  18. 764. 225. 252.  82. 445. 744.   0.]]\n"
     ]
    }
   ],
   "source": [
    "\n",
    "X_num_nodes = 200\n",
    "X_plus_num_nodes = 201\n",
    "\n",
    "edges = []\n",
    "\n",
    "for u in range(X_plus_num_nodes):  \n",
    "    for v in range(X_plus_num_nodes): \n",
    "        if u != v:\n",
    "            w = int(random.uniform(1, 1000))\n",
    "            edges.append((u, v, w))\n",
    " \n",
    "X_plus_distance_matrix = create_distance_matrix(edges, X_plus_num_nodes)\n",
    "\n",
    "print(X_plus_distance_matrix[:10, :10])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "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": 8,
   "id": "fba6fb9d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(200, 200)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_distance_matrix.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b22f1fdb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(201, 201)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_plus_distance_matrix.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "3823d649",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  0. 851. 388. 132. 988.]\n",
      " [241.   0. 903. 565. 424.]\n",
      " [843. 898.   0.  57. 210.]\n",
      " [536. 759. 729.   0. 488.]\n",
      " [644. 647. 508.  22.   0.]]\n"
     ]
    }
   ],
   "source": [
    "print(X_distance_matrix[:5, :5])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6a413018",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  0. 851. 388. 132. 988.]\n",
      " [241.   0. 903. 565. 424.]\n",
      " [843. 898.   0.  57. 210.]\n",
      " [536. 759. 729.   0. 488.]\n",
      " [644. 647. 508.  22.   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": null,
   "id": "033b4779",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "dfdc1859",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cold start calculation of the APPD matrix by Floyd-Warshall algorithm, time_used: 6.778s.\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_dis_matrix(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 APPD matrix by Floyd-Warshall algorithm, time_used: {time_used}s.\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "ed0297df",
   "metadata": {},
   "outputs": [],
   "source": [
    "X_mmj_matrix = cal_mmj_matrix_algo_1_python_dis_matrix(X_distance_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "14c191a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(200, 200)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_mmj_matrix.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ce43a2d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "ba32e1a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_mmj_matrix_algo_1_warm_start_new(X_plus_distance_matrix, X_mmj_matrix):\n",
    "    \n",
    " \n",
    "    N = len(X_mmj_matrix)\n",
    "    \n",
    "    N_plus_one = N + 1\n",
    "   \n",
    "    X_plus_mmj_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_mmj_matrix[i,j] = X_mmj_matrix[i,j]\n",
    "            \n",
    "    cal_n_mmj(X_plus_distance_matrix, X_plus_mmj_matrix, N)\n",
    " \n",
    "    return X_plus_mmj_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "b27d936a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Warm-start calculation of the APPD matrix by Algorithm 1, time_used: 0.947s.\n"
     ]
    }
   ],
   "source": [
    "# Test warm-start calculation of the APPD matrix by Algorithm 1.\n",
    " \n",
    "start = time.time()\n",
    "X_plus_mmj_matrix_algo_1_warm = cal_mmj_matrix_algo_1_warm_start_new(X_plus_distance_matrix, 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": 17,
   "id": "213687ac",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0.0\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": 18,
   "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
}