Use Cases
All use cases for the DJK package share some required preparation. The general workflow is:
- Initialize a graph.
- Enable caching.
- Set edge weights.
- Perform the necessary computations.
- Retrieve the computed path or hops.
Use-case specific steps are discussed in later sections. In this document, we assume that you have already built a PrgT_Graph. See Chapter 6 “Graph Package” on page 121 to learn about graph-building.
The following steps are common to all use cases:
-
prg_djk_graph_init() — Initialize a graph for use with the DJK algorithms.
-
prg_djk_graph_cache_enable() — Turn on the caching of the efficient data structure used internally to represent the graph so that each prg_djk_path_get() call does not re-index the graph. When changes are made to the graph (creation or deletion of vertices or edges), the cache must be disabled and then re-enabled.
Note: This graph cache does not include (output) path data, only (input) graph data.
-
prg_djk_edge_weight_set() — Set edge weights used for shortest-path (least-cost) computations. (The default weight for each edge is 1.)
-
(Optional) See Utility Functions and Options for additional options and callback functions.
-
(Optional) Define edge and node acceptability filters; define and register the
consider_proccallback for enforcing constraints that cannot be expressed as edge weights.a) prg_djk_consider_proc_register() — (Dynamic local constraints) Register a function that determines whether an edge is acceptable for use in a shortest-path. It is generally more efficient to “prune” the graph ahead of time by removing or disabling (see prg_djk_edge_disable()) edges that should not be allowed in the shortest path. In other cases, it is better to use the
consider_proccallback, such as when**:**– An edge's acceptability depends on the partial-path cost from the source to that edge.
– An edge's acceptability will vary over the course of several shortest-path calculations. A common case is routing demands that share a resource (such as link bandwidth). When one route is returned by this package, client code records resource consumption; as the next route is being computed, the
consider_procdisables fully-utilized links in just-in-time fashion.b) prg_djk_path_consider_proc_register() — (Dynamic global constraints) Register a function that determines whether a partial path is acceptable. Use this callback when an edge’s acceptability depends on the other hops in the path, not just path cost.
-
Use case-specific steps, as given in the following sections: Single Paths, Routing Tables, and Multipaths and Topology Planning.
-
prg_djk_graph_init() can be used after these calls also, to free up any cached route state information.