10  Warm-start calculation of path - shortest path problem.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e919a87e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "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": 2,
   "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": 3,
   "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": 4,
   "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": 5,
   "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": 6,
   "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",
    "   \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": 7,
   "id": "025ebebe",
   "metadata": {},
   "outputs": [],
   "source": [
    "# N = 100\n",
    "\n",
    "# X_distance_matrix = create_distance_matrix(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "8e87922b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "X_distance_matrix = np.loadtxt(\"./data/X_100_distance_matrix.csv\", delimiter=\",\")\n",
    "\n",
    "shortest_path_matrix = floyd_warshall(X_distance_matrix)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "fb4b6901",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "N = len(X_distance_matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f63bdabe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 19, 69, 60, 37, 57, 53, 5]\n",
      "[2, 19, 69, 60, 37, 57, 53, 5]\n"
     ]
    }
   ],
   "source": [
    "i = 2\n",
    "j = 5\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": null,
   "id": "76900a86",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0d9399c5",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "39504b73",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time_used1_warm:  0.012\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "for i in range(N):\n",
    "    for j in range(N):\n",
    "#         if i != j:\n",
    "        if i == 2:\n",
    "            path2 = cal_path_warm_start(i, j, shortest_path_matrix, X_distance_matrix)\n",
    "end = time.time()\n",
    "\n",
    " \n",
    "time_used1_warm = end - start\n",
    "time_used1_warm = np.round(time_used1_warm, 3)\n",
    "\n",
    "print(\"time_used1_warm: \", time_used1_warm)            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "6834652b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time_used2_cold:  0.116\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "for i in range(N):\n",
    "    for j in range(N):\n",
    "#         if i != j:\n",
    "        if i == 2:\n",
    "            path1 = dijkstra_show_path(X_distance_matrix, i, j)\n",
    "end = time.time()\n",
    "\n",
    " \n",
    "time_used2_cold = end - start\n",
    "time_used2_cold = np.round(time_used2_cold, 3)\n",
    "\n",
    "print(\"time_used2_cold: \", time_used2_cold) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "11a63db8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "f8f2abf3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ratio:  0.103\n"
     ]
    }
   ],
   "source": [
    "print(\"Ratio: \", np.round(time_used1_warm/time_used2_cold, 3))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c285d758",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "017d5b31",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb97642f",
   "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
}