Construct Path Graphs Across Hop Limits

Find minimum-length routes using at most each requested number of edges. Equal-length routes prefer fewer hops. One route is stored per unordered pair and can be retrieved in either direction with get.shortest.path().

Usage

create.path.graph(graph, h.values, stage = "final")

Arguments

graph

A dgraph with finite nonnegative stored lengths.

h.values

One or more strictly increasing positive integer hop limits. A hop counts one traversed edge. Invalid, duplicate or unordered values error; values are never silently rounded or reordered.

stage

Stored graph stage; defaults to "final".

Value

A named path.graph.series collection, even for one limit. Names are h_2, h_4, etc. Each member is a path.graph with a graph of reachable pairs, stored shortest.paths, and an h attribute recording the requested limit. Its graph stores route lengths and a hops edge attribute. Routes use the input graph's vertex indices. Empty graphs and isolated vertices are preserved.

Details

Hop-constrained search retains a separate distance for each hop count, then selects the best route for each pair. With nonnegative lengths, limits above n - 1 need no additional search. For each source, auxiliary storage is proportional to n * min(h, n - 1); storing routes for all reachable pairs can require cubic space. Use small hop limits when possible.

Examples

graph <- create.graph("chain", n = 5)
paths <- create.path.graph(graph, h.values = c(2, 4))
get.shortest.path(paths[["h_4"]], from = 1, to = 5)
#> $path
#> [1] 1 2 3 4 5
#> 
#> $length
#> [1] 4
#> 
#> $hops
#> [1] 4
#> 
get.shortest.path(paths[["h_4"]], from = 5, to = 1)
#> $path
#> [1] 5 4 3 2 1
#> 
#> $length
#> [1] 4
#> 
#> $hops
#> [1] 4
#> 
compare.paths(paths, from = 1, to = 5)
#>     h path_exists path_length n_hops          path
#> h_2 2       FALSE          NA     NA          NULL
#> h_4 4        TRUE           4      4 1, 2, 3, 4, 5