13  Warm-start calculation of path - widest path problem.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e919a87e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c8f75cd9",
   "metadata": {},
   "outputs": [],
   "source": [
    "exec(open(\"./funcs/tool_funcs.py\").read())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "562c9604",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1e12bdac",
   "metadata": {},
   "outputs": [],
   "source": [
    "# For the widest path problem, we need a Max-Heap, rather than a Min-Heap. \n",
    "# We use some techniques to convert a Min-Heap into a Max-Heap.\n",
    "\n",
    "\n",
    "def dijkstra_show_path_widest_path(adj_matrix, start, end):\n",
    " \n",
    "    n = len(adj_matrix)\n",
    "    distances = [0] * n\n",
    "    previous_nodes = [-1] * n\n",
    "    distances[start] = np.inf\n",
    "    \n",
    "    # For the widest path problem, we need a Max-Heap, rather than a Min-Heap.\n",
    "    priority_queue = [(-np.inf, start)]  # (distance, node)\n",
    "\n",
    " \n",
    "    \n",
    "    while priority_queue:\n",
    "       \n",
    "        \n",
    "        # For the widest path problem, we need a Max-Heap, rather than a Min-Heap.\n",
    "        current_distance, current_node = heapq.heappop(priority_queue)\n",
    "        current_distance = -current_distance\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 < np.inf:  \n",
    "                distance = min(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",
    "                    \n",
    "                    # For the widest path problem, we need a Max-Heap, rather than a Min-Heap.\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, widest_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 widest_path_matrix[i,j] > min(widest_path_matrix[i,t], widest_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_widest_path(i, j, widest_path_matrix, X_distance_matrix):\n",
    "    candidate_node_list = cal_candidate_node_list(i, j, widest_path_matrix, X_distance_matrix)\n",
    "    # print(candidate_node_list)\n",
    "   \n",
    "    small_matrix = output_small_matrix(X_distance_matrix, candidate_node_list)\n",
    "    path = dijkstra_show_path_widest_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": "9a37675d",
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 100\n",
    "\n",
    "X_distance_matrix = create_distance_matrix(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b5d9c1b0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# X_distance_matrix = np.loadtxt(\"./data/X_100_distance_matrix.csv\", delimiter=\",\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "09ec1101",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "5485d3a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# For the widest path problem, a node's bandwidth to itself should be infinity.\n",
    "\n",
    "\n",
    "N = len(X_distance_matrix)\n",
    "for i in range(N):\n",
    "    X_distance_matrix[i,i] = np.inf\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "8e87922b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    " \n",
    "widest_path_matrix = floyd_warshall_widest_path(X_distance_matrix)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "f63bdabe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 65, 92, 90, 77, 58, 78, 72, 26, 85, 94, 6, 97, 20, 50]\n",
      "[10, 65, 92, 90, 77, 58, 78, 72, 26, 85, 94, 6, 97, 20, 50]\n"
     ]
    }
   ],
   "source": [
    "i = 10\n",
    "j = 50\n",
    "\n",
    "path1 = dijkstra_show_path_widest_path(X_distance_matrix, i, j)  \n",
    "path2 = cal_path_warm_start_widest_path(i, j, widest_path_matrix, X_distance_matrix) \n",
    "\n",
    "print(path1)\n",
    "print(path2)\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "39504b73",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time_used1_warm:  0.303\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_widest_path(i, j, widest_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": 13,
   "id": "6834652b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time_used2_cold:  0.179\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_widest_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": 14,
   "id": "11a63db8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ratio:  1.693\n"
     ]
    }
   ],
   "source": [
    "print(\"Ratio: \", np.round(time_used1_warm/time_used2_cold, 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "c285d758",
   "metadata": {},
   "outputs": [],
   "source": [
    "# It seems a warm-start calculation of widest path can be less efficient than cold-start. \n",
    "# The speculative reason is that the size of candidate_node_list is quite large.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8fb5fdb9",
   "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
}