Calculate MMJ distance matrix with Algorithm 1 in directed graph.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d8c341f4-72ec-41d9-8094-82d124d0d245",
   "metadata": {},
   "outputs": [],
   "source": [
    "exec(open(\"./funcs/mmj_functions.py\").read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e919a87e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ad25e018",
   "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": 3,
   "id": "606faa7a",
   "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": null,
   "id": "b5de4469",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c504c83c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  0.   7.  55. 883. 293. 330. 296. 130. 542. 732.]\n",
      " [228.   0. 662. 362. 753. 427. 122. 471. 400. 332.]\n",
      " [468. 298.   0.  inf 844. 405. 262.  60. 467. 793.]\n",
      " [223. 426. 387.   0. 758. 678.  89. 821. 474. 821.]\n",
      " [ 48. 509. 205. 496.   0.   6. 292.  94. 955. 669.]\n",
      " [475. 664. 489. 409. 543.   0. 254. 160. 681. 442.]\n",
      " [ 58. 393. 170. 319. 709. 329.   0. 920. 308.  18.]\n",
      " [310. 690. 543. 114. 611. 859.  12.   0. 961. 191.]\n",
      " [765.  67. 282. 947. 762. 284. 411. 239.   0. 600.]\n",
      " [291. 815.   5. 134. 507. 312. 269. 647. 283.   0.]]\n"
     ]
    }
   ],
   "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\n",
    "\n",
    " \n",
    "num_nodes = 100\n",
    "\n",
    "edges = []\n",
    "for _ in range(50000):  \n",
    "    u = random.randint(0, num_nodes - 1)\n",
    "    v = random.randint(0, num_nodes - 1)\n",
    "    if u != v:\n",
    "        w = int(random.uniform(1, 1000))\n",
    "        edges.append((u, v, w))\n",
    " \n",
    "distance_matrix = create_distance_matrix(edges, num_nodes)\n",
    "\n",
    "print(distance_matrix[:10, :10])  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1594fe7a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9ace5d79",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "X_mmj_matrix_python_algo_1 = cal_mmj_matrix_algo_1_python_dis_matrix(distance_matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "090d69da",
   "metadata": {},
   "outputs": [],
   "source": [
    "X_mmj_matrix_python_Floyd_Warshall = cal_mmj_variant_of_Floyd_Warshall_python_dis_matrix(distance_matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1032168",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "2461fc54",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print(np.allclose(X_mmj_matrix_python_algo_1, X_mmj_matrix_python_Floyd_Warshall)) \n",
    "print(np.sum(np.abs(X_mmj_matrix_python_algo_1 - X_mmj_matrix_python_Floyd_Warshall))) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "baaa8d92-4f03-49ed-8bd8-d37415560429",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  7. 18. 18. 11. 11. 13. 16. 14. 18.]\n",
      " [16.  0. 18. 18. 11. 11. 13. 16. 14. 18.]\n",
      " [16.  9.  0. 18. 11. 11. 13. 16. 14. 18.]\n",
      " [23. 23. 23.  0. 23. 23. 23. 23. 23. 23.]\n",
      " [16.  9. 18. 18.  0.  6. 13. 16. 14. 18.]\n",
      " [16.  9. 18. 18. 11.  0. 13. 16. 14. 18.]\n",
      " [16. 15. 18. 18. 15. 15.  0. 16. 15. 18.]\n",
      " [16.  9. 18. 18. 11. 11. 12.  0. 14. 18.]\n",
      " [16. 13. 18. 18. 13. 13. 13. 16.  0. 18.]\n",
      " [16.  9.  5. 15. 11. 11. 13. 16. 14.  0.]]\n"
     ]
    }
   ],
   "source": [
    "print(X_mmj_matrix_python_algo_1[:10, :10])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a414879e-ba89-4c38-a1e2-eec3741363e3",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  7. 18. 18. 11. 11. 13. 16. 14. 18.]\n",
      " [16.  0. 18. 18. 11. 11. 13. 16. 14. 18.]\n",
      " [16.  9.  0. 18. 11. 11. 13. 16. 14. 18.]\n",
      " [23. 23. 23.  0. 23. 23. 23. 23. 23. 23.]\n",
      " [16.  9. 18. 18.  0.  6. 13. 16. 14. 18.]\n",
      " [16.  9. 18. 18. 11.  0. 13. 16. 14. 18.]\n",
      " [16. 15. 18. 18. 15. 15.  0. 16. 15. 18.]\n",
      " [16.  9. 18. 18. 11. 11. 12.  0. 14. 18.]\n",
      " [16. 13. 18. 18. 13. 13. 13. 16.  0. 18.]\n",
      " [16.  9.  5. 15. 11. 11. 13. 16. 14.  0.]]\n"
     ]
    }
   ],
   "source": [
    "print(X_mmj_matrix_python_Floyd_Warshall[:10, :10]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be4fa6af",
   "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
}