scgraph.core

   1from .utils import haversine, distance_converter, get_line_path, cheap_ruler
   2import json
   3from heapq import heappop, heappush
   4
   5
   6class Graph:
   7    @staticmethod
   8    def validate_graph(
   9        graph: list[dict[int, int | float]],
  10        check_symmetry: bool = True,
  11        check_connected: bool = True,
  12    ) -> None:
  13        """
  14        Function:
  15
  16        - Validate that a graph is properly formatted
  17
  18        Required Arguments:
  19
  20        - `graph`:
  21            - Type: list of dictionaries with integer keys and integer or float values
  22            - What: A list of dictionaries where the indicies are origin node ids and the values are dictionaries of destination node indices and graph weights
  23            - Note: All nodes must be included as origins in the graph regardless of if they have any connected destinations
  24            - EG:
  25            ```
  26                [
  27                    # From London (index 0)
  28                    {
  29                        # To Paris (index 1)
  30                        1: 311,
  31                    },
  32                    # From Paris (index 1)
  33                    {
  34                        # To London (index 0)
  35                        0: 311,
  36                        # To Berlin (index 2)
  37                        2: 878,
  38                        # To Rome (index 3)
  39                        3: 1439,
  40                        # To Madrid (index 4)
  41                        4: 1053
  42                    },
  43                    # From Berlin (index 2)
  44                    {
  45                        # To Paris (index 1)
  46                        1: 878,
  47                        # To Rome (index 3)
  48                        3: 1181,
  49                    },
  50                    # From Rome (index 3)
  51                    {
  52                        # To Paris (index 1)
  53                        1: 1439,
  54                        # To Berlin (index 2)
  55                        2: 1181,
  56                    },
  57                    # From Madrid (index 4)
  58                    {
  59                        # To Paris (index 1)
  60                        1: 1053,
  61                        # To Lisbon (index 5)
  62                        5: 623
  63                    },
  64                    # From Lisbon (index 5)
  65                    {
  66                        # To Madrid (index 4)
  67                        4: 623
  68                    }
  69                ]
  70            ```
  71
  72        Optional Arguments:
  73
  74        - `check_symmetry`
  75            - Type: bool
  76            - What: Whether to check that the graph is symmetric
  77            - Default: True
  78            - Note: This is forced to True if `check_connected` is True
  79        - `check_connected`
  80            - Type: bool
  81            - What: Whether to check that the graph is fully connected
  82            - Default: True
  83            - Note: For computational efficiency, only symmetric graphs are checked for connectivity
  84            - Note: If this is True, `check_symmetry` is forced to True and the graph will be checked for symmetry prior to checking for connectivity
  85        """
  86        check_symmetry = check_symmetry or check_connected
  87        assert isinstance(graph, list), "Your graph must be a list"
  88        len_graph = len(graph)
  89        for origin_id, origin_dict in enumerate(graph):
  90            assert isinstance(
  91                origin_dict, dict
  92            ), f"Your graph must be a list of dictionaries but the value for origin {origin_id} is not a dictionary"
  93            destinations = list(origin_dict.keys())
  94            lengths = list(origin_dict.values())
  95            assert all(
  96                [
  97                    (isinstance(i, int) and i >= 0 and i < len_graph)
  98                    for i in destinations
  99                ]
 100            ), f"Destination ids must be non-negative integers and equivalent to an existing index, but graph[{origin_id}] has an error in the destination ids"
 101            assert all(
 102                [(isinstance(i, (int, float)) and i >= 0) for i in lengths]
 103            ), f"Distances must be integers or floats, but graph[{origin_id}] contains a non-integer or non-float distance"
 104            if check_symmetry:
 105                for destination_id, distance in origin_dict.items():
 106                    assert (
 107                        graph[destination_id].get(origin_id) == distance
 108                    ), f"Your graph is not symmetric, the distance from node {origin_id} to node {destination_id} is {distance} but the distance from node {destination_id} to node {origin_id} is {graph.get(destination_id, {}).get(origin_id)}"
 109        if check_connected:
 110            assert Graph.validate_connected(
 111                graph
 112            ), "Your graph is not fully connected"
 113
 114    @staticmethod
 115    def validate_connected(
 116        graph: list[dict[int, int | float]], origin_id: int = 0
 117    ) -> bool:
 118        """
 119        Function:
 120
 121        - Validate that a graph is fully connected
 122            - This means that every node in the graph has a path to every other node in the graph
 123            - Note: This assumes that the graph is symmetric
 124        - Return True if the graph is fully connected and False if it is not
 125
 126        Required Arguments:
 127
 128        - `graph`:
 129            - Type: list of dictionaries
 130            - See: https://connor-makowski.github.io/scgraph/scgraph/core.html#Graph.validate_graph
 131
 132        Optional Arguments:
 133
 134        - `origin_id`
 135            - Type: int
 136            - What: The id of the origin node from which to start the connectivity check
 137            - Default: 0
 138        """
 139        visited = [0] * len(graph)
 140        open_leaves = [origin_id]
 141
 142        while open_leaves:
 143            current_id = open_leaves.pop()
 144            visited[current_id] = 1
 145            for connected_id, connected_distance in graph[current_id].items():
 146                if visited[connected_id] == 0:
 147                    open_leaves.append(connected_id)
 148        return min(visited) == 1
 149
 150    @staticmethod
 151    def input_check(
 152        graph: list[dict[int, int | float]], origin_id: int, destination_id: int
 153    ) -> None:
 154        """
 155        Function:
 156
 157        - Check that the inputs passed to the shortest path algorithm are valid
 158        - Raises an exception if the inputs passed are not valid
 159
 160        Required Arguments:
 161
 162        - `graph`:
 163            - Type: list of dictionaries
 164            - See: https://connor-makowski.github.io/scgraph/scgraph/core.html#Graph.validate_graph
 165        - `origin_id`
 166            - Type: int
 167            - What: The id of the origin node from the graph dictionary to start the shortest path from
 168        - `destination_id`
 169            - Type: int
 170            - What: The id of the destination node from the graph dictionary to end the shortest path at
 171
 172        Optional Arguments:
 173
 174        - None
 175        """
 176        if (
 177            not isinstance(origin_id, int)
 178            and origin_id < len(graph)
 179            and origin_id >= 0
 180        ):
 181            raise Exception(f"Origin node ({origin_id}) is not in the graph")
 182        if (
 183            not isinstance(destination_id, int)
 184            and origin_id < len(graph)
 185            and origin_id >= 0
 186        ):
 187            raise Exception(
 188                f"Destination node ({destination_id}) is not in the graph"
 189            )
 190
 191    @staticmethod
 192    def dijkstra(
 193        graph: list[dict[int, int | float]], origin_id: int, destination_id: int
 194    ) -> dict:
 195        """
 196        Function:
 197
 198        - Identify the shortest path between two nodes in a sparse network graph using a modified dijkstra algorithm
 199            - Modifications allow for a sparse distance matrix to be used instead of a dense distance matrix
 200            - This can dramatically reduce the memory and compute requirements of the algorithm
 201            - This algorithm runs in O(n^2) time where n is the number of nodes in the graph
 202        - Return a dictionary of various path information including:
 203            - `id_path`: A list of node ids in the order they are visited
 204            - `path`: A list of node dictionaries (lat + long) in the order they are visited
 205
 206        Required Arguments:
 207
 208        - `graph`:
 209            - Type: list of dictionaries
 210            - See: https://connor-makowski.github.io/scgraph/scgraph/core.html#Graph.validate_graph
 211        - `origin_id`
 212            - Type: int
 213            - What: The id of the origin node from the graph dictionary to start the shortest path from
 214        - `destination_id`
 215            - Type: int
 216            - What: The id of the destination node from the graph dictionary to end the shortest path at
 217
 218        Optional Arguments:
 219
 220        - None
 221        """
 222        Graph.input_check(
 223            graph=graph, origin_id=origin_id, destination_id=destination_id
 224        )
 225        distance_matrix = [float("inf")] * len(graph)
 226        branch_tip_distances = [float("inf")] * len(graph)
 227        predecessor = [-1] * len(graph)
 228
 229        distance_matrix[origin_id] = 0
 230        branch_tip_distances[origin_id] = 0
 231
 232        while True:
 233            current_distance = min(branch_tip_distances)
 234            if current_distance == float("inf"):
 235                raise Exception(
 236                    "Something went wrong, the origin and destination nodes are not connected."
 237                )
 238            current_id = branch_tip_distances.index(current_distance)
 239            branch_tip_distances[current_id] = float("inf")
 240            if current_id == destination_id:
 241                break
 242            for connected_id, connected_distance in graph[current_id].items():
 243                possible_distance = current_distance + connected_distance
 244                if possible_distance < distance_matrix[connected_id]:
 245                    distance_matrix[connected_id] = possible_distance
 246                    predecessor[connected_id] = current_id
 247                    branch_tip_distances[connected_id] = possible_distance
 248
 249        output_path = [current_id]
 250        while predecessor[current_id] != -1:
 251            current_id = predecessor[current_id]
 252            output_path.append(current_id)
 253
 254        output_path.reverse()
 255
 256        return {
 257            "path": output_path,
 258            "length": distance_matrix[destination_id],
 259        }
 260
 261    @staticmethod
 262    def dijkstra_makowski(
 263        graph: list[dict[int, int | float]], origin_id: int, destination_id: int
 264    ) -> dict:
 265        """
 266        Function:
 267
 268        - Identify the shortest path between two nodes in a sparse network graph using Makowski's modified Dijkstra algorithm
 269            - Modifications allow for a sparse distance matrix to be used instead of a dense distance matrix
 270            - Improvements include only computing future potential nodes based on the open leaves for each branch
 271                - Open leaves are nodes that have not been visited yet but are adjacent to other visited nodes
 272            - This can dramatically reduce the memory and compute requirements of the algorithm
 273            - For particularly sparse graphs, this algorithm runs close to O(n log n) time
 274                - Where n is the number of nodes in the graph
 275            - For dense graphs, this algorithm runs closer to O(n^2) time (similar to the standard Dijkstra algorithm)
 276                - Where n is the number of nodes in the graph
 277        - Return a dictionary of various path information including:
 278            - `id_path`: A list of node ids in the order they are visited
 279            - `path`: A list of node dictionaries (lat + long) in the order they are visited
 280
 281        Required Arguments:
 282
 283        - `graph`:
 284            - Type: list of dictionaries
 285            - See: https://connor-makowski.github.io/scgraph/scgraph/core.html#Graph.validate_graph
 286        - `origin_id`
 287            - Type: int
 288            - What: The id of the origin node from the graph dictionary to start the shortest path from
 289        - `destination_id`
 290            - Type: int
 291            - What: The id of the destination node from the graph dictionary to end the shortest path at
 292
 293        Optional Arguments:
 294
 295        - None
 296        """
 297        # Input Validation
 298        Graph.input_check(
 299            graph=graph, origin_id=origin_id, destination_id=destination_id
 300        )
 301        # Variable Initialization
 302        distance_matrix = [float("inf")] * len(graph)
 303        distance_matrix[origin_id] = 0
 304        open_leaves = []
 305        heappush(open_leaves, (0, origin_id))
 306        predecessor = [-1] * len(graph)
 307
 308        while open_leaves:
 309            current_distance, current_id = heappop(open_leaves)
 310            if current_id == destination_id:
 311                break
 312            for connected_id, connected_distance in graph[current_id].items():
 313                possible_distance = current_distance + connected_distance
 314                if possible_distance < distance_matrix[connected_id]:
 315                    distance_matrix[connected_id] = possible_distance
 316                    predecessor[connected_id] = current_id
 317                    heappush(open_leaves, (possible_distance, connected_id))
 318        if current_id != destination_id:
 319            raise Exception(
 320                "Something went wrong, the origin and destination nodes are not connected."
 321            )
 322
 323        output_path = [current_id]
 324        while predecessor[current_id] != -1:
 325            current_id = predecessor[current_id]
 326            output_path.append(current_id)
 327
 328        output_path.reverse()
 329
 330        return {
 331            "path": output_path,
 332            "length": distance_matrix[destination_id],
 333        }
 334
 335    @staticmethod
 336    def a_star(
 337        graph: list[dict[int, int | float]],
 338        origin_id: int,
 339        destination_id: int,
 340        heuristic_fn=None,
 341    ) -> dict:
 342        """
 343        Function:
 344
 345        - Identify the shortest path between two nodes in a sparse network graph using an A* extension of Makowski's modified Dijkstra algorithm
 346        - Return a dictionary of various path information including:
 347            - `id_path`: A list of node ids in the order they are visited
 348            - `path`: A list of node dictionaries (lat + long) in the order they are visited
 349
 350        Required Arguments:
 351
 352        - `graph`:
 353            - Type: list of dictionaries
 354            - See: https://connor-makowski.github.io/scgraph/scgraph/core.html#Graph.validate_graph
 355        - `origin_id`
 356            - Type: int
 357            - What: The id of the origin node from the graph dictionary to start the shortest path from
 358        - `destination_id`
 359            - Type: int
 360            - What: The id of the destination node from the graph dictionary to end the shortest path at
 361        - `heuristic_fn`
 362            - Type: function
 363            - What: A heuristic function that takes two node ids and returns an estimated distance between them
 364            - Note: If None, returns the shortest path using Makowski's modified Dijkstra algorithm
 365            - Default: None
 366
 367        Optional Arguments:
 368
 369        - None
 370        """
 371        if heuristic_fn is None:
 372            return Graph.dijkstra_makowski(
 373                graph=graph,
 374                origin_id=origin_id,
 375                destination_id=destination_id,
 376            )
 377        # Input Validation
 378        Graph.input_check(
 379            graph=graph, origin_id=origin_id, destination_id=destination_id
 380        )
 381        # Variable Initialization
 382        distance_matrix = [float("inf")] * len(graph)
 383        distance_matrix[origin_id] = 0
 384        open_leaves = []
 385        heappush(open_leaves, (0, origin_id))
 386        predecessor = [-1] * len(graph)
 387
 388        while open_leaves:
 389            current_id = heappop(open_leaves)[1]
 390            if current_id == destination_id:
 391                break
 392            current_distance = distance_matrix[current_id]
 393            for connected_id, connected_distance in graph[current_id].items():
 394                possible_distance = current_distance + connected_distance
 395                if possible_distance < distance_matrix[connected_id]:
 396                    distance_matrix[connected_id] = possible_distance
 397                    predecessor[connected_id] = current_id
 398                    heappush(
 399                        open_leaves,
 400                        (
 401                            possible_distance
 402                            + heuristic_fn(connected_id, destination_id),
 403                            connected_id,
 404                        ),
 405                    )
 406        if current_id != destination_id:
 407            raise Exception(
 408                "Something went wrong, the origin and destination nodes are not connected."
 409            )
 410
 411        output_path = [current_id]
 412        while predecessor[current_id] != -1:
 413            current_id = predecessor[current_id]
 414            output_path.append(current_id)
 415
 416        output_path.reverse()
 417
 418        return {
 419            "path": output_path,
 420            "length": distance_matrix[destination_id],
 421        }
 422
 423
 424class GeoGraph:
 425    def __init__(
 426        self,
 427        graph: list[dict[int, int | float]],
 428        nodes: list[list[float | int]],
 429    ) -> None:
 430        """
 431        Function:
 432
 433        - Create a GeoGraph object
 434
 435        Required Arguments:
 436
 437        - `graph`
 438            - Type: list of dictionaries
 439            - See: https://connor-makowski.github.io/scgraph/scgraph/core.html#Graph.validate_graph
 440        - `nodes`
 441            - Type: list of lists of ints or floats
 442            - What: A list of lists where the values are coordinates (latitude then longitude)
 443            - Note: The length of the nodes list must be the same as that of the graph list
 444            - EG Continuing off the example from https://connor-makowski.github.io/scgraph/scgraph/core.html#Graph.validate_graph
 445            ```
 446                [
 447                    # London (index 0)
 448                    [51.5074, 0.1278],
 449                    # Paris (index 1)
 450                    [48.8566, 2.3522],
 451                    # Berlin (index 2)
 452                    [52.5200, 13.4050],
 453                    # Rome (index 3)
 454                    [41.9028, 12.4964],
 455                    # Madrid (index 4)
 456                    [40.4168, 3.7038],
 457                    # Lisbon (index 5)
 458                    [38.7223, 9.1393]
 459                ]
 460            ```
 461        """
 462        self.graph = graph
 463        self.nodes = nodes
 464
 465    def validate_graph(
 466        self, check_symmetry: bool = True, check_connected: bool = True
 467    ) -> None:
 468        """
 469        Function:
 470
 471        - Validate that self.graph is properly formatted (see Graph.validate_graph)
 472        - Raises an exception if the graph is invalid
 473        - Returns None if the graph is valid
 474
 475        Required Arguments:
 476
 477        - None
 478
 479        Optional Arguments:
 480
 481        - `check_symmetry`
 482            - Type: bool
 483            - What: Whether to check that the graph is symmetric
 484            - Default: True
 485            - Note: This is forced to True if `check_connected` is True
 486        - `check_connected`
 487            - Type: bool
 488            - What: Whether to check that the graph is fully connected
 489            - Default: True
 490            - Note: For computational efficiency, graphs are validated for symmetry prior to checking for connectivity
 491        """
 492        Graph.validate_graph(
 493            self.graph,
 494            check_symmetry=check_symmetry,
 495            check_connected=check_connected,
 496        )
 497
 498    def validate_nodes(self) -> None:
 499        """
 500
 501        Function:
 502
 503        - Validate that self.nodes is properly formatted (see GeoGraph.__init__ docs for more details)
 504        - Raises an exception if the nodes are invalid
 505        - Returns None if the nodes are valid
 506
 507        Required Arguments:
 508
 509        - None
 510
 511        Optional Arguments:
 512
 513        - None
 514        """
 515        assert isinstance(self.nodes, list), "Your nodes must be a dictionary"
 516        assert all(
 517            [isinstance(i, list) for i in self.nodes]
 518        ), "Your nodes must be a list of lists"
 519        assert all(
 520            [len(i) == 2 for i in self.nodes]
 521        ), "Your nodes must be a list of lists where each sub list has a length of 2"
 522        assert all(
 523            [
 524                (
 525                    isinstance(i[0], (int, float))
 526                    and isinstance(i[1], (int, float))
 527                )
 528                for i in self.nodes
 529            ]
 530        ), "Your nodes must be a list of lists where each sub list has a numeric latitude and longitude value"
 531        assert all(
 532            [
 533                (i[0] >= -90 and i[0] <= 90 and i[1] >= -180 and i[1] <= 180)
 534                for i in self.nodes
 535            ]
 536        ), "Your nodes must be a list of lists where each sub list has a length of 2 with a latitude [-90,90] and longitude [-180,180] value"
 537
 538    def haversine(
 539        self,
 540        origin_id: int,
 541        destination_id: int,
 542    ):
 543        return haversine(
 544            origin=self.nodes[origin_id],
 545            destination=self.nodes[destination_id],
 546            units="km",
 547            circuity=1,
 548        )
 549
 550    def cheap_ruler(
 551        self,
 552        origin_id: int,
 553        destination_id: int,
 554    ):
 555        return cheap_ruler(
 556            origin=self.nodes[origin_id],
 557            destination=self.nodes[destination_id],
 558            units="km",
 559            # Use a circuity factor of 0.95 to account for the fact that cheap_ruler can overestimate distances
 560            circuity=0.9,
 561        )
 562
 563    def get_shortest_path(
 564        self,
 565        origin_node: dict[float | int],
 566        destination_node: dict[float | int],
 567        output_units: str = "km",
 568        algorithm_fn=Graph.dijkstra_makowski,
 569        algorithm_kwargs: dict = dict(),
 570        off_graph_circuity: [float | int] = 1,
 571        node_addition_type: str = "quadrant",
 572        node_addition_circuity: [float | int] = 4,
 573        geograph_units: str = "km",
 574        output_coordinate_path: str = "list_of_lists",
 575        output_path: bool = False,
 576        node_addition_lat_lon_bound: [float | int] = 5,
 577        node_addition_math: str = "euclidean",
 578        **kwargs,
 579    ) -> dict:
 580        """
 581        Function:
 582
 583        - Identify the shortest path between two nodes in a sparse network graph
 584
 585        - Return a dictionary of various path information including:
 586            - `id_path`: A list of node ids in the order they are visited
 587            - `path`: A list of nodes  (list of lat then long) in the order they are visited
 588            - `length`: The length of the path
 589
 590         Required Arguments:
 591
 592        - `origin_node`
 593            - Type: dict of int | float
 594            - What: A dictionary with the keys 'latitude' and 'longitude'
 595        - `destination_node`
 596            - Type: dict of int | float
 597            - What: A dictionary with the keys 'latitude' and 'longitude'
 598
 599        Optional Arguments:
 600
 601        - `output_units`
 602            - Type: str
 603            - What: The units in which to return the length of the path
 604            - Default: 'km'
 605            - Options:
 606                - 'km': Kilometers
 607                - 'm': Meters
 608                - 'mi': Miles
 609                - 'ft': Feet
 610        - `algorithm_fn`
 611            - Type: function | method
 612            - What: The algorithm function to identify the shortest path
 613            - Default: 'Graph.dijkstra_makowski'
 614            - Options:
 615                - 'Graph.dijkstra': A modified dijkstra algorithm that uses a sparse distance matrix to identify the shortest path
 616                - 'Graph.dijkstra_makowski': A modified dijkstra algorithm that uses a sparse distance matrix to identify the shortest path
 617                - Any user defined algorithm that takes the arguments:
 618                    - `graph`: A dictionary of dictionaries where the keys are origin node ids and the values are dictionaries of destination node ids and distances
 619                        - See: https://connor-makowski.github.io/scgraph/scgraph/core.html#Graph.validate_graph
 620                    - `origin`: The id of the origin node from the graph dictionary to start the shortest path from
 621                    - `destination`: The id of the destination node from the graph dictionary to end the shortest path at
 622        - `algorithm_kwargs`
 623            - Type: dict
 624            - What: Additional keyword arguments to pass to the algorithm function assuming it accepts them
 625        - `off_graph_circuity`
 626            - Type: int | float
 627            - What: The circuity factor to apply to any distance calculations between your origin and destination nodes and their connecting nodes in the graph
 628            - Default: 1
 629            - Notes:
 630                - For alogrithmic solving purposes, the node_addition_circuity is applied to the origin and destination nodes when they are added to the graph
 631                - This is only applied after an `optimal solution` using the `node_addition_circuity` has been found when it is then adjusted to equal the `off_graph_circuity`
 632        - `node_addition_type`
 633            - Type: str
 634            - What: The type of node addition to use when adding your origin node to the distance matrix
 635            - Default: 'quadrant'
 636            - Options:
 637                - 'quadrant': Add the closest node in each quadrant (ne, nw, se, sw) to the distance matrix for this node
 638                - 'closest': Add only the closest node to the distance matrix for this node
 639                - 'all': Add all nodes to the distance matrix for this node
 640            - Notes:
 641                - `dijkstra_makowski` will operate substantially faster if the `node_addition_type` is set to 'quadrant' or 'closest'
 642                - `dijkstra` will operate at the similar speeds regardless of the `node_addition_type`
 643                - When using `all`, you should consider using `dijkstra` instead of `dijkstra_makowski` as it will be faster
 644                - The destination node is always added as 'all' regardless of the `node_addition_type` setting
 645                    - This guarantees that any destination node will be connected to any origin node regardless of how or where the origin node is added to the graph
 646                - If the passed graph is not a connected graph (meaning it is comprised of multiple disconnected networks)
 647                    - The entrypoints generated using the `node_addition_type` will determine which disconnected networks will be used to calculate the `optimal route`
 648        - `node_addition_circuity`
 649            - Type: int | float
 650            - What: The circuity factor to apply when adding your origin and destination nodes to the distance matrix
 651            - Default: 4
 652            - Note:
 653                - This defaults to 4 to prevent the algorithm from taking a direct route in direction of the destination over some impassible terrain (EG: a maritime network that goes through land)
 654                - A higher value will push the algorithm to join the network at a closer node to avoid the extra distance from the circuity factor
 655                - This is only relevant if `node_addition_type` is set to 'quadrant' or 'all' as it affects the choice on where to enter the graph network
 656                - This factor is used to calculate the node sequence for the `optimal route`, however the reported `length` of the path will be calculated using the `off_graph_circuity` factor
 657        - `geograph_units`
 658            - Type: str
 659            - What: The units of measurement in the geograph data
 660            - Default: 'km'
 661            - Options:
 662                - 'km': Kilometers
 663                - 'm': Meters
 664                - 'mi': Miles
 665                - 'ft': Feet
 666            - Note: In general, all scgraph provided geographs be in kilometers
 667        - `output_coordinate_path`
 668            - Type: str
 669            - What: The format of the output coordinate path
 670            - Default: 'list_of_lists'
 671            - Options:
 672                - 'list_of_dicts': A list of dictionaries with keys 'latitude' and 'longitude'
 673                - 'list_of_lists': A list of lists with the first value being latitude and the second being longitude
 674                - 'list_of_lists_long_first': A list of lists with the first value being longitude and the second being latitude
 675        - `output_path`
 676            - Type: bool
 677            - What: Whether to output the path as a list of geograph node ids (for debugging and other advanced uses)
 678            - Default: False
 679        - `node_addition_lat_lon_bound`
 680            - Type: int | float
 681            - What: Forms a bounding box around the origin and destination nodes as they are added to graph
 682                - Only points on the current graph inside of this bounding box are considered when updating the distance matrix for the origin or destination nodes
 683            - Default: 5
 684            - Note: If no nodes are found within the bounding box, the bounding box is expanded to 180 degrees in all directions (all nodes are considered)
 685            - Note: This is only used when adding a new node (the specified origin and destination) to the graph
 686        - `node_addition_math`
 687            - Type: str
 688            - What: The math to use when calculating the distance between nodes when determining the closest node (or closest quadrant node) to add to the graph
 689            - Default: 'euclidean'
 690            - Options:
 691                - 'euclidean': Use the euclidean distance between nodes. This is much faster but is not as accurate (especially near the poles)
 692                - 'haversine': Use the haversine distance between nodes. This is slower but is an accurate representation of the surface distance between two points on the earth
 693            - Notes:
 694                - Only used if `node_addition_type` is set to 'quadrant' or 'closest'
 695        - `**kwargs`
 696            - Additional keyword arguments. These are included for forwards and backwards compatibility reasons, but are not currently used.
 697        """
 698        original_graph_length = len(self.graph)
 699        # Add the origin and destination nodes to the graph
 700        origin_id = self.add_node(
 701            node=origin_node,
 702            node_addition_type=node_addition_type,
 703            circuity=node_addition_circuity,
 704            lat_lon_bound=node_addition_lat_lon_bound,
 705            node_addition_math=node_addition_math,
 706        )
 707        destination_id = self.add_node(
 708            node=destination_node,
 709            node_addition_type="all",
 710            circuity=node_addition_circuity,
 711            lat_lon_bound=node_addition_lat_lon_bound,
 712            node_addition_math=node_addition_math,
 713        )
 714        try:
 715            output = algorithm_fn(
 716                graph=self.graph,
 717                origin_id=origin_id,
 718                destination_id=destination_id,
 719                **algorithm_kwargs,
 720            )
 721            output["coordinate_path"] = self.get_coordinate_path(output["path"])
 722            output["length"] = self.adujust_circuity_length(
 723                output=output,
 724                node_addition_circuity=node_addition_circuity,
 725                off_graph_circuity=off_graph_circuity,
 726            )
 727            output["length"] = distance_converter(
 728                output["length"],
 729                input_units=geograph_units,
 730                output_units=output_units,
 731            )
 732            if output_coordinate_path == "list_of_dicts":
 733                output["coordinate_path"] = [
 734                    {"latitude": i[0], "longitude": i[1]}
 735                    for i in output["coordinate_path"]
 736                ]
 737            elif output_coordinate_path == "list_of_lists_long_first":
 738                output["coordinate_path"] = [
 739                    [i[1], i[0]] for i in output["coordinate_path"]
 740                ]
 741                output["long_first"] = True
 742            if not output_path:
 743                del output["path"]
 744            while len(self.graph) > original_graph_length:
 745                self.remove_appended_node()
 746            return output
 747        except Exception as e:
 748            while len(self.graph) > original_graph_length:
 749                self.remove_appended_node()
 750            raise e
 751
 752    def adujust_circuity_length(
 753        self,
 754        output: dict,
 755        node_addition_circuity: [float | int],
 756        off_graph_circuity: [float | int],
 757    ) -> [float | int]:
 758        """
 759        Function:
 760
 761        - Adjust the length of the path to account for the circuity factors applied to the origin and destination nodes
 762
 763        Required Arguments:
 764
 765        - `output`
 766            - Type: dict
 767            - What: The output from the algorithm function
 768        - `node_addition_circuity`
 769            - Type: int | float
 770            - What: The circuity factor that was applied when adding your origin and destination nodes to the distance matrix
 771        - `off_graph_circuity`
 772            - Type: int | float
 773            - What: The circuity factor to apply to any distance calculations between your origin and destination nodes and their connecting nodes in the graph
 774        """
 775        coordinate_path = output["coordinate_path"]
 776        # If the path does not enter the graph, undo the node_addition_circuity and apply the off_graph_circuity
 777        if len(output["coordinate_path"]) == 2:
 778            return (
 779                output["length"] / node_addition_circuity
 780            ) * off_graph_circuity
 781        else:
 782            direct_off_graph_length = haversine(
 783                coordinate_path[0], coordinate_path[1], circuity=1
 784            ) + haversine(coordinate_path[-2], coordinate_path[-1], circuity=1)
 785            return round(
 786                output["length"]
 787                + direct_off_graph_length
 788                * (off_graph_circuity - node_addition_circuity),
 789                4,
 790            )
 791
 792    def get_coordinate_path(self, path: list[int]) -> list[dict[float | int]]:
 793        """
 794        Function:
 795
 796        - Return a list of node dictionaries (lat + long) in the order they are visited
 797
 798        Required Arguments:
 799
 800        - `path`
 801            - Type: list
 802            - What: A list of node ids in the order they are visited
 803
 804        Optional Arguments:
 805
 806        - None
 807        """
 808        return [self.nodes[node_id] for node_id in path]
 809
 810    def remove_appended_node(self) -> None:
 811        """
 812        Function:
 813
 814        - Remove the last node that was appended to the graph
 815        - Assumes that this node has symmetric flows
 816            - EG: If node A has a distance of 10 to node B, then node B has a distance of 10 to node A
 817        - Return None
 818
 819        Required Arguments:
 820
 821        - None
 822
 823        Optional Arguments:
 824
 825        - None
 826        """
 827        node_id = len(self.graph) - 1
 828        for reverse_connection in [i for i in self.graph[node_id].keys()]:
 829            del self.graph[reverse_connection][node_id]
 830        self.graph = self.graph[:node_id]
 831        self.nodes = self.nodes[:node_id]
 832
 833    def get_node_distances(
 834        self,
 835        node: list,
 836        circuity: [float | int],
 837        node_addition_type: str,
 838        node_addition_math: str,
 839        lat_lon_bound: [float | int],
 840    ) -> dict[float | int]:
 841        """
 842        Function:
 843
 844        - Get the distances between a node and all other nodes in the graph
 845        - This is used to determine the closest node to add to the graph when adding a new node
 846
 847        Required Arguments:
 848
 849        - `node`
 850            - Type: list
 851            - What: A list of the latitude and longitude of the node
 852            - EG: [latitude, longitude] -> [31.23, 121.47]
 853        - `circuity`
 854            - Type: int | float
 855            - What: The circuity to apply to any distance calculations
 856            - Note: This defaults to 4 to prevent the algorithm from taking a direct route in direction of the destination over some impassible terrain (EG: a maritime network that goes through land)
 857        - `node_addition_type`
 858            - Type: str
 859            - What: The type of node addition to use
 860            - Options:
 861                - 'quadrant': Add the closest node in each quadrant (ne, nw, se, sw) to the distance matrix for this node
 862                - 'closest': Add only the closest node to the distance matrix for this node
 863                - 'all': Add all nodes to the distance matrix for this node
 864            - Notes:
 865                - `dijkstra_makowski` will operate substantially faster if the `node_addition_type` is set to 'quadrant' or 'closest'
 866                - `dijkstra` will operate at the similar speeds regardless of the `node_addition_type`
 867                - When using `all`, you should consider using `dijkstra` instead of `dijkstra_makowski` as it will be faster
 868        - `node_addition_math`
 869            - Type: str
 870            - What: The math to use when calculating the distance between nodes when determining the closest node (or closest quadrant node) to add to the graph
 871            - Default: 'euclidean'
 872            - Options:
 873                - 'euclidean': Use the euclidean distance between nodes. This is much faster but is not accurate (especially near the poles)
 874                - 'haversine': Use the haversine distance between nodes. This is slower but is an accurate representation of the surface distance between two points on the earth
 875            - Notes:
 876                - Once the closest node (or closest quadrant node) is determined, the haversine distance (with circuity) is used to calculate the distance between the nodes when adding it to the graph.
 877        - `lat_lon_bound`
 878            - Type: int | float
 879            - What: Forms a bounding box around the node that is to be added to graph. Only selects graph nodes to consider joining that are within this bounding box.
 880        """
 881        assert node_addition_type in [
 882            "quadrant",
 883            "all",
 884            "closest",
 885        ], f"Invalid node addition type provided ({node_addition_type}), valid options are: ['quadrant', 'all', 'closest']"
 886        assert node_addition_math in [
 887            "euclidean",
 888            "haversine",
 889        ], f"Invalid node addition math provided ({node_addition_math}), valid options are: ['euclidean', 'haversine']"
 890        # Get only bounded nodes
 891        nodes = {
 892            node_idx: node_i
 893            for node_idx, node_i in enumerate(self.nodes)
 894            if abs(node_i[0] - node[0]) < lat_lon_bound
 895            and abs(node_i[1] - node[1]) < lat_lon_bound
 896        }
 897        if len(nodes) == 0:
 898            # Default to all if the lat_lon_bound fails to find any nodes
 899            return self.get_node_distances(
 900                node=node,
 901                circuity=circuity,
 902                lat_lon_bound=180,
 903                node_addition_type=node_addition_type,
 904                node_addition_math=node_addition_math,
 905            )
 906        if node_addition_type == "all":
 907            return {
 908                node_idx: round(haversine(node, node_i, circuity=circuity), 4)
 909                for node_idx, node_i in nodes.items()
 910            }
 911        if node_addition_math == "haversine":
 912            dist_fn = lambda x: round(haversine(node, x, circuity=circuity), 4)
 913        else:
 914            dist_fn = lambda x: round(
 915                ((node[0] - x[0]) ** 2 + (node[1] - x[1]) ** 2) ** 0.5, 4
 916            )
 917        if node_addition_type == "closest":
 918            quadrant_fn = lambda x, y: "all"
 919        else:
 920            quadrant_fn = lambda x, y: ("n" if x[0] - y[0] > 0 else "s") + (
 921                "e" if x[1] - y[1] > 0 else "w"
 922            )
 923        min_diffs = {}
 924        min_diffs_idx = {}
 925        for node_idx, node_i in nodes.items():
 926            quadrant = quadrant_fn(node_i, node)
 927            dist = dist_fn(node_i)
 928            if dist < min_diffs.get(quadrant, 999999999):
 929                min_diffs[quadrant] = dist
 930                min_diffs_idx[quadrant] = node_idx
 931        return {
 932            node_idx: round(
 933                haversine(node, self.nodes[node_idx], circuity=circuity), 4
 934            )
 935            for node_idx in min_diffs_idx.values()
 936        }
 937
 938    def add_node(
 939        self,
 940        node: dict[float | int],
 941        circuity: [float | int],
 942        node_addition_type: str = "quadrant",
 943        node_addition_math: str = "euclidean",
 944        lat_lon_bound: [float | int] = 5,
 945    ) -> int:
 946        """
 947        Function:
 948
 949        - Add a node to the network
 950        - Returns the id of the new node
 951
 952        Required Arguments:
 953
 954        - `node`
 955            - Type: dict
 956            - What: A dictionary with the keys 'latitude' and 'longitude'
 957
 958        Optional Arguments:
 959
 960        - `circuity`
 961            - Type: int | float
 962            - What: The circuity to apply to any distance calculations
 963            - Default: 4
 964            - Note: This defaults to 4 to prevent the algorithm from taking a direct route in direction of the destination over some impassible terrain (EG: a maritime network that goes through land)
 965        - `node_addition_type`
 966            - Type: str
 967            - What: The type of node addition to use
 968            - Default: 'quadrant'
 969            - Options:
 970                - 'quadrant': Add the closest node in each quadrant (ne, nw, se, sw) to the distance matrix for this node
 971                - 'closest': Add only the closest node to the distance matrix for this node
 972                - 'all': Add all nodes to the distance matrix for this node
 973            - Notes:
 974                - `dijkstra_makowski` will operate substantially faster if the `node_addition_type` is set to 'quadrant' or 'closest'
 975                - `dijkstra` will operate at the similar speeds regardless of the `node_addition_type`
 976                - When using `all`, you should consider using `dijkstra` instead of `dijkstra_makowski` as it will be faster
 977        - `node_addition_math`
 978            - Type: str
 979            - What: The math to use when calculating the distance between nodes when determining the closest node (or closest quadrant node) to add to the graph
 980            - Default: 'euclidean'
 981            - Options:
 982                - 'euclidean': Use the euclidean distance between nodes. This is much faster but is not accurate (especially near the poles)
 983                - 'haversine': Use the haversine distance between nodes. This is slower but is an accurate representation of the surface distance between two points on the earth
 984            - Notes:
 985                - Once the closest node (or closest quadrant node) is determined, the haversine distance (with circuity) is used to calculate the distance between the nodes when adding it to the graph.
 986        - `lat_lon_bound`
 987            - Type: int | float
 988            - What: Forms a bounding box around the node that is to be added to graph. Only selects graph nodes to consider joining that are within this bounding box.
 989            - Default: 5
 990
 991        """
 992        # Validate the inputs
 993        assert isinstance(node, dict), "Node must be a dictionary"
 994        assert "latitude" in node.keys(), "Node must have a latitude"
 995        assert "longitude" in node.keys(), "Node must have a longitude"
 996        assert (
 997            node["latitude"] >= -90 and node["latitude"] <= 90
 998        ), "Latitude must be between -90 and 90"
 999        assert (
1000            node["longitude"] >= -180 and node["longitude"] <= 180
1001        ), "Longitude must be between -180 and 180"
1002        assert circuity > 0, "Circuity must be greater than 0"
1003        assert node_addition_type in [
1004            "quadrant",
1005            "all",
1006            "closest",
1007        ], f"Invalid node addition type provided ({node_addition_type}), valid options are: ['quadrant', 'all', 'closest']"
1008        assert node_addition_math in [
1009            "euclidean",
1010            "haversine",
1011        ], f"Invalid node addition math provided ({node_addition_math}), valid options are: ['euclidean', 'haversine']"
1012        assert isinstance(
1013            lat_lon_bound, (int, float)
1014        ), "Lat_lon_bound must be a number"
1015        assert lat_lon_bound > 0, "Lat_lon_bound must be greater than 0"
1016        node = [node["latitude"], node["longitude"]]
1017        # Get the distances to all other nodes
1018        distances = self.get_node_distances(
1019            node=node,
1020            circuity=circuity,
1021            node_addition_type=node_addition_type,
1022            node_addition_math=node_addition_math,
1023            lat_lon_bound=lat_lon_bound,
1024        )
1025
1026        # Create the node
1027        new_node_id = len(self.graph)
1028        self.nodes.append(node)
1029        self.graph.append(distances)
1030        for node_idx, node_distance in distances.items():
1031            self.graph[node_idx][new_node_id] = node_distance
1032        return new_node_id
1033
1034    def save_as_geojson(self, filename: str) -> None:
1035        """
1036        Function:
1037
1038        - Save the current geograph object as a geojson file specifed by `filename`
1039        - This is useful for understanding the underlying geograph and for debugging purposes
1040        - Returns None
1041
1042        Required Arguments:
1043
1044        - `filename`
1045            - Type: str
1046            - What: The filename to save the geojson file as
1047
1048        """
1049        features = []
1050        for origin_idx, destinations in enumerate(self.graph):
1051            for destination_idx, distance in destinations.items():
1052                # Create an undirected graph for geojson purposes
1053                if origin_idx > destination_idx:
1054                    continue
1055                origin = self.nodes[origin_idx]
1056                destination = self.nodes[destination_idx]
1057                features.append(
1058                    {
1059                        "type": "Feature",
1060                        "properties": {
1061                            "origin_idx": origin_idx,
1062                            "destination_idx": destination_idx,
1063                            "distance": distance,
1064                        },
1065                        "geometry": {
1066                            "type": "LineString",
1067                            "coordinates": [
1068                                [origin[1], origin[0]],
1069                                [
1070                                    destination[1],
1071                                    destination[0],
1072                                ],
1073                            ],
1074                        },
1075                    }
1076                )
1077
1078        out_dict = {"type": "FeatureCollection", "features": features}
1079        with open(filename, "w") as f:
1080            json.dump(out_dict, f)
1081
1082    def save_as_geograph(self, name: str) -> None:
1083        """
1084        Function:
1085
1086        - Save the current geograph as an importable python file
1087
1088        Required Arguments:
1089
1090        - `name`
1091            - Type: str
1092            - What: The name of the geograph and file
1093            - EG: 'custom'
1094                - Stored as: 'custom.py'
1095                    - In your current directory
1096                - Import as: 'from .custom import custom_geograph'
1097        """
1098        self.validate_nodes()
1099        self.validate_graph(check_symmetry=True, check_connected=False)
1100        out_string = f"""from scgraph.core import GeoGraph\ngraph={str(self.graph)}\nnodes={str(self.nodes)}\n{name}_geograph = GeoGraph(graph=graph, nodes=nodes)"""
1101        with open(name + ".py", "w") as f:
1102            f.write(out_string)
1103
1104    def mod_remove_arc(
1105        self, origin_idx: int, destination_idx: int, undirected: bool = True
1106    ) -> None:
1107        """
1108        Function:
1109
1110        - Remove an arc from the graph
1111
1112        Required Arguments:
1113
1114        - `origin_idx`
1115            - Type: int
1116            - What: The index of the origin node
1117        - `destination_idx`
1118            - Type: int
1119            - What: The index of the destination node
1120
1121        Optional Arguments:
1122
1123        - `undirected`
1124            - Type: bool
1125            - What: Whether to remove the arc in both directions
1126            - Default: True
1127        """
1128        assert origin_idx < len(self.graph), "Origin node does not exist"
1129        assert destination_idx < len(
1130            self.graph
1131        ), "Destination node does not exist"
1132        assert destination_idx in self.graph[origin_idx], "Arc does not exist"
1133        del self.graph[origin_idx][destination_idx]
1134        if undirected:
1135            if origin_idx in self.graph[destination_idx]:
1136                del self.graph[destination_idx][origin_idx]
1137
1138    def mod_add_node(
1139        self, latitude: [float | int], longitude: [float | int]
1140    ) -> int:
1141        """
1142        Function:
1143
1144        - Add a node to the graph
1145
1146        Required Arguments:
1147
1148        - `latitude`
1149            - Type: int | float
1150            - What: The latitude of the node
1151        - `longitude`
1152            - Type: int | float
1153            - What: The longitude of the node
1154
1155        Returns:
1156
1157        - The index of the new node
1158        """
1159        self.nodes.append([latitude, longitude])
1160        self.graph.append({})
1161        return len(self.graph) - 1
1162
1163    def mod_add_arc(
1164        self,
1165        origin_idx: int,
1166        destination_idx: int,
1167        distance: [float | int] = 0,
1168        use_haversine_distance=True,
1169        undirected: bool = True,
1170    ) -> None:
1171        """
1172        Function:
1173
1174        - Add an arc to the graph
1175
1176        Required Arguments:
1177
1178        - `origin_idx`
1179            - Type: int
1180            - What: The index of the origin node
1181        - `destination_idx`
1182            - Type: int
1183            - What: The index of the destination node
1184
1185        Optional Arguments:
1186
1187        - `distance`
1188            - Type: int | float
1189            - What: The distance between the origin and destination nodes in terms of the graph distance (normally km)
1190            - Default: 0
1191        - `use_haversine_distance`
1192            - Type: bool
1193            - What: Whether to calculate the haversine distance (km) between the nodes when calculating the distance
1194            - Default: True
1195            - Note: If true, overrides the `distance` argument
1196        - `undirected`
1197            - Type: bool
1198            - What: Whether to add the arc in both directions
1199            - Default: True
1200        """
1201        assert origin_idx < len(self.graph), "Origin node does not exist"
1202        assert destination_idx < len(
1203            self.graph
1204        ), "Destination node does not exist"
1205        if use_haversine_distance:
1206            distance = haversine(
1207                self.nodes[origin_idx], self.nodes[destination_idx]
1208            )
1209        self.graph[origin_idx][destination_idx] = distance
1210        if undirected:
1211            self.graph[destination_idx][origin_idx] = distance
1212
1213
1214def load_geojson_as_geograph(geojson_filename: str) -> GeoGraph:
1215    """
1216    Function:
1217
1218    - Create a CustomGeoGraph object loaded from a geojson file
1219
1220    Required Arguments:
1221
1222    - `geojson_filename`
1223        - Type: str
1224        - What: The filename of the geojson file to load
1225        - Note: All arcs read in will be undirected
1226        - Note: This geojson file must be formatted in a specific way
1227            - The geojson file must be a FeatureCollection
1228            - Each feature must be a LineString with two coordinate pairs
1229                - The first coordinate pair must be the origin node
1230                - The second coordinate pair must be the destination node
1231                - The properties of the feature must include the distance between the origin and destination nodes
1232                - The properties of the feature must include the origin and destination node idxs
1233                - Origin and destination node idxs must be integers between 0 and n-1 where n is the number of nodes in the graph
1234            - EG:
1235            ```
1236            {
1237                "type": "FeatureCollection",
1238                "features": [
1239                    {
1240                        "type": "Feature",
1241                        "properties": {
1242                            "origin_idx": 0,
1243                            "destination_idx": 1,
1244                            "distance": 10
1245                        },
1246                        "geometry": {
1247                            "type": "LineString",
1248                            "coordinates": [
1249                                [121.47, 31.23],
1250                                [121.48, 31.24]
1251                            ]
1252                        }
1253                    }
1254                ]
1255            }
1256            ```
1257    """
1258    with open(geojson_filename, "r") as f:
1259        geojson_features = json.load(f).get("features", [])
1260
1261    nodes_dict = {}
1262    graph_dict = {}
1263    for feature in geojson_features:
1264        properties = feature.get("properties", {})
1265        origin_idx = properties.get("origin_idx")
1266        destination_idx = properties.get("destination_idx")
1267        distance = properties.get("distance")
1268        geometry = feature.get("geometry", {})
1269        coordinates = geometry.get("coordinates", [])
1270
1271        # Validations
1272        assert (
1273            feature.get("type") == "Feature"
1274        ), "All features must be of type 'Feature'"
1275        assert (
1276            geometry.get("type") == "LineString"
1277        ), "All geometries must be of type 'LineString'"
1278        assert (
1279            len(coordinates) == 2
1280        ), "All LineStrings must have exactly 2 coordinates"
1281        assert isinstance(
1282            origin_idx, int
1283        ), "All features must have an 'origin_idx' property that is an integer"
1284        assert isinstance(
1285            destination_idx, int
1286        ), "All features must have a 'destination_idx' property that is an integer"
1287        assert isinstance(
1288            distance, (int, float)
1289        ), "All features must have a 'distance' property that is a number"
1290        assert (
1291            origin_idx >= 0
1292        ), "All origin_idxs must be greater than or equal to 0"
1293        assert (
1294            destination_idx >= 0
1295        ), "All destination_idxs must be greater than or equal to 0"
1296        assert distance >= 0, "All distances must be greater than or equal to 0"
1297        origin = coordinates[0]
1298        destination = coordinates[1]
1299        assert isinstance(origin, list), "All coordinates must be lists"
1300        assert isinstance(destination, list), "All coordinates must be lists"
1301        assert len(origin) == 2, "All coordinates must have a length of 2"
1302        assert len(destination) == 2, "All coordinates must have a length of 2"
1303        assert all(
1304            [isinstance(i, (int, float)) for i in origin]
1305        ), "All coordinates must be numeric"
1306        assert all(
1307            [isinstance(i, (int, float)) for i in destination]
1308        ), "All coordinates must be numeric"
1309        # assert all([origin[0] >= -90, origin[0] <= 90, origin[1] >= -180, origin[1] <= 180]), "All coordinates must be valid latitudes and longitudes"
1310        # assert all([destination[0] >= -90, destination[0] <= 90, destination[1] >= -180, destination[1] <= 180]), "All coordinates must be valid latitudes and longitudes"
1311
1312        # Update the data
1313        nodes_dict[origin_idx] = origin
1314        nodes_dict[destination_idx] = destination
1315        graph_dict[origin_idx] = {
1316            **graph_dict.get(origin_idx, {}),
1317            destination_idx: distance,
1318        }
1319        graph_dict[destination_idx] = {
1320            **graph_dict.get(destination_idx, {}),
1321            origin_idx: distance,
1322        }
1323    assert len(nodes_dict) == len(
1324        graph_dict
1325    ), "All nodes must be included as origins in the graph dictionary"
1326    nodes = [
1327        [i[1][1], i[1][0]]
1328        for i in sorted(nodes_dict.items(), key=lambda x: x[0])
1329    ]
1330    ordered_graph_tuple = sorted(graph_dict.items(), key=lambda x: x[0])
1331    graph_map = {i[0]: idx for idx, i in enumerate(ordered_graph_tuple)}
1332    graph = [
1333        {graph_map[k]: v for k, v in i[1].items()} for i in ordered_graph_tuple
1334    ]
1335    return GeoGraph(graph=graph, nodes=nodes)
1336
1337
1338def get_multi_path_geojson(
1339    routes: list[dict],
1340    filename: [str, None] = None,
1341    show_progress: bool = False,
1342) -> dict:
1343    """
1344    Creates a GeoJSON file with the shortest path between the origin and destination of each route.
1345
1346    Required Parameters:
1347
1348    - `routes`: list[dict]
1349        - List of dictionaries with the following keys:
1350            - geograph: GeoGraph
1351                - Geograph object to use for the shortest path calculation.
1352            - origin: dict[float|float]
1353                - Origin coordinates
1354                - EG: {"latitude":39.2904, "longitude":-76.6122}
1355            - destination: dict[float|int]
1356                - Destination coordinates
1357                - EG: {"latitude":39.2904, "longitude":-76.6122}
1358            - properties: dict
1359                - Dictionary with the properties of the route
1360                - Everything in this dictionary will be included in the output GeoJSON file as properties of the route.
1361                - EG: {"id":"route_1", "name":"Route 1", "color":"#ff0000"}
1362
1363    Optional Parameters:
1364
1365    - `filename`: str | None
1366        - Name of the output GeoJSON file.
1367        - If None, the function will not save the file
1368        - Default: None
1369    - `show_progress`: bool
1370        - Whether to show basic progress information
1371        - Default: False
1372
1373    Returns
1374
1375    - `output`: dict
1376        - Dictionary with the GeoJSON file content.
1377    """
1378    assert isinstance(routes, list), "Routes must be a list"
1379    assert all(
1380        [isinstance(i, dict) for i in routes]
1381    ), "Routes must be a list of dictionaries"
1382    assert all(
1383        [isinstance(i.get("geograph"), GeoGraph) for i in routes]
1384    ), "All routes must have a 'geograph' key with a GeoGraph object"
1385    assert all(
1386        [isinstance(i.get("origin"), dict) for i in routes]
1387    ), "All routes must have an 'origin' key with a dictionary"
1388    assert all(
1389        [isinstance(i.get("destination"), dict) for i in routes]
1390    ), "All routes must have a 'destination' key with a dictionary"
1391    assert all(
1392        [isinstance(i.get("properties"), dict) for i in routes]
1393    ), "All routes must have a 'properties' key with a dictionary"
1394    assert all(
1395        [isinstance(i["origin"].get("latitude"), (int, float)) for i in routes]
1396    ), "All origins must have a 'latitude' key with a number"
1397    assert all(
1398        [isinstance(i["origin"].get("longitude"), (int, float)) for i in routes]
1399    ), "All origins must have a 'longitude' key with a number"
1400    assert all(
1401        [
1402            isinstance(i["destination"].get("latitude"), (int, float))
1403            for i in routes
1404        ]
1405    ), "All destinations must have a 'latitude' key with a number"
1406    assert all(
1407        [
1408            isinstance(i["destination"].get("longitude"), (int, float))
1409            for i in routes
1410        ]
1411    ), "All destinations must have a 'longitude' key with a number"
1412    assert all(
1413        [
1414            (
1415                i["origin"].get("latitude") >= -90
1416                and i["origin"].get("latitude") <= 90
1417            )
1418            for i in routes
1419        ]
1420    ), "All origin latitudes must be between -90 and 90"
1421    assert all(
1422        [
1423            (
1424                i["origin"].get("longitude") >= -180
1425                and i["origin"].get("longitude") <= 180
1426            )
1427            for i in routes
1428        ]
1429    ), "All origin longitudes must be between -180 and 180"
1430    assert all(
1431        [
1432            (
1433                i["destination"].get("latitude") >= -90
1434                and i["destination"].get("latitude") <= 90
1435            )
1436            for i in routes
1437        ]
1438    ), "All destination latitudes must be between -90 and 90"
1439    assert all(
1440        [
1441            (
1442                i["destination"].get("longitude") >= -180
1443                and i["destination"].get("longitude") <= 180
1444            )
1445            for i in routes
1446        ]
1447    ), "All destination longitudes must be between -180 and 180"
1448
1449    output = {"type": "FeatureCollection", "features": []}
1450    len_routes = len(routes)
1451    for idx, route in enumerate(routes):
1452        shortest_path = route["geograph"].get_shortest_path(
1453            route["origin"], route["destination"]
1454        )
1455        shortest_line_path = get_line_path(shortest_path)
1456        output["features"].append(
1457            {
1458                "type": "Feature",
1459                "properties": route["properties"],
1460                "geometry": shortest_line_path,
1461            }
1462        )
1463        if show_progress:
1464            print(
1465                f"[{'='*(int((idx+1)/len_routes*20))}>{' '*(20-int((idx+1)/len_routes*20))}] {idx+1}/{len_routes}",
1466                end="\r",
1467            )
1468    if show_progress:
1469        print()
1470    if filename is not None:
1471        json.dump(output, open(filename, "w"))
1472    return output