a_star.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9f21c1ab-8ba7-4c3c-b5f4-80271df57182",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "config": {
        "linkText": "Export to plot.ly",
        "plotlyServerURL": "https://plot.ly",
        "showLink": false
       },
       "data": [
        {
         "line": {
          "color": "#888",
          "width": 2
         },
         "type": "scatter",
         "x": [
          0,
          0.1,
          null,
          0,
          0.1,
          null,
          0,
          0.1,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.2,
          0.3,
          null,
          0.2,
          0.3,
          null,
          0.2,
          0.3,
          null,
          0.2,
          0.4,
          null,
          0.2,
          0.3,
          null,
          0.3,
          0.4,
          null,
          0.3,
          0.5,
          null,
          0.3,
          0.4,
          null,
          0.3,
          0.5,
          null,
          0.4,
          0.5,
          null,
          0.4,
          0.5,
          null,
          0.4,
          0.5,
          null,
          0.5,
          0.6,
          null,
          0.5,
          0.6,
          null,
          0.5,
          0.9,
          null,
          0.5,
          0.9,
          null
         ],
         "y": [
          0.5,
          0.7,
          null,
          0.5,
          0.6,
          null,
          0.5,
          0.4,
          null,
          0.7,
          0.6,
          null,
          0.7,
          0.4,
          null,
          0.7,
          0.9,
          null,
          0.6,
          0.6,
          null,
          0.6,
          0.4,
          null,
          0.6,
          0.9,
          null,
          0.4,
          0.6,
          null,
          0.4,
          0.4,
          null,
          0.4,
          0.9,
          null,
          0.6,
          0.7,
          null,
          0.4,
          0.7,
          null,
          0.4,
          0.3,
          null,
          0.4,
          0.5,
          null,
          0.9,
          0.3,
          null,
          0.7,
          0.5,
          null,
          0.7,
          0.6,
          null,
          0.3,
          0.5,
          null,
          0.3,
          0.2,
          null,
          0.5,
          0.6,
          null,
          0.5,
          0.5,
          null,
          0.5,
          0.2,
          null,
          0.6,
          0.7,
          null,
          0.5,
          0.7,
          null,
          0.5,
          0.4,
          null,
          0.2,
          0.4,
          null
         ]
        },
        {
         "hoverinfo": "x+y+text",
         "marker": {
          "color": [
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0,
           0
          ],
          "colorscale": [
           [
            0,
            "rgb(0,0,0)"
           ],
           [
            0.3333333333333333,
            "rgb(230,0,0)"
           ],
           [
            0.6666666666666666,
            "rgb(255,210,0)"
           ],
           [
            1,
            "rgb(255,255,255)"
           ]
          ],
          "line": {
           "width": 4
          },
          "reversescale": true,
          "showscale": true,
          "size": 20
         },
         "mode": "markers",
         "text": [
          "Router 0",
          "Router 1",
          "Router 2",
          "Router 3",
          "Router 4",
          "Router 5",
          "Router 6",
          "Router 7",
          "Router 8",
          "Router 9",
          "Router 10",
          "Router 11",
          "Router 12",
          "Router 13",
          "Router 14"
         ],
         "type": "scatter",
         "x": [
          0,
          0.1,
          0.1,
          0.1,
          0.2,
          0.2,
          0.2,
          0.3,
          0.3,
          0.4,
          0.5,
          0.5,
          0.5,
          0.6,
          0.9
         ],
         "y": [
          0.5,
          0.7,
          0.6,
          0.4,
          0.6,
          0.4,
          0.9,
          0.7,
          0.3,
          0.5,
          0.6,
          0.5,
          0.2,
          0.7,
          0.4
         ]
        }
       ],
       "layout": {
        "hovermode": "closest",
        "margin": {
         "b": 25,
         "l": 7,
         "r": 7,
         "t": 35
        },
        "showlegend": false,
        "template": {
         "data": {
          "bar": [
           {
            "error_x": {
             "color": "#2a3f5f"
            },
            "error_y": {
             "color": "#2a3f5f"
            },
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "bar"
           }
          ],
          "barpolar": [
           {
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "barpolar"
           }
          ],
          "carpet": [
           {
            "aaxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "baxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "type": "carpet"
           }
          ],
          "choropleth": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "choropleth"
           }
          ],
          "contour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "contour"
           }
          ],
          "contourcarpet": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "contourcarpet"
           }
          ],
          "heatmap": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmap"
           }
          ],
          "heatmapgl": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmapgl"
           }
          ],
          "histogram": [
           {
            "marker": {
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "histogram"
           }
          ],
          "histogram2d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2d"
           }
          ],
          "histogram2dcontour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2dcontour"
           }
          ],
          "mesh3d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "mesh3d"
           }
          ],
          "parcoords": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "parcoords"
           }
          ],
          "pie": [
           {
            "automargin": true,
            "type": "pie"
           }
          ],
          "scatter": [
           {
            "fillpattern": {
             "fillmode": "overlay",
             "size": 10,
             "solidity": 0.2
            },
            "type": "scatter"
           }
          ],
          "scatter3d": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatter3d"
           }
          ],
          "scattercarpet": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattercarpet"
           }
          ],
          "scattergeo": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergeo"
           }
          ],
          "scattergl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergl"
           }
          ],
          "scattermapbox": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattermapbox"
           }
          ],
          "scatterpolar": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolar"
           }
          ],
          "scatterpolargl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolargl"
           }
          ],
          "scatterternary": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterternary"
           }
          ],
          "surface": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "surface"
           }
          ],
          "table": [
           {
            "cells": {
             "fill": {
              "color": "#EBF0F8"
             },
             "line": {
              "color": "white"
             }
            },
            "header": {
             "fill": {
              "color": "#C8D4E3"
             },
             "line": {
              "color": "white"
             }
            },
            "type": "table"
           }
          ]
         },
         "layout": {
          "annotationdefaults": {
           "arrowcolor": "#2a3f5f",
           "arrowhead": 0,
           "arrowwidth": 1
          },
          "autotypenumbers": "strict",
          "coloraxis": {
           "colorbar": {
            "outlinewidth": 0,
            "ticks": ""
           }
          },
          "colorscale": {
           "diverging": [
            [
             0,
             "#8e0152"
            ],
            [
             0.1,
             "#c51b7d"
            ],
            [
             0.2,
             "#de77ae"
            ],
            [
             0.3,
             "#f1b6da"
            ],
            [
             0.4,
             "#fde0ef"
            ],
            [
             0.5,
             "#f7f7f7"
            ],
            [
             0.6,
             "#e6f5d0"
            ],
            [
             0.7,
             "#b8e186"
            ],
            [
             0.8,
             "#7fbc41"
            ],
            [
             0.9,
             "#4d9221"
            ],
            [
             1,
             "#276419"
            ]
           ],
           "sequential": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ],
           "sequentialminus": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ]
          },
          "colorway": [
           "#636efa",
           "#EF553B",
           "#00cc96",
           "#ab63fa",
           "#FFA15A",
           "#19d3f3",
           "#FF6692",
           "#B6E880",
           "#FF97FF",
           "#FECB52"
          ],
          "font": {
           "color": "#2a3f5f"
          },
          "geo": {
           "bgcolor": "white",
           "lakecolor": "white",
           "landcolor": "#E5ECF6",
           "showlakes": true,
           "showland": true,
           "subunitcolor": "white"
          },
          "hoverlabel": {
           "align": "left"
          },
          "hovermode": "closest",
          "mapbox": {
           "style": "light"
          },
          "paper_bgcolor": "white",
          "plot_bgcolor": "#E5ECF6",
          "polar": {
           "angularaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "radialaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "scene": {
           "xaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "yaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "zaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           }
          },
          "shapedefaults": {
           "line": {
            "color": "#2a3f5f"
           }
          },
          "ternary": {
           "aaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "baxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "caxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "title": {
           "x": 0.05
          },
          "xaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          },
          "yaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          }
         }
        },
        "title": {
         "font": {
          "size": 20
         },
         "text": "Network Topology using A* search for fast Packet Routing"
        }
       }
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from map import load_map, show_map, map_15_dict\n",
    "# from map import Map\n",
    "import math\n",
    "\n",
    "show_map(load_map(map_15_dict))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "41924186-a900-49c4-852e-49d7a049d833",
   "metadata": {},
   "outputs": [],
   "source": [
    "class PacketPlanner():\n",
    "    # Construct a PacketPlanner Object\n",
    "    def __init__(self, MapX, start=None, goal=None):\n",
    "        (self.map, self.start, self.goal) = (MapX, start, goal)\n",
    "        (self.closedSet, self.openSet, self.cameFrom) = (set(), {start}, dict())\n",
    "\n",
    "        self.gScore = {key: float('infinity') for key in range(len(self.map.convergence))}\n",
    "        self.gScore[start] = 0.0\n",
    "        \n",
    "        self.fScore = {key: float('infinity') for key in range(len(self.map.convergence))}\n",
    "        self.fScore[start] = self.total_hScore(start)\n",
    "\n",
    "        self.path = self.run_search()\n",
    "        return None\n",
    "\n",
    "    \n",
    "    def reconstruct_path(self, current):\n",
    "        # Reconstructs path after search\n",
    "        total_path = [current]\n",
    "        while current in self.cameFrom.keys():\n",
    "            current = self.cameFrom[current]\n",
    "            total_path.append(current)\n",
    "        return total_path\n",
    "    \n",
    "\n",
    "    def run_search(self):\n",
    "        while not len(self.openSet) == 0:                                   # if openSet is NOT empty\n",
    "            current = self.get_current_node()\n",
    "\n",
    "            if current == self.goal:\n",
    "                self.path = self.reconstruct_path(current)[::-1]\n",
    "                return self.path\n",
    "            else:\n",
    "                self.openSet.remove(current)\n",
    "                self.closedSet.add(current)\n",
    "\n",
    "            for neighbor in self.map.ways[current]:                        # returns neighbors of the node\n",
    "                # ################# EXPERIMENTAL #################\n",
    "                # Map.gScore_setter(self.distance(current, neighbor))\n",
    "                # Map.hScore_setter(self.total_hScore(current))\n",
    "\n",
    "                if neighbor in self.closedSet:\n",
    "                    continue                                                # Ignore the neighbor which is already evaluated.\n",
    "\n",
    "                if not neighbor in self.openSet:                            # Discover a new node\n",
    "                    self.openSet.add(neighbor)\n",
    "\n",
    "                # The distance from start to a neighbor, the distance function may vary depending on location\n",
    "                if self.total_gScore(current, neighbor) < self.gScore[neighbor]:\n",
    "                    # Record the path if it's the best until now\n",
    "                    self.record_best_path_to(current, neighbor)\n",
    "\n",
    "        print(\"No routing path found\")\n",
    "        self.path = None\n",
    "        return None\n",
    "\n",
    "    def get_current_node(self):\n",
    "        # Returns the node in the open set with the lowest value of f(node)\n",
    "        node_f_scores = {node: self.total_fScore(node) for node in self.openSet}\n",
    "        return min(node_f_scores, key=node_f_scores.get)\n",
    "\n",
    "    def distance(self, node_1, node_2):\n",
    "        # Compute and return the distance between two points\n",
    "        (x1, y1), (x2, y2) = self.map.convergence[node_1], self.map.convergence[node_2]\n",
    "        return math.sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2))\n",
    "\n",
    "    def total_gScore(self, current, neighbor):\n",
    "        # Return the G score of the current node \n",
    "        # Plus distance from the current node to it's neighbors\n",
    "        return self.gScore[current] + self.distance(current, neighbor)\n",
    "\n",
    "    def total_hScore(self, node):\n",
    "        # Returns the heuristic cost estimate of a node\n",
    "        return self.distance(node, self.goal)\n",
    "\n",
    "    def total_fScore(self, node):\n",
    "        # F = G + H\n",
    "        return self.gScore[node] + self.total_hScore(node)\n",
    "\n",
    "\n",
    "    def record_best_path_to(self, current, neighbor):\n",
    "        # Record the best path to a node, by updating cameFrom, gScore, and fScore\n",
    "        self.cameFrom[neighbor] = current\n",
    "        self.gScore[neighbor] = self.total_gScore(current, neighbor)\n",
    "        self.fScore[current] = self.total_fScore(current)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d359fefc-8cd0-4314-809b-3ccdfb1d28d0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path:  [0, 3, 5, 9, 11, 14]\n"
     ]
    },
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "config": {
        "linkText": "Export to plot.ly",
        "plotlyServerURL": "https://plot.ly",
        "showLink": false
       },
       "data": [
        {
         "line": {
          "color": "#888",
          "width": 2
         },
         "type": "scatter",
         "x": [
          0,
          0.1,
          null,
          0,
          0.1,
          null,
          0,
          0.1,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.1,
          0.2,
          null,
          0.2,
          0.3,
          null,
          0.2,
          0.3,
          null,
          0.2,
          0.3,
          null,
          0.2,
          0.4,
          null,
          0.2,
          0.3,
          null,
          0.3,
          0.4,
          null,
          0.3,
          0.5,
          null,
          0.3,
          0.4,
          null,
          0.3,
          0.5,
          null,
          0.4,
          0.5,
          null,
          0.4,
          0.5,
          null,
          0.4,
          0.5,
          null,
          0.5,
          0.6,
          null,
          0.5,
          0.6,
          null,
          0.5,
          0.9,
          null,
          0.5,
          0.9,
          null
         ],
         "y": [
          0.5,
          0.7,
          null,
          0.5,
          0.6,
          null,
          0.5,
          0.4,
          null,
          0.7,
          0.6,
          null,
          0.7,
          0.4,
          null,
          0.7,
          0.9,
          null,
          0.6,
          0.6,
          null,
          0.6,
          0.4,
          null,
          0.6,
          0.9,
          null,
          0.4,
          0.6,
          null,
          0.4,
          0.4,
          null,
          0.4,
          0.9,
          null,
          0.6,
          0.7,
          null,
          0.4,
          0.7,
          null,
          0.4,
          0.3,
          null,
          0.4,
          0.5,
          null,
          0.9,
          0.3,
          null,
          0.7,
          0.5,
          null,
          0.7,
          0.6,
          null,
          0.3,
          0.5,
          null,
          0.3,
          0.2,
          null,
          0.5,
          0.6,
          null,
          0.5,
          0.5,
          null,
          0.5,
          0.2,
          null,
          0.6,
          0.7,
          null,
          0.5,
          0.7,
          null,
          0.5,
          0.4,
          null,
          0.2,
          0.4,
          null
         ]
        },
        {
         "hoverinfo": "x+y+text",
         "marker": {
          "color": [
           3,
           0,
           0,
           2,
           0,
           2,
           0,
           0,
           0,
           2,
           0,
           2,
           0,
           0,
           1
          ],
          "colorscale": [
           [
            0,
            "rgb(0,0,0)"
           ],
           [
            0.3333333333333333,
            "rgb(230,0,0)"
           ],
           [
            0.6666666666666666,
            "rgb(255,210,0)"
           ],
           [
            1,
            "rgb(255,255,255)"
           ]
          ],
          "line": {
           "width": 4
          },
          "reversescale": true,
          "showscale": true,
          "size": 20
         },
         "mode": "markers",
         "text": [
          "Router 0",
          "Router 1",
          "Router 2",
          "Router 3",
          "Router 4",
          "Router 5",
          "Router 6",
          "Router 7",
          "Router 8",
          "Router 9",
          "Router 10",
          "Router 11",
          "Router 12",
          "Router 13",
          "Router 14"
         ],
         "type": "scatter",
         "x": [
          0,
          0.1,
          0.1,
          0.1,
          0.2,
          0.2,
          0.2,
          0.3,
          0.3,
          0.4,
          0.5,
          0.5,
          0.5,
          0.6,
          0.9
         ],
         "y": [
          0.5,
          0.7,
          0.6,
          0.4,
          0.6,
          0.4,
          0.9,
          0.7,
          0.3,
          0.5,
          0.6,
          0.5,
          0.2,
          0.7,
          0.4
         ]
        }
       ],
       "layout": {
        "hovermode": "closest",
        "margin": {
         "b": 25,
         "l": 7,
         "r": 7,
         "t": 35
        },
        "showlegend": false,
        "template": {
         "data": {
          "bar": [
           {
            "error_x": {
             "color": "#2a3f5f"
            },
            "error_y": {
             "color": "#2a3f5f"
            },
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "bar"
           }
          ],
          "barpolar": [
           {
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "barpolar"
           }
          ],
          "carpet": [
           {
            "aaxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "baxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "type": "carpet"
           }
          ],
          "choropleth": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "choropleth"
           }
          ],
          "contour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "contour"
           }
          ],
          "contourcarpet": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "contourcarpet"
           }
          ],
          "heatmap": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmap"
           }
          ],
          "heatmapgl": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmapgl"
           }
          ],
          "histogram": [
           {
            "marker": {
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "histogram"
           }
          ],
          "histogram2d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2d"
           }
          ],
          "histogram2dcontour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2dcontour"
           }
          ],
          "mesh3d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "mesh3d"
           }
          ],
          "parcoords": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "parcoords"
           }
          ],
          "pie": [
           {
            "automargin": true,
            "type": "pie"
           }
          ],
          "scatter": [
           {
            "fillpattern": {
             "fillmode": "overlay",
             "size": 10,
             "solidity": 0.2
            },
            "type": "scatter"
           }
          ],
          "scatter3d": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatter3d"
           }
          ],
          "scattercarpet": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattercarpet"
           }
          ],
          "scattergeo": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergeo"
           }
          ],
          "scattergl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergl"
           }
          ],
          "scattermapbox": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattermapbox"
           }
          ],
          "scatterpolar": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolar"
           }
          ],
          "scatterpolargl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolargl"
           }
          ],
          "scatterternary": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterternary"
           }
          ],
          "surface": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "surface"
           }
          ],
          "table": [
           {
            "cells": {
             "fill": {
              "color": "#EBF0F8"
             },
             "line": {
              "color": "white"
             }
            },
            "header": {
             "fill": {
              "color": "#C8D4E3"
             },
             "line": {
              "color": "white"
             }
            },
            "type": "table"
           }
          ]
         },
         "layout": {
          "annotationdefaults": {
           "arrowcolor": "#2a3f5f",
           "arrowhead": 0,
           "arrowwidth": 1
          },
          "autotypenumbers": "strict",
          "coloraxis": {
           "colorbar": {
            "outlinewidth": 0,
            "ticks": ""
           }
          },
          "colorscale": {
           "diverging": [
            [
             0,
             "#8e0152"
            ],
            [
             0.1,
             "#c51b7d"
            ],
            [
             0.2,
             "#de77ae"
            ],
            [
             0.3,
             "#f1b6da"
            ],
            [
             0.4,
             "#fde0ef"
            ],
            [
             0.5,
             "#f7f7f7"
            ],
            [
             0.6,
             "#e6f5d0"
            ],
            [
             0.7,
             "#b8e186"
            ],
            [
             0.8,
             "#7fbc41"
            ],
            [
             0.9,
             "#4d9221"
            ],
            [
             1,
             "#276419"
            ]
           ],
           "sequential": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ],
           "sequentialminus": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ]
          },
          "colorway": [
           "#636efa",
           "#EF553B",
           "#00cc96",
           "#ab63fa",
           "#FFA15A",
           "#19d3f3",
           "#FF6692",
           "#B6E880",
           "#FF97FF",
           "#FECB52"
          ],
          "font": {
           "color": "#2a3f5f"
          },
          "geo": {
           "bgcolor": "white",
           "lakecolor": "white",
           "landcolor": "#E5ECF6",
           "showlakes": true,
           "showland": true,
           "subunitcolor": "white"
          },
          "hoverlabel": {
           "align": "left"
          },
          "hovermode": "closest",
          "mapbox": {
           "style": "light"
          },
          "paper_bgcolor": "white",
          "plot_bgcolor": "#E5ECF6",
          "polar": {
           "angularaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "radialaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "scene": {
           "xaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "yaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "zaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           }
          },
          "shapedefaults": {
           "line": {
            "color": "#2a3f5f"
           }
          },
          "ternary": {
           "aaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "baxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "caxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "title": {
           "x": 0.05
          },
          "xaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          },
          "yaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          }
         }
        },
        "title": {
         "font": {
          "size": 20
         },
         "text": "Network Topology using A* search for fast Packet Routing"
        }
       }
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "start = 0\n",
    "goal = 14\n",
    "test_path = PacketPlanner(load_map(map_15_dict), start, goal).path\n",
    "print(\"Path: \", test_path)\n",
    "show_map(load_map(map_15_dict), start, goal, test_path)\n",
    "\n",
    "# start = 0\n",
    "# goal = 13\n",
    "# test_path = PacketPlanner(load_map(map_15_dict), start, goal).path\n",
    "# print(\"Path: \", test_path)\n",
    "# show_map(load_map(map_15_dict), start, goal, test_path)"
   ]
  }
 ],
 "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.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}