20  Cold-start calculation of all shortest paths on undirected graph - further optimized.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e919a87e",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "# On an undirected graph, the adjacency matrix is symmetric.\n",
    "\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": "87a4ced8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_candidate_node_list_symmetric(i, j, shortest_path_vectors, 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_vectors[0][j] < shortest_path_vectors[0][t] + shortest_path_vectors[1][t]:\n",
    "            pass\n",
    "        else:\n",
    "            candidate_node_list.append(t)\n",
    "    candidate_node_list.append(j)\n",
    " \n",
    "    return candidate_node_list\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "08f2b99a",
   "metadata": {},
   "outputs": [],
   "source": [
    " \n",
    "def cal_SPD(X_distance_matrix, SPD_path):\n",
    "    temp1= SPD_path[:-1]\n",
    "    temp2= SPD_path[1:]\n",
    "    llll = [X_distance_matrix[temp1[i],temp2[i]] for i in range(len(temp1))]\n",
    "    return np.sum(llll) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fc2c5502",
   "metadata": {},
   "outputs": [],
   "source": [
    " \n",
    "def check_shortest_path_SPD(i,j, X_distance_matrix, SPD, path):\n",
    "    \n",
    "    \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 == SPD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "5c88ac44",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def dijkstra_cal_previous_nodes(adj_matrix, start):\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)]  \n",
    "\n",
    "    while priority_queue:\n",
    "        current_distance, current_node = heapq.heappop(priority_queue)\n",
    "\n",
    "        if current_distance > distances[current_node]:\n",
    "            continue\n",
    " \n",
    "        for neighbor, weight in enumerate(adj_matrix[current_node]):\n",
    "            if weight > 0:  \n",
    "                distance = current_distance + weight\n",
    " \n",
    "                if distance < distances[neighbor]:\n",
    "                    distances[neighbor] = distance\n",
    "                    previous_nodes[neighbor] = current_node\n",
    "                    heapq.heappush(priority_queue, (distance, neighbor))\n",
    " \n",
    "    return previous_nodes\n",
    "\n",
    "def dijkstra_show_path_from_previous_nodes(previous_nodes, start, end): \n",
    "    path = []\n",
    "    current = end\n",
    "    while current != -1:\n",
    "        path.append(current)\n",
    "        current = previous_nodes[current]\n",
    "    path.reverse()\n",
    "    return path if path[0] == start else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "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_cold_start_undirected_graph(i, j, shortest_path_vectors, X_distance_matrix):\n",
    "    candidate_node_list = cal_candidate_node_list_symmetric(i, j, shortest_path_vectors, X_distance_matrix)\n",
    "\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",
    "\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",
    "    previous_nodes_i = dijkstra_cal_previous_nodes(small_matrix, 0)\n",
    "    previous_nodes_j = dijkstra_cal_previous_nodes(small_matrix, K - 1)\n",
    "\n",
    "    for m in temp_list:\n",
    "        # There is no need to call dijkstra_show_path for each node m.\n",
    "        # temp_path1 = dijkstra_show_path(small_matrix, 0, m)\n",
    "        # temp_path2 = dijkstra_show_path(small_matrix, m, K - 1)\n",
    " \n",
    "        temp_path1 = dijkstra_show_path_from_previous_nodes(previous_nodes_i, 0, m)\n",
    "        temp_path2 = dijkstra_show_path_from_previous_nodes(previous_nodes_j, K - 1, m)\n",
    "        temp_path2 = temp_path2[::-1]\n",
    "   \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": 11,
   "id": "7bd94ae3",
   "metadata": {},
   "outputs": [],
   "source": [
    " \n",
    "\n",
    "def dijkstra_one_to_all_simple(distance_matrix, src):\n",
    "    \n",
    "    N = len(distance_matrix)\n",
    "    dist = [np.inf] * N\n",
    "    dist[src] = 0\n",
    "    visited = [False] * N\n",
    "\n",
    "    # Priority queue: (distance, node)\n",
    "    pq = [(0, src)]\n",
    "    \n",
    "    while pq:\n",
    "        current_dist, u = heapq.heappop(pq)\n",
    "\n",
    "        if visited[u]:\n",
    "            continue\n",
    "        visited[u] = True\n",
    "\n",
    "        # Update distances for neighbors\n",
    "        for v in range(N):\n",
    "            if not visited[v] and distance_matrix[u][v] > 0:\n",
    "                new_dist = current_dist + distance_matrix[u][v]\n",
    "                if new_dist < dist[v]:\n",
    "                    dist[v] = new_dist\n",
    "                    heapq.heappush(pq, (new_dist, v))\n",
    "\n",
    "    return np.array(dist)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9f59b13b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_dis_matrix_symmetric(dist_matrix):\n",
    "    n = len(dist_matrix)    \n",
    " \n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            if i < j:\n",
    "                dist_matrix[j,i] = dist_matrix[i,j]\n",
    " \n",
    "    return dist_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "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",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "de2ce185",
   "metadata": {},
   "outputs": [],
   "source": [
    "X_distance_matrix = make_dis_matrix_symmetric(X_distance_matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "1cba1c0b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0., 952., 405., ..., 208., 152., 808.],\n",
       "       [952.,   0., 557., ..., 912., 737.,  17.],\n",
       "       [405., 557.,   0., ..., 932., 459., 276.],\n",
       "       ...,\n",
       "       [208., 912., 932., ...,   0., 984., 276.],\n",
       "       [152., 737., 459., ..., 984.,   0., 241.],\n",
       "       [808.,  17., 276., ..., 276., 241.,   0.]])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_distance_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "fb4b6901",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "N = len(X_distance_matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "f63bdabe",
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 44\n",
    "j = 90\n",
    " \n",
    "SPD_path = dijkstra_show_path(X_distance_matrix, i, j)\n",
    "\n",
    " \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9f1fefd",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "024e2dff",
   "metadata": {},
   "outputs": [],
   "source": [
    "# SPD stands for shortest path distance.\n",
    "\n",
    "SPD = cal_SPD(X_distance_matrix, SPD_path)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "87b16507",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check_shortest_path_SPD(i,j, X_distance_matrix, SPD, SPD_path)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "c44c1608",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "t1 = dijkstra_one_to_all_simple(X_distance_matrix, i)\n",
    "t2 = dijkstra_one_to_all_simple(X_distance_matrix, j)\n",
    "\n",
    "shortest_path_vectors = [t1, t2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "60bbd478",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "candidate_node_list:\n",
      "[44, 10, 26, 28, 43, 48, 60, 65, 69, 82, 83, 88, 98, 90]\n",
      "shortest_path: \n",
      "[44, 28, 65, 90]\n"
     ]
    }
   ],
   "source": [
    "all_paths_list = cal_all_paths_cold_start_undirected_graph(i, j, shortest_path_vectors, X_distance_matrix)\n",
    "\n",
    "print(\"shortest_path: \")\n",
    "   \n",
    "print(SPD_path)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "f0142716",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[44, 28, 65, 90] True\n",
      "[44, 98, 60, 69, 10, 90] True\n",
      "[44, 26, 88, 82, 83, 48, 43, 90] True\n"
     ]
    }
   ],
   "source": [
    " \n",
    "for path_i in all_paths_list:\n",
    "    aaa = check_shortest_path_SPD(i,j, X_distance_matrix, SPD, path_i)\n",
    "    print(path_i, aaa)\n",
    "\n"
   ]
  }
 ],
 "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
}