scgraph.graph

  1from heapq import heappop, heappush
  2from typing import Any
  3from scgraph.graph_utils import GraphUtils, GraphModifiers
  4from scgraph.contraction_hierarchies import CHGraph
  5from bmsspy import Bmssp
  6
  7
  8class GraphTrees:
  9    def get_shortest_path_tree(self, origin_id: int | set[int]) -> dict:
 10        """
 11        Function:
 12
 13        - Calculate the shortest path tree of a graph using Dijkstra's algorithm
 14
 15        Required Arguments:
 16
 17        - `origin_id`
 18            - Type: int | set[int]
 19            - What: The id(s) of the node(s) from which to calculate the shortest path tree
 20
 21        Returns:
 22
 23        - A dictionary with the following keys:
 24            - `origin_id`: The id of the node from which the shortest path tree was calculated
 25            - `predecessors`: A list of node ids referring to the predecessor of each node given the shortest path tree
 26                - Note: For disconnected graphs, nodes that are not connected to the origin node will have a predecessor of None
 27            - `distance_matrix`: A list of distances from the origin node to each node in the graph
 28                - Note: For disconnected graphs, nodes that are not connected to the origin node will have a distance of float("inf")
 29
 30        """
 31        # Input Validation
 32        self.__input_check__(origin_id=origin_id, destination_id=0)
 33        origin_ids = {origin_id} if isinstance(origin_id, int) else origin_id
 34
 35        # Variable Initialization
 36        distance_matrix = [float("inf")] * len(self.graph)
 37        open_leaves = []
 38        predecessor = [-1] * len(self.graph)
 39
 40        for oid in origin_ids:
 41            distance_matrix[oid] = 0
 42            heappush(open_leaves, (0, oid))
 43
 44        while open_leaves:
 45            current_distance, current_id = heappop(open_leaves)
 46            for connected_id, connected_distance in self.graph[
 47                current_id
 48            ].items():
 49                possible_distance = current_distance + connected_distance
 50                if possible_distance < distance_matrix[connected_id]:
 51                    distance_matrix[connected_id] = possible_distance
 52                    predecessor[connected_id] = current_id
 53                    heappush(open_leaves, (possible_distance, connected_id))
 54
 55        return {
 56            "origin_id": origin_id,
 57            "predecessors": predecessor,
 58            "distance_matrix": distance_matrix,
 59        }
 60
 61    def get_tree_path(
 62        self,
 63        origin_id: int,
 64        destination_id: int,
 65        tree_data: dict,
 66        length_only: bool = False,
 67    ) -> dict:
 68        """
 69        Function:
 70
 71        - Get the path from the origin node to the destination node using the provided tree_data
 72        - Return a list of node ids in the order they are visited as well as the length of the path
 73        - If the destination node is not reachable from the origin node, return None
 74
 75        Required Arguments:
 76
 77        - `origin_id`
 78            - Type: int
 79            - What: The id of the origin node from the graph dictionary to start the shortest path from
 80            - Note: Since multiple origins are possible, if the origin_id is not a predecessor node of the destination node, the closest origin will be used.
 81        - `destination_id`
 82            - Type: int
 83            - What: The id of the destination node from the graph dictionary to end the shortest path at
 84        - `tree_data`
 85            - Type: dict
 86            - What: The output from a tree function
 87
 88        Optional Arguments:
 89
 90        - `length_only`
 91            - Type: bool
 92            - What: If True, only returns the length of the path
 93            - Default: False
 94
 95        Returns:
 96
 97        - A dictionary with the following keys:
 98            - `path`: A list of node ids in the order they are visited from the origin node to the destination node
 99            - `length`: The length of the path from the origin node to the destination node
100        """
101        if tree_data["origin_id"] != origin_id:
102            raise Exception(
103                "The origin node must be the same as the spanning node for this function to work."
104            )
105        destination_distance = tree_data["distance_matrix"][destination_id]
106        if destination_distance == float("inf"):
107            raise Exception(
108                "Something went wrong, the origin and destination nodes are not connected."
109            )
110        if length_only:
111            return {"length": destination_distance}
112        current_id = destination_id
113        current_path = [destination_id]
114        while current_id != origin_id and current_id != -1:
115            current_id = tree_data["predecessors"][current_id]
116            current_path.append(current_id)
117        current_path.reverse()
118        return {
119            "path": current_path,
120            "length": destination_distance,
121        }
122
123
124class GraphAlgorithms:
125    def dijkstra(
126        self,
127        origin_id: int | set[int],
128        destination_id: int,
129    ) -> dict:
130        """
131        Function:
132
133        - Identify the shortest path between two nodes in a sparse network graph using a modified Dijkstra algorithm
134
135        - Return a dictionary of various path information including:
136            - `path`: A list of node ids in the order they are visited
137            - `length`: The length of the path from the origin node to the destination node
138
139        Required Arguments:
140
141        - `origin_id`
142            - Type: int | set[int]
143            - What: The id(s) of the origin node(s) from the graph dictionary to start the shortest path from
144        - `destination_id`
145            - Type: int
146            - What: The id of the destination node from the graph dictionary to end the shortest path at
147
148        Optional Arguments:
149
150        - None
151        """
152        # Input Validation
153        self.__input_check__(origin_id=origin_id, destination_id=destination_id)
154        origin_ids = {origin_id} if isinstance(origin_id, int) else origin_id
155        # Variable Initialization
156        distance_matrix = [float("inf")] * len(self.graph)
157        predecessor = [-1] * len(self.graph)
158        open_leaves = []
159
160        for oid in origin_ids:
161            distance_matrix[oid] = 0
162            heappush(open_leaves, (0, oid))
163
164        while open_leaves:
165            current_distance, current_id = heappop(open_leaves)
166            if current_id == destination_id:
167                break
168            # Technically, the next line is not necessary but can help with performance
169            if current_distance == distance_matrix[current_id]:
170                for connected_id, connected_distance in self.graph[
171                    current_id
172                ].items():
173                    possible_distance = current_distance + connected_distance
174                    if possible_distance < distance_matrix[connected_id]:
175                        distance_matrix[connected_id] = possible_distance
176                        predecessor[connected_id] = current_id
177                        heappush(open_leaves, (possible_distance, connected_id))
178        if current_id != destination_id:
179            raise Exception(
180                "Something went wrong, the origin and destination nodes are not connected."
181            )
182
183        return {
184            "path": self.__reconstruct_path__(destination_id, predecessor),
185            "length": distance_matrix[destination_id],
186        }
187
188    def dijkstra_negative(
189        self,
190        origin_id: int | set[int],
191        destination_id: int,
192        cycle_check_iterations: int | None = None,
193    ) -> dict:
194        """
195        Function:
196
197        - Identify the shortest path between two nodes in a sparse network graph using a modified Dijkstra algorithm that catches negative cycles
198            - Negative cycles raise an exception if they are detected
199        - Note: This algorithm is guaranteed to find the shortest path or raise an exception if a negative cycle is detected
200        - Note: This algorithm requires computing the entire shortest path tree of the graph and is therefore not able to be terminated early
201            - For non negative weighted graphs, it is recommended to use the `dijkstra` algorithm instead
202        - Note: This should be fairly performant in general, however it does have a higher worst-case time complexity than Bellman-Ford
203
204        - Return a dictionary of various path information including:
205            - `id_path`: A list of node ids in the order they are visited
206            - `path`: A list of node dictionaries (lat + long) in the order they are visited
207
208        Required Arguments:
209
210        - `origin_id`
211            - Type: int | set[int]
212            - What: The id(s) of the origin node(s) from the graph dictionary to start the shortest path from
213        - `destination_id`
214            - Type: int
215            - What: The id of the destination node from the graph dictionary to end the shortest path at
216
217        Optional Arguments:
218
219        - `cycle_check_iterations`
220            - Type: int | None
221            - What: The number of iterations to loop over before checking for negative cycles
222            - Default: None (Then set to the number of nodes in the graph)
223        """
224        # Input Validation
225        self.__input_check__(origin_id=origin_id, destination_id=destination_id)
226        origin_ids = {origin_id} if isinstance(origin_id, int) else origin_id
227
228        # Variable Initialization
229        distance_matrix = [float("inf")] * len(self.graph)
230        predecessor = [-1] * len(self.graph)
231        open_leaves = []
232
233        for oid in origin_ids:
234            distance_matrix[oid] = 0
235            heappush(open_leaves, (0, oid))
236
237        # Cycle iteration Variables
238        cycle_iteration = 0
239        if cycle_check_iterations is None:
240            cycle_check_iterations = len(self.graph)
241
242        while open_leaves:
243            current_distance, current_id = heappop(open_leaves)
244            if current_distance == distance_matrix[current_id]:
245                # Increment the cycle iteration counter and check for negative cycles if the iteration limit is reached
246                cycle_iteration += 1
247                if cycle_iteration >= cycle_check_iterations:
248                    cycle_iteration = 0  # Reset the cycle iteration counter
249                    self.__cycle_check__(
250                        predecessor_matrix=predecessor, node_id=current_id
251                    )
252                for connected_id, connected_distance in self.graph[
253                    current_id
254                ].items():
255                    possible_distance = current_distance + connected_distance
256                    if possible_distance < distance_matrix[connected_id]:
257                        distance_matrix[connected_id] = possible_distance
258                        predecessor[connected_id] = current_id
259                        heappush(open_leaves, (possible_distance, connected_id))
260
261        if distance_matrix[destination_id] == float("inf"):
262            raise Exception(
263                "Something went wrong, the origin and destination nodes are not connected."
264            )
265
266        return {
267            "path": self.__reconstruct_path__(destination_id, predecessor),
268            "length": distance_matrix[destination_id],
269        }
270
271    def a_star(
272        self,
273        origin_id: int | set[int],
274        destination_id: int,
275        heuristic_fn: callable = None,
276    ) -> dict:
277        """
278        Function:
279
280        - Identify the shortest path between two nodes in a sparse network graph using an A* extension of Makowski's modified Dijkstra algorithm
281        - Return a dictionary of various path information including:
282            - `id_path`: A list of node ids in the order they are visited
283            - `path`: A list of node dictionaries (lat + long) in the order they are visited
284
285        Required Arguments:
286
287        - `origin_id`
288            - Type: int | set[int]
289            - What: The id of the origin node from the graph dictionary to start the shortest path from
290        - `destination_id`
291            - Type: int
292            - What: The id of the destination node from the graph dictionary to end the shortest path at
293        - `heuristic_fn`
294            - Type: function
295            - What: A heuristic function that takes two node ids and returns an estimated distance between them
296            - Note: If None, returns the shortest path using Dijkstra's algorithm
297            - Default: None
298
299        Optional Arguments:
300
301        - None
302        """
303        if heuristic_fn is None:
304            return self.dijkstra(
305                origin_id=origin_id,
306                destination_id=destination_id,
307            )
308        # Input Validation
309        self.__input_check__(origin_id=origin_id, destination_id=destination_id)
310        origin_ids = {origin_id} if isinstance(origin_id, int) else origin_id
311
312        # Variable Initialization
313        distance_matrix = [float("inf")] * len(self.graph)
314        # Using a visited matrix does add a tad bit of overhead but avoids revisiting nodes
315        # and does not require anything extra to be stored in the heap
316        visited = [0] * len(self.graph)
317        open_leaves = []
318        predecessor = [-1] * len(self.graph)
319
320        for oid in origin_ids:
321            distance_matrix[oid] = 0
322            heappush(open_leaves, (0, oid))
323
324        while open_leaves:
325            current_id = heappop(open_leaves)[1]
326            if current_id == destination_id:
327                break
328            if visited[current_id] == 1:
329                continue
330            visited[current_id] = 1
331            current_distance = distance_matrix[current_id]
332            for connected_id, connected_distance in self.graph[
333                current_id
334            ].items():
335                possible_distance = current_distance + connected_distance
336                if possible_distance < distance_matrix[connected_id]:
337                    distance_matrix[connected_id] = possible_distance
338                    predecessor[connected_id] = current_id
339                    heappush(
340                        open_leaves,
341                        (
342                            possible_distance
343                            + heuristic_fn(connected_id, destination_id),
344                            connected_id,
345                        ),
346                    )
347        if current_id != destination_id:
348            raise Exception(
349                "Something went wrong, the origin and destination nodes are not connected."
350            )
351
352        return {
353            "path": self.__reconstruct_path__(destination_id, predecessor),
354            "length": distance_matrix[destination_id],
355        }
356
357    def bellman_ford(
358        self,
359        origin_id: int | set[int],
360        destination_id: int,
361    ) -> dict:
362        """
363        Function:
364
365        - Identify the shortest path between two nodes in a sparse network graph using the Bellman-Ford algorithm
366        - Return a dictionary of various path information including:
367            - `id_path`: A list of node ids in the order they are visited
368            - `path`: A list of node dictionaries (lat + long) in the order they are visited
369
370        Required Arguments:
371
372        - `origin_id`
373            - Type: int | set[int]
374            - What: The id(s) of the origin node(s) from the graph dictionary to start the shortest path from
375        - `destination_id`
376            - Type: int
377            - What: The id of the destination node from the graph dictionary to end the shortest path at
378
379        Optional Arguments:
380
381        - None
382        """
383        # Input Validation
384        self.__input_check__(origin_id=origin_id, destination_id=destination_id)
385        origin_ids = {origin_id} if isinstance(origin_id, int) else origin_id
386        # Variable Initialization
387        distance_matrix = [float("inf")] * len(self.graph)
388        predecessor = [-1] * len(self.graph)
389
390        for oid in origin_ids:
391            distance_matrix[oid] = 0
392
393        len_graph = len(self.graph)
394        for i in range(len_graph):
395            for current_id in range(len(self.graph)):
396                current_distance = distance_matrix[current_id]
397                for connected_id, connected_distance in self.graph[
398                    current_id
399                ].items():
400                    possible_distance = current_distance + connected_distance
401                    if possible_distance < distance_matrix[connected_id]:
402                        distance_matrix[connected_id] = possible_distance
403                        predecessor[connected_id] = current_id
404                        if i == len_graph - 1:
405                            raise Exception(
406                                "Graph contains a negative weight cycle"
407                            )
408        # Check if destination is reachable
409        if distance_matrix[destination_id] == float("inf"):
410            raise Exception(
411                "Something went wrong, the origin and destination nodes are not connected."
412            )
413
414        return {
415            "path": self.__reconstruct_path__(destination_id, predecessor),
416            "length": distance_matrix[destination_id],
417        }
418
419    def bmssp(
420        self,
421        origin_id: int | set[int],
422        destination_id: int,
423        use_constant_degree_graph: bool = True,
424    ):
425        """
426        Function:
427
428        - Identify the shortest path between two nodes in a sparse network graph using the BMSSPy package
429
430        - This is now a wrapper for the BMSSPy package
431            - https://github.com/connor-makowski/bmsspy
432            - For backwards compatibility, this function wraps around the dijkstra function if BMSSPy is not installed
433
434        - Return a dictionary of various path information including:
435            - `id_path`: A list of node ids in the order they are visited
436            - `path`: A list of node dictionaries (lat + long) in the order they are visited
437
438        Required Arguments:
439
440        - `origin_id`
441            - Type: int | set[int]
442            - What: The id(s) of the origin node(s) from the graph dictionary to start the shortest path from
443        - `destination_id`
444            - Type: int
445            - What: The id of the destination node from the graph dictionary to end the shortest path at
446        - `use_constant_degree_graph`
447            - Type: bool
448            - What: Whether to convert the graph to a constant degree 2 graph prior to running the BMSSPy algorithm
449            - Default: True
450
451
452        Optional Arguments:
453
454        - None
455        """
456        bmssp_graph = Bmssp(
457            graph=self.graph,
458            use_constant_degree_graph=use_constant_degree_graph,
459        )
460        output = bmssp_graph.solve(
461            origin_id=origin_id, destination_id=destination_id
462        )
463        return {
464            "path": output["path"],
465            "length": output["length"],
466        }
467
468    def cached_shortest_path(
469        self,
470        origin_id: int,
471        destination_id: int,
472        length_only: bool = False,
473    ):
474        """
475        Function:
476
477        - Get the shortest path between two nodes in the graph attempting to use a cached shortest path tree if available
478        - If a cached shortest path tree is not available, it will compute the shortest path tree and cache it for future use if specified by `cache`
479        - Uses the get_shortest_path_tree (Dijkstra) and get_tree_path functions internally
480        - Stores cached shortest path trees in a list (self.__cache__) where the index corresponds to the origin node id
481        - Note: If you modify this graph after caching shortest path trees, the cached trees may become invalid
482            - You can reset the cache by calling self.reset_cache()
483            - For efficiency, the cache is not automatically reset when the graph is modified
484            - This logic must be handled by the user
485
486        Requires:
487
488        - origin_id: The id of the origin node
489        - destination_id: The id of the destination node
490
491        Optional:
492
493        - length_only: If True, only returns the length of the path
494        """
495        shortest_path_tree = self.__cache__[origin_id]
496        if shortest_path_tree == 0:
497            shortest_path_tree = self.get_shortest_path_tree(
498                origin_id=origin_id
499            )
500            self.__cache__[origin_id] = shortest_path_tree
501        return self.get_tree_path(
502            origin_id=origin_id,
503            destination_id=destination_id,
504            tree_data=shortest_path_tree,
505            length_only=length_only,
506        )
507
508    def create_contraction_hierarchy(
509        self, heuristic_fn=None, ch_graph_kwargs=None
510    ) -> Any:
511        """
512        Function:
513
514        - Create a Contraction Hierarchies (CH) graph from the current Graph object
515        - The CH graph is stored as an instance variable `self.ch_graph`
516
517        Optional Arguments:
518
519        - `heuristic_fn`:
520            - Type: function or None
521            - What: A heuristic function for CH preprocessing
522            - Default: None (uses default heuristic)
523        """
524        if not hasattr(self, "__ch_graph__"):
525            ch_graph_kwargs = (
526                ch_graph_kwargs if ch_graph_kwargs is not None else dict()
527            )
528            self.__ch_graph__ = CHGraph(
529                graph=self.graph, heuristic_fn=heuristic_fn, **ch_graph_kwargs
530            )
531
532    def contraction_hierarchy(
533        self, origin_id: int, destination_id: int, length_only: bool = False
534    ) -> dict[str, Any]:
535        """
536        Function:
537
538        - Get the shortest path between two nodes using the Contraction Hierarchies (CH) graph
539        - Creates the CH graph if it doesn't exist
540
541        Requires:
542
543        - origin_id: The id of the origin node
544        - destination_id: The id of the destination node
545
546        Optional:
547
548        - length_only: If True, only returns the length of the path (not implemented yet)
549
550        Returns:
551
552        - A dictionary with 'path' and 'length' keys containing the shortest path and its length
553        """
554        # Ensure that the CH graph is created and warmed up
555        self.create_contraction_hierarchy()
556        return self.__ch_graph__.search(origin_id, destination_id)
557
558
559class Graph(GraphUtils, GraphModifiers, GraphTrees, GraphAlgorithms):
560    def __init__(self, graph: list[dict[int, int | float]], validate=False):
561        """
562        Function:
563
564        - Initialize a Graph object
565        - Validate the input graph
566
567        Required Arguments:
568
569        - `graph`:
570            - Type: list of dictionaries with integer keys and integer or float values
571            - What: A list of dictionaries where the indicies are origin node ids and the values are dictionaries of destination node indices and graph weights
572            - Note: All nodes must be included as origins in the graph regardless of if they have any connected destinations
573            - EG:
574            ```
575                [
576                    # From London (index 0)
577                    {
578                        # To Paris (index 1)
579                        1: 311,
580                    },
581                    # From Paris (index 1)
582                    {
583                        # To London (index 0)
584                        0: 311,
585                        # To Berlin (index 2)
586                        2: 878,
587                        # To Rome (index 3)
588                        3: 1439,
589                        # To Madrid (index 4)
590                        4: 1053
591                    },
592                    # From Berlin (index 2)
593                    {
594                        # To Paris (index 1)
595                        1: 878,
596                        # To Rome (index 3)
597                        3: 1181,
598                    },
599                    # From Rome (index 3)
600                    {
601                        # To Paris (index 1)
602                        1: 1439,
603                        # To Berlin (index 2)
604                        2: 1181,
605                    },
606                    # From Madrid (index 4)
607                    {
608                        # To Paris (index 1)
609                        1: 1053,
610                        # To Lisbon (index 5)
611                        5: 623
612                    },
613                    # From Lisbon (index 5)
614                    {
615                        # To Madrid (index 4)
616                        4: 623
617                    }
618                ]
619            ```
620
621        Optional Arguments:
622
623        - `validate`:
624            - Type: bool
625            - What: Whether to validate the input graph upon initialization
626            - Default: False
627        """
628        self.graph = graph
629        self.reset_cache()
630        if validate:
631            self.validate()