21  All shortest paths calculated by Algorithm 8 may be incomplete.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e919a87e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b013d490",
   "metadata": {},
   "outputs": [],
   "source": [
    "# All shortest paths calculated by Algorithm 8 and 9 may be incomplete.\n",
    "# Here is an example of four nodes.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "562c9604",
   "metadata": {},
   "outputs": [],
   "source": [
    "exec(open(\"./funcs/tool_funcs.py\").read())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "78d3581b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1e12bdac",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dijkstra_show_path(adj_matrix, start, end):\n",
    " \n",
    "    n = len(adj_matrix)\n",
    "    distances = [float('inf')] * n\n",
    "    previous_nodes = [-1] * n\n",
    "    distances[start] = 0\n",
    "    priority_queue = [(0, start)]  # (distance, node)\n",
    "\n",
    "    while priority_queue:\n",
    "        current_distance, current_node = heapq.heappop(priority_queue)\n",
    "\n",
    "        # Stop if we reached the destination node\n",
    "        if current_node == end:\n",
    "            break\n",
    "\n",
    "        # If the distance is no longer optimal, skip\n",
    "        if current_distance > distances[current_node]:\n",
    "            continue\n",
    "\n",
    "        # Explore neighbors\n",
    "        for neighbor, weight in enumerate(adj_matrix[current_node]):\n",
    "            if weight > 0:  # Only consider edges with weight > 0\n",
    "                distance = current_distance + weight\n",
    "\n",
    "                # Update distance if it's better\n",
    "                if distance < distances[neighbor]:\n",
    "                    distances[neighbor] = distance\n",
    "                    previous_nodes[neighbor] = current_node\n",
    "                    heapq.heappush(priority_queue, (distance, neighbor))\n",
    "\n",
    "    # Reconstruct the path from end to start\n",
    "    path = []\n",
    "    current = end\n",
    "    while current != -1:\n",
    "        path.append(current)\n",
    "        current = previous_nodes[current]\n",
    "    path.reverse()\n",
    "\n",
    "    # If the start node isn't reachable, return an empty path\n",
    "    return path if path[0] == start else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8c3c2a38",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a96d92af",
   "metadata": {},
   "outputs": [],
   "source": [
    "def translate_path(path, candidate_node_list):\n",
    "    new_path = [candidate_node_list[i] for i in path]\n",
    "    return new_path\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ad6bbacb",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ff1876be",
   "metadata": {},
   "outputs": [],
   "source": [
    "def output_small_matrix(X_distance_matrix, candidate_node_list):\n",
    "    small_matrix = np.zeros((len(candidate_node_list), len(candidate_node_list)))\n",
    "    for i, ii in enumerate(candidate_node_list):\n",
    "        for j, jj in enumerate(candidate_node_list):\n",
    "            small_matrix[i,j] = X_distance_matrix[ii, jj]\n",
    "    return small_matrix\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9c210f08",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_candidate_node_list(i, j, shortest_path_matrix, X_distance_matrix):\n",
    "    \n",
    "    N = len(X_distance_matrix)\n",
    "    \n",
    "    remaining_list = [k for k in np.arange(N) if k != i and k != j]\n",
    "    candidate_node_list = []\n",
    "    candidate_node_list.append(i)\n",
    "    for t in remaining_list:\n",
    "        if shortest_path_matrix[i,j] < shortest_path_matrix[i,t] + shortest_path_matrix[t,j]:\n",
    "            pass\n",
    "        else:\n",
    "            candidate_node_list.append(t)\n",
    "    candidate_node_list.append(j)\n",
    " \n",
    "    return candidate_node_list\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ae965627",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def cal_path_warm_start(i, j, shortest_path_matrix, X_distance_matrix):\n",
    "    candidate_node_list = cal_candidate_node_list(i, j, shortest_path_matrix, X_distance_matrix)\n",
    "    print(\"candidate_node_list:\")\n",
    "    print(candidate_node_list)\n",
    "   \n",
    "    small_matrix = output_small_matrix(X_distance_matrix, candidate_node_list)\n",
    "    path = dijkstra_show_path(small_matrix, 0, len(candidate_node_list) - 1)\n",
    "    path = translate_path(path, candidate_node_list)\n",
    "    \n",
    "    return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4100db2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# APPD stands for all points path distance (APPD).\n",
    "\n",
    "def check_shortest_path(i,j, X_distance_matrix, APPD_matrix, path):\n",
    "    temp1= path[:-1]\n",
    "    temp2= path[1:]\n",
    "    llll = [X_distance_matrix[temp1[i],temp2[i]] for i in range(len(temp1))]\n",
    "    ooo = np.sum(llll)\n",
    "    return ooo == APPD_matrix[i,j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "75b32da0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_if_temp_path_already_in(all_paths_list, temp_path):\n",
    "    aa = set(temp_path)\n",
    "    for bb in all_paths_list:\n",
    "        bb = set(bb)\n",
    "        if aa == bb:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "def cal_all_paths_warm_start(i, j, shortest_path_matrix, X_distance_matrix):\n",
    "    candidate_node_list = cal_candidate_node_list(i, j, shortest_path_matrix, X_distance_matrix)\n",
    " \n",
    "    small_matrix = output_small_matrix(X_distance_matrix, candidate_node_list)\n",
    "    path = dijkstra_show_path(small_matrix, 0, len(candidate_node_list) - 1)\n",
    "\n",
    "    all_paths_list = []\n",
    "    all_paths_list.append(path)\n",
    "\n",
    "    K = len(candidate_node_list)\n",
    "    # temp_list = [q for q in range(K) if q not in path]\n",
    "    \n",
    "    temp_list = [q for q in range(1, K - 1)]\n",
    "\n",
    "    for m in temp_list:\n",
    "        temp_path1 = dijkstra_show_path(small_matrix, 0, m)\n",
    "        temp_path2 = dijkstra_show_path(small_matrix, m, K - 1)\n",
    "        temp_path =  temp_path1[:-1] + temp_path2\n",
    "        if not check_if_temp_path_already_in(all_paths_list, temp_path):\n",
    "            all_paths_list.append(temp_path)\n",
    "\n",
    "    all_paths_list = [translate_path(ppp, candidate_node_list) for ppp in all_paths_list]    \n",
    "\n",
    "    return all_paths_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "025ebebe",
   "metadata": {},
   "outputs": [],
   "source": [
    "# N = 1000\n",
    "\n",
    "# X_distance_matrix = create_distance_matrix(N)\n",
    "\n",
    "# X_distance_matrix = np.loadtxt(\"./data/X_100_distance_matrix.csv\", delimiter=\",\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "91696c81",
   "metadata": {},
   "outputs": [],
   "source": [
    "X_distance_matrix = np.array([[  0., 5., 12., np.inf],\n",
    "       [np.inf,   0.,  7., 10.],\n",
    "       [np.inf,   np.inf,  0., 3.],\n",
    "       [np.inf,  np.inf,   np.inf, 0.]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "8e87922b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "\n",
    "shortest_path_matrix = floyd_warshall(X_distance_matrix)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "fb4b6901",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "N = len(X_distance_matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "f63bdabe",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "candidate_node_list:\n",
      "[0, 1, 2, 3]\n",
      "[0, 1, 3]\n",
      "[0, 1, 3]\n"
     ]
    }
   ],
   "source": [
    "i = 0\n",
    "j = 3\n",
    " \n",
    "path1 = dijkstra_show_path(X_distance_matrix, i, j)\n",
    "    \n",
    "path2 = cal_path_warm_start(i, j, shortest_path_matrix, X_distance_matrix)   \n",
    "print(path1)\n",
    "print(path2)\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "87b16507",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check_shortest_path(i,j, X_distance_matrix, shortest_path_matrix, path2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "60bbd478",
   "metadata": {},
   "outputs": [],
   "source": [
    "all_paths_list = cal_all_paths_warm_start(i, j, shortest_path_matrix, X_distance_matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "f0142716",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3] True\n",
      "[0, 2, 3] True\n"
     ]
    }
   ],
   "source": [
    "for path_i in all_paths_list:\n",
    "    aaa = check_shortest_path(i,j, X_distance_matrix, shortest_path_matrix, path_i)\n",
    "    print(path_i, aaa)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "3e0e54ed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15.0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_path_matrix[0, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "0fe31940",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check_shortest_path(i,j, X_distance_matrix, shortest_path_matrix, [0, 1, 3])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "38845ad0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check_shortest_path(i,j, X_distance_matrix, shortest_path_matrix, [0, 2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "77c49a3b",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check_shortest_path(i,j, X_distance_matrix, shortest_path_matrix, [0, 1, 2, 3])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "ceb01389",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Path [0, 1, 2, 3] is missed in all_paths_list.\n",
    "\n",
    "# However, as indicated in Section 4.4 (Maintaining a key_node_list), \n",
    "# this does not affect the correctness of Algorithm 10 (warm-start calculation of APSP by key_node_list). \n",
    "# Because if all_paths_list is not complete, \n",
    "# the calculated key_node_list is a superset of the actual key_node_list, \n",
    "# this property makes it do not affect the correctness of Algorithm 10. \n",
    " \n",
    "#  A set A is a superset of another set B if all elements of the set B are elements of the set A.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4223fe3e",
   "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
}