scgraph.graph

  1from heapq import heappop, heappush
  2from scgraph.bmssp import BmsspSolver
  3
  4
  5class Graph:
  6    @staticmethod
  7    def validate_graph(
  8        graph: list[dict[int, int | float]],
  9        check_symmetry: bool = True,
 10        check_connected: bool = True,
 11    ) -> None:
 12        """
 13        Function:
 14
 15        - Validate that a graph is properly formatted
 16
 17        Required Arguments:
 18
 19        - `graph`:
 20            - Type: list of dictionaries with integer keys and integer or float values
 21            - What: A list of dictionaries where the indicies are origin node ids and the values are dictionaries of destination node indices and graph weights
 22            - Note: All nodes must be included as origins in the graph regardless of if they have any connected destinations
 23            - EG:
 24            ```
 25                [
 26                    # From London (index 0)
 27                    {
 28                        # To Paris (index 1)
 29                        1: 311,
 30                    },
 31                    # From Paris (index 1)
 32                    {
 33                        # To London (index 0)
 34                        0: 311,
 35                        # To Berlin (index 2)
 36                        2: 878,
 37                        # To Rome (index 3)
 38                        3: 1439,
 39                        # To Madrid (index 4)
 40                        4: 1053
 41                    },
 42                    # From Berlin (index 2)
 43                    {
 44                        # To Paris (index 1)
 45                        1: 878,
 46                        # To Rome (index 3)
 47                        3: 1181,
 48                    },
 49                    # From Rome (index 3)
 50                    {
 51                        # To Paris (index 1)
 52                        1: 1439,
 53                        # To Berlin (index 2)
 54                        2: 1181,
 55                    },
 56                    # From Madrid (index 4)
 57                    {
 58                        # To Paris (index 1)
 59                        1: 1053,
 60                        # To Lisbon (index 5)
 61                        5: 623
 62                    },
 63                    # From Lisbon (index 5)
 64                    {
 65                        # To Madrid (index 4)
 66                        4: 623
 67                    }
 68                ]
 69            ```
 70
 71        Optional Arguments:
 72
 73        - `check_symmetry`
 74            - Type: bool
 75            - What: Whether to check that the graph is symmetric
 76            - Default: True
 77            - Note: This is forced to True if `check_connected` is True
 78        - `check_connected`
 79            - Type: bool
 80            - What: Whether to check that the graph is fully connected
 81            - Default: True
 82            - Note: For computational efficiency, only symmetric graphs are checked for connectivity
 83            - Note: If this is True, `check_symmetry` is forced to True and the graph will be checked for symmetry prior to checking for connectivity
 84        """
 85        check_symmetry = check_symmetry or check_connected
 86        assert isinstance(graph, list), "Your graph must be a list"
 87        len_graph = len(graph)
 88        for origin_id, origin_dict in enumerate(graph):
 89            assert isinstance(
 90                origin_dict, dict
 91            ), f"Your graph must be a list of dictionaries but the value for origin {origin_id} is not a dictionary"
 92            destinations = list(origin_dict.keys())
 93            lengths = list(origin_dict.values())
 94            assert all(
 95                [
 96                    (isinstance(i, int) and i >= 0 and i < len_graph)
 97                    for i in destinations
 98                ]
 99            ), 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"
100            assert all(
101                [(isinstance(i, (int, float)) and i >= 0) for i in lengths]
102            ), f"Distances must be integers or floats, but graph[{origin_id}] contains a non-integer or non-float distance"
103            if check_symmetry:
104                for destination_id, distance in origin_dict.items():
105                    assert (
106                        graph[destination_id].get(origin_id) == distance
107                    ), 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)}"
108        if check_connected:
109            assert Graph.validate_connected(
110                graph
111            ), "Your graph is not fully connected"
112
113    @staticmethod
114    def validate_connected(
115        graph: list[dict[int, int | float]], origin_id: int = 0
116    ) -> bool:
117        """
118        Function:
119
120        - Validate that a graph is fully connected
121            - This means that every node in the graph has a path to every other node in the graph
122            - Note: This assumes that the graph is symmetric
123        - Return True if the graph is fully connected and False if it is not
124
125        Required Arguments:
126
127        - `graph`:
128            - Type: list of dictionaries
129            - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
130
131        Optional Arguments:
132
133        - `origin_id`
134            - Type: int
135            - What: The id of the origin node from which to start the connectivity check
136            - Default: 0
137        """
138        visited = [0] * len(graph)
139        open_leaves = [origin_id]
140
141        while open_leaves:
142            current_id = open_leaves.pop()
143            visited[current_id] = 1
144            for connected_id, connected_distance in graph[current_id].items():
145                if visited[connected_id] == 0:
146                    open_leaves.append(connected_id)
147        return min(visited) == 1
148
149    @staticmethod
150    def input_check(
151        graph: list[dict[int, int | float]], origin_id: int, destination_id: int
152    ) -> None:
153        """
154        Function:
155
156        - Check that the inputs passed to the shortest path algorithm are valid
157        - Raises an exception if the inputs passed are not valid
158
159        Required Arguments:
160
161        - `graph`:
162            - Type: list of dictionaries
163            - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
164        - `origin_id`
165            - Type: int
166            - What: The id of the origin node from the graph dictionary to start the shortest path from
167        - `destination_id`
168            - Type: int
169            - What: The id of the destination node from the graph dictionary to end the shortest path at
170
171        Optional Arguments:
172
173        - None
174        """
175        if (
176            not isinstance(origin_id, int)
177            and origin_id < len(graph)
178            and origin_id >= 0
179        ):
180            raise Exception(f"Origin node ({origin_id}) is not in the graph")
181        if (
182            not isinstance(destination_id, int)
183            and origin_id < len(graph)
184            and origin_id >= 0
185        ):
186            raise Exception(
187                f"Destination node ({destination_id}) is not in the graph"
188            )
189
190    @staticmethod
191    def reconstruct_path(
192        destination_id: int, predecessor: list[int]
193    ) -> list[int]:
194        """
195        Function:
196
197        - Reconstruct the shortest path from the destination node to the origin node
198        - Return the reconstructed path in the correct order
199        - Given the predecessor list, this function reconstructs the path
200
201        Required Arguments:
202
203        - `destination_id`
204            - Type: int
205            - What: The id of the destination node from the graph dictionary to end the shortest path at
206        - `predecessor`
207            - Type: list[int]
208            - What: The predecessor list that was used to compute the shortest path
209            - This list is used to reconstruct the path from the destination node to the origin node
210            - Note: Nodes with no predecessor should be -1
211
212        Optional Arguments:
213
214        - None
215        """
216        output_path = [destination_id]
217        while predecessor[destination_id] != -1:
218            destination_id = predecessor[destination_id]
219            output_path.append(destination_id)
220        output_path.reverse()
221        return output_path
222
223    @staticmethod
224    def dijkstra(
225        graph: list[dict[int, int | float]], origin_id: int, destination_id: int
226    ) -> dict:
227        """
228        Function:
229
230        - Identify the shortest path between two nodes in a sparse network graph using a modified dijkstra algorithm
231            - Modifications allow for a sparse distance matrix to be used instead of a dense distance matrix
232            - This can dramatically reduce the memory and compute requirements of the algorithm
233            - This algorithm should run in O(n^2) time where n is the number of nodes in the graph
234        - Return a dictionary of various path information including:
235            - `id_path`: A list of node ids in the order they are visited
236            - `path`: A list of node dictionaries (lat + long) in the order they are visited
237
238        Required Arguments:
239
240        - `graph`:
241            - Type: list of dictionaries
242            - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
243        - `origin_id`
244            - Type: int
245            - What: The id of the origin node from the graph dictionary to start the shortest path from
246        - `destination_id`
247            - Type: int
248            - What: The id of the destination node from the graph dictionary to end the shortest path at
249
250        Optional Arguments:
251
252        - None
253        """
254        Graph.input_check(
255            graph=graph, origin_id=origin_id, destination_id=destination_id
256        )
257        distance_matrix = [float("inf")] * len(graph)
258        branch_tip_distances = [float("inf")] * len(graph)
259        predecessor = [-1] * len(graph)
260
261        distance_matrix[origin_id] = 0
262        branch_tip_distances[origin_id] = 0
263
264        while True:
265            current_distance = min(branch_tip_distances)
266            if current_distance == float("inf"):
267                raise Exception(
268                    "Something went wrong, the origin and destination nodes are not connected."
269                )
270            current_id = branch_tip_distances.index(current_distance)
271            branch_tip_distances[current_id] = float("inf")
272            if current_id == destination_id:
273                break
274            for connected_id, connected_distance in graph[current_id].items():
275                possible_distance = current_distance + connected_distance
276                if possible_distance < distance_matrix[connected_id]:
277                    distance_matrix[connected_id] = possible_distance
278                    predecessor[connected_id] = current_id
279                    branch_tip_distances[connected_id] = possible_distance
280
281        return {
282            "path": Graph.reconstruct_path(destination_id, predecessor),
283            "length": distance_matrix[destination_id],
284        }
285
286    @staticmethod
287    def dijkstra_makowski(
288        graph: list[dict[int, int | float]], origin_id: int, destination_id: int
289    ) -> dict:
290        """
291        Function:
292
293        - Identify the shortest path between two nodes in a sparse network graph using a modified Dijkstra algorithm
294            - Modifications allow for a sparse distance matrix to be used instead of a dense distance matrix
295            - Improvements include only computing future potential nodes based on the open leaves for each branch
296                - Open leaves are nodes that have not been visited yet but are adjacent to other visited nodes
297            - This can dramatically reduce the memory and compute requirements of the algorithm
298            - This algorithm should run close to O((n+m) log n) time
299                - Where n is the number of nodes in the graph and m is the number of edges in the graph
300        - Return a dictionary of various path information including:
301            - `id_path`: A list of node ids in the order they are visited
302            - `path`: A list of node dictionaries (lat + long) in the order they are visited
303
304        Required Arguments:
305
306        - `graph`:
307            - Type: list of dictionaries
308            - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
309        - `origin_id`
310            - Type: int
311            - What: The id of the origin node from the graph dictionary to start the shortest path from
312        - `destination_id`
313            - Type: int
314            - What: The id of the destination node from the graph dictionary to end the shortest path at
315
316        Optional Arguments:
317
318        - None
319        """
320        # Input Validation
321        Graph.input_check(
322            graph=graph, origin_id=origin_id, destination_id=destination_id
323        )
324        # Variable Initialization
325        distance_matrix = [float("inf")] * len(graph)
326        distance_matrix[origin_id] = 0
327        open_leaves = []
328        heappush(open_leaves, (0, origin_id))
329        predecessor = [-1] * len(graph)
330
331        while open_leaves:
332            current_distance, current_id = heappop(open_leaves)
333            if current_id == destination_id:
334                break
335            # Technically, the next line is not necessary but can help with performance
336            if current_distance == distance_matrix[current_id]:
337                for connected_id, connected_distance in graph[
338                    current_id
339                ].items():
340                    possible_distance = current_distance + connected_distance
341                    if possible_distance < distance_matrix[connected_id]:
342                        distance_matrix[connected_id] = possible_distance
343                        predecessor[connected_id] = current_id
344                        heappush(open_leaves, (possible_distance, connected_id))
345        if current_id != destination_id:
346            raise Exception(
347                "Something went wrong, the origin and destination nodes are not connected."
348            )
349
350        return {
351            "path": Graph.reconstruct_path(destination_id, predecessor),
352            "length": distance_matrix[destination_id],
353        }
354
355    @staticmethod
356    def cycle_check(predecessor_matrix, node_id):
357        """
358        Function:
359
360        - Check if a cycle exists in the predecessor matrix starting from the given node_id
361        - Returns None if no cycle is detected
362        - Raises an Exception if a cycle is detected
363
364        Required Arguments:
365
366        - `predecessor_matrix`:
367            - Type: list[int]
368            - What: A list where the index represents the node id and the value at that index is the predecessor node id
369        - `node_id`:
370            - Type: int
371            - What: The node id to start checking for cycles from
372
373        Optional Arguments:
374
375        - None
376        """
377        cycle_id = node_id
378        while True:
379            cycle_id = predecessor_matrix[cycle_id]
380            if cycle_id == -1:
381                return
382            if cycle_id == node_id:
383                raise Exception(
384                    f"Cycle detected in the graph at node {node_id}"
385                )
386
387    @staticmethod
388    def dijkstra_negative(
389        graph: list[dict[int, int | float]],
390        origin_id: int,
391        destination_id: int,
392        cycle_check_iterations: int | None = None,
393    ) -> dict:
394        """
395        Function:
396
397        - Identify the shortest path between two nodes in a sparse network graph using a modified Dijkstra algorithm that catches negative cycles
398            - Negative cycles raise an exception if they are detected
399        - Note: This algorithm is guaranteed to find the shortest path or raise an exception if a negative cycle is detected
400        - Note: This algorithm requires computing the entire spanning tree of the graph and is therefore not able to be terminated early
401            - For non negative weighted graphs, it is recommended to use the `dijkstra_makowski` algorithm instead
402        - Note: For certain graphs with weights that are negative, this algorithm may run far slower than O((n+m) log n)
403
404        - Return a dictionary of various path information including:
405            - `id_path`: A list of node ids in the order they are visited
406            - `path`: A list of node dictionaries (lat + long) in the order they are visited
407
408        Required Arguments:
409
410        - `graph`:
411            - Type: list of dictionaries
412            - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
413        - `origin_id`
414            - Type: int
415            - What: The id of the origin node from the graph dictionary to start the shortest path from
416        - `destination_id`
417            - Type: int
418            - What: The id of the destination node from the graph dictionary to end the shortest path at
419
420        Optional Arguments:
421
422        - `cycle_check_iterations`
423            - Type: int | None
424            - Default: None -> The length of the graph is used as the default number of iterations to loop over before checking for negative cycles
425            - What: The number of iterations to loop over before checking for negative cycles
426        """
427        # Input Validation
428        Graph.input_check(
429            graph=graph, origin_id=origin_id, destination_id=destination_id
430        )
431        # Variable Initialization
432        distance_matrix = [float("inf")] * len(graph)
433        distance_matrix[origin_id] = 0
434        open_leaves = []
435        heappush(open_leaves, (0, origin_id))
436        predecessor = [-1] * len(graph)
437
438        # Cycle iteration Variables
439        cycle_iteration = 0
440        if cycle_check_iterations is None:
441            cycle_check_iterations = len(graph)
442
443        while open_leaves:
444            current_distance, current_id = heappop(open_leaves)
445            if current_distance == distance_matrix[current_id]:
446                # Increment the cycle iteration counter and check for negative cycles if the iteration limit is reached
447                cycle_iteration += 1
448                if cycle_iteration >= cycle_check_iterations:
449                    cycle_iteration = 0  # Reset the cycle iteration counter
450                    Graph.cycle_check(
451                        predecessor_matrix=predecessor, node_id=current_id
452                    )
453                for connected_id, connected_distance in graph[
454                    current_id
455                ].items():
456                    possible_distance = current_distance + connected_distance
457                    if possible_distance < distance_matrix[connected_id]:
458                        distance_matrix[connected_id] = possible_distance
459                        predecessor[connected_id] = current_id
460                        heappush(open_leaves, (possible_distance, connected_id))
461
462        if distance_matrix[destination_id] == float("inf"):
463            raise Exception(
464                "Something went wrong, the origin and destination nodes are not connected."
465            )
466
467        return {
468            "path": Graph.reconstruct_path(destination_id, predecessor),
469            "length": distance_matrix[destination_id],
470        }
471
472    @staticmethod
473    def a_star(
474        graph: list[dict[int, int | float]],
475        origin_id: int,
476        destination_id: int,
477        heuristic_fn: callable = None,
478    ) -> dict:
479        """
480        Function:
481
482        - Identify the shortest path between two nodes in a sparse network graph using an A* extension of Makowski's modified Dijkstra algorithm
483        - Return a dictionary of various path information including:
484            - `id_path`: A list of node ids in the order they are visited
485            - `path`: A list of node dictionaries (lat + long) in the order they are visited
486
487        Required Arguments:
488
489        - `graph`:
490            - Type: list of dictionaries
491            - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
492        - `origin_id`
493            - Type: int
494            - What: The id of the origin node from the graph dictionary to start the shortest path from
495        - `destination_id`
496            - Type: int
497            - What: The id of the destination node from the graph dictionary to end the shortest path at
498        - `heuristic_fn`
499            - Type: function
500            - What: A heuristic function that takes two node ids and returns an estimated distance between them
501            - Note: If None, returns the shortest path using Makowski's modified Dijkstra algorithm
502            - Default: None
503
504        Optional Arguments:
505
506        - None
507        """
508        if heuristic_fn is None:
509            return Graph.dijkstra_makowski(
510                graph=graph,
511                origin_id=origin_id,
512                destination_id=destination_id,
513            )
514        # Input Validation
515        Graph.input_check(
516            graph=graph, origin_id=origin_id, destination_id=destination_id
517        )
518        # Variable Initialization
519        distance_matrix = [float("inf")] * len(graph)
520        distance_matrix[origin_id] = 0
521        # Using a visited matrix does add a tad bit of overhead but avoids revisiting nodes
522        # and does not require anything extra to be stored in the heap
523        visited = [0] * len(graph)
524        open_leaves = []
525        heappush(open_leaves, (0, origin_id))
526        predecessor = [-1] * len(graph)
527
528        while open_leaves:
529            current_id = heappop(open_leaves)[1]
530            if current_id == destination_id:
531                break
532            if visited[current_id] == 1:
533                continue
534            visited[current_id] = 1
535            current_distance = distance_matrix[current_id]
536            for connected_id, connected_distance in graph[current_id].items():
537                possible_distance = current_distance + connected_distance
538                if possible_distance < distance_matrix[connected_id]:
539                    distance_matrix[connected_id] = possible_distance
540                    predecessor[connected_id] = current_id
541                    heappush(
542                        open_leaves,
543                        (
544                            possible_distance
545                            + heuristic_fn(connected_id, destination_id),
546                            connected_id,
547                        ),
548                    )
549        if current_id != destination_id:
550            raise Exception(
551                "Something went wrong, the origin and destination nodes are not connected."
552            )
553
554        return {
555            "path": Graph.reconstruct_path(destination_id, predecessor),
556            "length": distance_matrix[destination_id],
557        }
558
559    @staticmethod
560    def bellman_ford(
561        graph: list[dict[int, int | float]],
562        origin_id: int,
563        destination_id: int,
564    ) -> dict:
565        """
566        Function:
567
568        - Identify the shortest path between two nodes in a sparse network graph using the Bellman-Ford algorithm
569        - Return a dictionary of various path information including:
570            - `id_path`: A list of node ids in the order they are visited
571            - `path`: A list of node dictionaries (lat + long) in the order they are visited
572
573        Required Arguments:
574
575        - `graph`:
576            - Type: list of dictionaries
577            - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
578        - `origin_id`
579            - Type: int
580            - What: The id of the origin node from the graph dictionary to start the shortest path from
581        - `destination_id`
582            - Type: int
583            - What: The id of the destination node from the graph dictionary to end the shortest path at
584
585        Optional Arguments:
586
587        - None
588        """
589        # Input Validation
590        Graph.input_check(
591            graph=graph, origin_id=origin_id, destination_id=destination_id
592        )
593        # Variable Initialization
594        distance_matrix = [float("inf")] * len(graph)
595        distance_matrix[origin_id] = 0
596        predecessor = [-1] * len(graph)
597
598        len_graph = len(graph)
599        for i in range(len_graph):
600            for current_id in range(len(graph)):
601                current_distance = distance_matrix[current_id]
602                for connected_id, connected_distance in graph[
603                    current_id
604                ].items():
605                    possible_distance = current_distance + connected_distance
606                    if possible_distance < distance_matrix[connected_id]:
607                        distance_matrix[connected_id] = possible_distance
608                        predecessor[connected_id] = current_id
609                        if i == len_graph - 1:
610                            raise Exception(
611                                "Graph contains a negative weight cycle"
612                            )
613        # Check if destination is reachable
614        if distance_matrix[destination_id] == float("inf"):
615            raise Exception(
616                "Something went wrong, the origin and destination nodes are not connected."
617            )
618
619        return {
620            "path": Graph.reconstruct_path(destination_id, predecessor),
621            "length": distance_matrix[destination_id],
622        }
623
624    @staticmethod
625    def bmssp(
626        graph: list[dict[int, int | float]], origin_id: int, destination_id: int
627    ):
628        """
629        Function:
630
631        - A Full BMSSP-style shortest path solver with a Dijkstra finalizer for non-relaxed edges.
632        - Return a dictionary of various path information including:
633            - `id_path`: A list of node ids in the order they are visited
634            - `path`: A list of node dictionaries (lat + long) in the order they are visited
635
636        Required Arguments:
637
638        - `graph`:
639            - Type: list of dictionaries
640            - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
641        - `origin_id`
642            - Type: int
643            - What: The id of the origin node from the graph dictionary to start the shortest path from
644        - `destination_id`
645            - Type: int
646            - What: The id of the destination node from the graph dictionary to end the shortest path at
647        - `heuristic_fn`
648            - Type: function
649            - What: A heuristic function that takes two node ids and returns an estimated distance between them
650            - Note: If None, returns the shortest path using Makowski's modified Dijkstra algorithm
651            - Default: None
652
653        Optional Arguments:
654
655        - None
656        """
657        # Input Validation
658        Graph.input_check(
659            graph=graph, origin_id=origin_id, destination_id=destination_id
660        )
661        # Run the BMSSP Algorithm to relax as many edges as possible.
662        solver = BmsspSolver(graph, origin_id)
663        if solver.distance_matrix[destination_id] == float("inf"):
664            raise Exception(
665                "Something went wrong, the origin and destination nodes are not connected."
666            )
667
668        return {
669            "path": Graph.reconstruct_path(destination_id, solver.predecessor),
670            "length": solver.distance_matrix[destination_id],
671        }