Use Cases

All use cases for the DJK package share some required preparation. The general workflow is:

  1. Initialize a graph.
  2. Enable caching.
  3. Set edge weights.
  4. Perform the necessary computations.
  5. 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:

  1. prg_djk_graph_init() — Initialize a graph for use with the DJK algorithms.

  2. 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.

  3. prg_djk_edge_weight_set() — Set edge weights used for shortest-path (least-cost) computations. (The default weight for each edge is 1.)

  4. (Optional) See Utility Functions and Options for additional options and callback functions.

  5. (Optional) Define edge and node acceptability filters; define and register the consider_proc callback 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_proc callback, 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_proc disables 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.

  6. Use case-specific steps, as given in the following sections: Single Paths, Routing Tables, and Multipaths and Topology Planning.

  7. prg_djk_graph_init() can be used after these calls also, to free up any cached route state information.