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 shortest path 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 shortest path 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 shortest path 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 shortest path tree if available
49        - 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`
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        shortest_path_tree = self.cache[origin_id]
61        if shortest_path_tree == 0:
62            shortest_path_tree = SpanningTree.makowskis_spanning_tree(
63                graph=self.graph, node_id=origin_id
64            )
65            self.cache[origin_id] = shortest_path_tree
66        return SpanningTree.get_path(
67            origin_id=origin_id,
68            destination_id=destination_id,
69            spanning_tree=shortest_path_tree,
70            length_only=length_only,
71        )
class CacheGraph: 
 6class CacheGraph:
 7    """
 8    A class allowing a graph to cache shortest path 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 shortest path 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 shortest path 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 shortest path tree if available
50        - 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`
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        shortest_path_tree = self.cache[origin_id]
62        if shortest_path_tree == 0:
63            shortest_path_tree = SpanningTree.makowskis_spanning_tree(
64                graph=self.graph, node_id=origin_id
65            )
66            self.cache[origin_id] = shortest_path_tree
67        return SpanningTree.get_path(
68            origin_id=origin_id,
69            destination_id=destination_id,
70            spanning_tree=shortest_path_tree,
71            length_only=length_only,
72        )

A class allowing a graph to cache shortest path 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 shortest path 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 shortest path 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:

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 shortest path trees to avoid memory issues. It is recommend to only cache for nodes that will be used often.

graph
cache
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 shortest path tree if available
50        - 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`
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        shortest_path_tree = self.cache[origin_id]
62        if shortest_path_tree == 0:
63            shortest_path_tree = SpanningTree.makowskis_spanning_tree(
64                graph=self.graph, node_id=origin_id
65            )
66            self.cache[origin_id] = shortest_path_tree
67        return SpanningTree.get_path(
68            origin_id=origin_id,
69            destination_id=destination_id,
70            spanning_tree=shortest_path_tree,
71            length_only=length_only,
72        )

Function:

  • Get the shortest path between two nodes in the graph attempting to use a cached shortest path tree if available
  • 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

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