test Algorithm 1 for solving the widest path problem.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())\n",
    "exec(open(\"./funcs/Prim_Minimum_Spanning_Tree.py\").read())\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "cc47a24e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# wides_path_exam_graph, widest path problem example graph, \n",
    "# see the upper right graph on https://en.wikipedia.org/wiki/Widest_path_problem\n",
    "\n",
    "pairwise_bandwidth_matrix = pickle.load(  open( \"./data/wides_path_exam_graph.p\", \"rb\" )) \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "0dc0c24a",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[inf, 15., 53.,  0.,  0.,  0.,  0.],\n",
       "       [15., inf, 40.,  0.,  0., 46.,  0.],\n",
       "       [53., 40., inf, 17., 31.,  0.,  0.],\n",
       "       [ 0.,  0., 17., inf, 29.,  0., 40.],\n",
       "       [ 0.,  0., 31., 29., inf,  3.,  8.],\n",
       "       [ 0., 46.,  0.,  0.,  3., inf, 11.],\n",
       "       [ 0.,  0.,  0., 40.,  8., 11., inf]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pairwise_bandwidth_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "31beb80a",
   "metadata": {},
   "outputs": [],
   "source": [
    "graph_nodes_names = {'Dunwich':0, 'Blaxhall':1, 'Harwich':2, 'Clacton':3, 'Tiptree':4, 'Feering':5, 'Maldon':6}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a630373e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "74239dd0",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., 40., 53., 29., 31., 40., 29.],\n",
       "       [40.,  0., 40., 29., 31., 46., 29.],\n",
       "       [53., 40.,  0., 29., 31., 40., 29.],\n",
       "       [29., 29., 29.,  0., 29., 29., 40.],\n",
       "       [31., 31., 31., 29.,  0., 31., 29.],\n",
       "       [40., 46., 40., 29., 31.,  0., 29.],\n",
       "       [29., 29., 29., 40., 29., 29.,  0.]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Widest_path_matrix_algo_4 = cal_Widest_path_problem_matrix_by_algo_4(pairwise_bandwidth_matrix)\n",
    "Widest_path_matrix_algo_4\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "1567b10d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "29.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = graph_nodes_names[\"Maldon\"]\n",
    "j = graph_nodes_names[\"Feering\"]\n",
    "\n",
    "Widest_path_matrix_algo_4[i,j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fd13e1fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "N = len(pairwise_bandwidth_matrix)\n",
    "for i in range(N):\n",
    "    Widest_path_matrix_algo_4[i,i] = np.inf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "f405f107",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[inf, 40., 53., 29., 31., 40., 29.],\n",
       "       [40., inf, 40., 29., 31., 46., 29.],\n",
       "       [53., 40., inf, 29., 31., 40., 29.],\n",
       "       [29., 29., 29., inf, 29., 29., 40.],\n",
       "       [31., 31., 31., 29., inf, 31., 29.],\n",
       "       [40., 46., 40., 29., 31., inf, 29.],\n",
       "       [29., 29., 29., 40., 29., 29., inf]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Widest_path_matrix_algo_4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c1f29450",
   "metadata": {},
   "outputs": [],
   "source": [
    "# See Section 7 (SOLVING THE WIDEST PATH PROBLEM) of the paper:\n",
    "# https://arxiv.org/abs/2301.05994\n",
    "\n",
    "def wpp_n_to_r(distance_matrix, widest_path_matrix, n, r):\n",
    "    max_jump_list = []\n",
    "    for ttt in range(n):\n",
    "        m_jump = np.min((distance_matrix[n,ttt],widest_path_matrix[ttt,r]))\n",
    "        max_jump_list.append(m_jump)\n",
    "    return np.max(max_jump_list)\n",
    "\n",
    "def wpp_r_to_n(distance_matrix, widest_path_matrix, n, r):\n",
    "    max_jump_list = []\n",
    "    for ttt in range(n):\n",
    "        m_jump = np.min((widest_path_matrix[r,ttt], distance_matrix[ttt, n]))\n",
    "        max_jump_list.append(m_jump)\n",
    "    return np.max(max_jump_list)\n",
    "\n",
    "     \n",
    "def cal_n_wpp(distance_matrix, widest_path_matrix, n):\n",
    "    for i in range(n):\n",
    "        widest_path_matrix[n,i] = wpp_n_to_r(distance_matrix, widest_path_matrix, n, i)\n",
    "        widest_path_matrix[i,n] = wpp_r_to_n(distance_matrix, widest_path_matrix, n, i)\n",
    "        \n",
    "    for i in range(n):        \n",
    "        for j in range(n):\n",
    "            if i < j:\n",
    "                widest_path_matrix[i,j] =  update_wpp_ij(distance_matrix, widest_path_matrix, n, i, j)\n",
    "                widest_path_matrix[j,i] =  update_wpp_ij(distance_matrix, widest_path_matrix, n, j, i)\n",
    "                \n",
    "def update_wpp_ij(distance_matrix, widest_path_matrix, n, i,j):\n",
    "    m1 = widest_path_matrix[i,j]\n",
    "    m2 = np.min((widest_path_matrix[i,n],widest_path_matrix[n,j]))\n",
    "    return np.max((m1,m2))\n",
    "\n",
    "def cal_widest_path_matrix_algo_1_python(distance_matrix):\n",
    " \n",
    "    N = len(distance_matrix)\n",
    "   \n",
    "    widest_path_matrix = np.ones((N,N))*np.inf\n",
    "\n",
    "    widest_path_matrix[0,1] = distance_matrix[0,1]\n",
    "    widest_path_matrix[1,0] = distance_matrix[1,0]\n",
    " \n",
    "    for kk in range(2, N):\n",
    "        cal_n_wpp(distance_matrix, widest_path_matrix, kk)\n",
    "    return widest_path_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "2fdb1448",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[inf, 40., 53., 29., 31., 40., 29.],\n",
       "       [40., inf, 40., 29., 31., 46., 29.],\n",
       "       [53., 40., inf, 29., 31., 40., 29.],\n",
       "       [29., 29., 29., inf, 29., 29., 40.],\n",
       "       [31., 31., 31., 29., inf, 31., 29.],\n",
       "       [40., 46., 40., 29., 31., inf, 29.],\n",
       "       [29., 29., 29., 40., 29., 29., inf]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Widest_path_matrix_algo_1 = cal_widest_path_matrix_algo_1_python(pairwise_bandwidth_matrix)\n",
    "Widest_path_matrix_algo_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "5cd76527",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "29.0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = graph_nodes_names[\"Maldon\"]\n",
    "j = graph_nodes_names[\"Feering\"]\n",
    "\n",
    "Widest_path_matrix_algo_1[i,j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "658d4389",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(np.allclose(Widest_path_matrix_algo_1, Widest_path_matrix_algo_4))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e0b76a7",
   "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
}