scgraph.cache
1from scgraph.spanning import SpanningTree 2from scgraph.graph import Graph 3 4 5class CacheGraph: 6 """ 7 A class allowing a graph to cache spanning trees to quickly compute shortest paths between nodes. 8 This is useful for speeding up the computation of shortest when origins or destinations are often the same. 9 """ 10 11 def __init__(self, graph: list[dict], validate_graph: bool = False): 12 """ 13 Initialize the CacheGraph with a graph. 14 15 Requires: 16 17 - graph: 18 - Type: list of dictionaries 19 - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph 20 - Note: The graph must be symmetric for the CacheGraph to work based on how it takes advantage of spanning trees. 21 22 Optional: 23 24 - validate_graph: 25 - Type: bool 26 - What: If True, validates the graph before caching 27 - Default: False 28 - Note: This is useful to ensure the graph is valid before caching, but can be skipped for performance reasons if you are sure the graph is valid. 29 30 - Note: Take care when caching spanning trees to avoid memory issues. It is recommend to only cache for nodes that will be used often. 31 """ 32 if validate_graph: 33 Graph.validate_graph( 34 graph, check_connected=False, check_symmetry=True 35 ) 36 self.graph = graph 37 self.cache = [0] * len(graph) 38 39 def get_shortest_path( 40 self, 41 origin_id: int, 42 destination_id: int, 43 length_only: bool = False, 44 ): 45 """ 46 Function: 47 48 - Get the shortest path between two nodes in the graph attempting to use a cached spanning tree if available 49 - If a cached spanning tree is not available, it will compute the spanning tree and cache it for future use if specified by `cache` 50 51 Requires: 52 53 - origin_id: The id of the origin node 54 - destination_id: The id of the destination node 55 56 Optional: 57 58 - length_only: If True, only returns the length of the path 59 """ 60 spanning_tree = self.cache[origin_id] 61 if spanning_tree == 0: 62 spanning_tree = SpanningTree.makowskis_spanning_tree( 63 graph=self.graph, node_id=origin_id 64 ) 65 self.cache[origin_id] = spanning_tree 66 return SpanningTree.get_path( 67 origin_id=origin_id, 68 destination_id=destination_id, 69 spanning_tree=spanning_tree, 70 length_only=length_only, 71 )
class
CacheGraph:
6class CacheGraph: 7 """ 8 A class allowing a graph to cache spanning trees to quickly compute shortest paths between nodes. 9 This is useful for speeding up the computation of shortest when origins or destinations are often the same. 10 """ 11 12 def __init__(self, graph: list[dict], validate_graph: bool = False): 13 """ 14 Initialize the CacheGraph with a graph. 15 16 Requires: 17 18 - graph: 19 - Type: list of dictionaries 20 - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph 21 - Note: The graph must be symmetric for the CacheGraph to work based on how it takes advantage of spanning trees. 22 23 Optional: 24 25 - validate_graph: 26 - Type: bool 27 - What: If True, validates the graph before caching 28 - Default: False 29 - Note: This is useful to ensure the graph is valid before caching, but can be skipped for performance reasons if you are sure the graph is valid. 30 31 - Note: Take care when caching spanning trees to avoid memory issues. It is recommend to only cache for nodes that will be used often. 32 """ 33 if validate_graph: 34 Graph.validate_graph( 35 graph, check_connected=False, check_symmetry=True 36 ) 37 self.graph = graph 38 self.cache = [0] * len(graph) 39 40 def get_shortest_path( 41 self, 42 origin_id: int, 43 destination_id: int, 44 length_only: bool = False, 45 ): 46 """ 47 Function: 48 49 - Get the shortest path between two nodes in the graph attempting to use a cached spanning tree if available 50 - If a cached spanning tree is not available, it will compute the spanning tree and cache it for future use if specified by `cache` 51 52 Requires: 53 54 - origin_id: The id of the origin node 55 - destination_id: The id of the destination node 56 57 Optional: 58 59 - length_only: If True, only returns the length of the path 60 """ 61 spanning_tree = self.cache[origin_id] 62 if spanning_tree == 0: 63 spanning_tree = SpanningTree.makowskis_spanning_tree( 64 graph=self.graph, node_id=origin_id 65 ) 66 self.cache[origin_id] = spanning_tree 67 return SpanningTree.get_path( 68 origin_id=origin_id, 69 destination_id=destination_id, 70 spanning_tree=spanning_tree, 71 length_only=length_only, 72 )
A class allowing a graph to cache spanning trees to quickly compute shortest paths between nodes. This is useful for speeding up the computation of shortest when origins or destinations are often the same.
CacheGraph(graph: list[dict], validate_graph: bool = False)
12 def __init__(self, graph: list[dict], validate_graph: bool = False): 13 """ 14 Initialize the CacheGraph with a graph. 15 16 Requires: 17 18 - graph: 19 - Type: list of dictionaries 20 - See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph 21 - Note: The graph must be symmetric for the CacheGraph to work based on how it takes advantage of spanning trees. 22 23 Optional: 24 25 - validate_graph: 26 - Type: bool 27 - What: If True, validates the graph before caching 28 - Default: False 29 - Note: This is useful to ensure the graph is valid before caching, but can be skipped for performance reasons if you are sure the graph is valid. 30 31 - Note: Take care when caching spanning trees to avoid memory issues. It is recommend to only cache for nodes that will be used often. 32 """ 33 if validate_graph: 34 Graph.validate_graph( 35 graph, check_connected=False, check_symmetry=True 36 ) 37 self.graph = graph 38 self.cache = [0] * len(graph)
Initialize the CacheGraph with a graph.
Requires:
- graph:
- Type: list of dictionaries
- See: https://connor-makowski.github.io/scgraph/scgraph/graph.html#Graph.validate_graph
- Note: The graph must be symmetric for the CacheGraph to work based on how it takes advantage of spanning trees.
Optional:
validate_graph:
- Type: bool
- What: If True, validates the graph before caching
- Default: False
- Note: This is useful to ensure the graph is valid before caching, but can be skipped for performance reasons if you are sure the graph is valid.
Note: Take care when caching spanning trees to avoid memory issues. It is recommend to only cache for nodes that will be used often.
def
get_shortest_path(self, origin_id: int, destination_id: int, length_only: bool = False):
40 def get_shortest_path( 41 self, 42 origin_id: int, 43 destination_id: int, 44 length_only: bool = False, 45 ): 46 """ 47 Function: 48 49 - Get the shortest path between two nodes in the graph attempting to use a cached spanning tree if available 50 - If a cached spanning tree is not available, it will compute the spanning tree and cache it for future use if specified by `cache` 51 52 Requires: 53 54 - origin_id: The id of the origin node 55 - destination_id: The id of the destination node 56 57 Optional: 58 59 - length_only: If True, only returns the length of the path 60 """ 61 spanning_tree = self.cache[origin_id] 62 if spanning_tree == 0: 63 spanning_tree = SpanningTree.makowskis_spanning_tree( 64 graph=self.graph, node_id=origin_id 65 ) 66 self.cache[origin_id] = spanning_tree 67 return SpanningTree.get_path( 68 origin_id=origin_id, 69 destination_id=destination_id, 70 spanning_tree=spanning_tree, 71 length_only=length_only, 72 )
Function:
- Get the shortest path between two nodes in the graph attempting to use a cached spanning tree if available
- If a cached spanning tree is not available, it will compute the spanning tree and cache it for future use if specified by
cache
Requires:
- origin_id: The id of the origin node
- destination_id: The id of the destination node
Optional:
- length_only: If True, only returns the length of the path