Single-source shortest paths using Dijkstra's algorithm taking into account contextual constraints. Enforcement of constraints is the task of the given user-defined function.
shortest_path_ctx(g, s, decision_fct)
| g | The graph object |
|---|---|
| s | The source vertex |
| decision_fct | A function enforcing constraints. The signature of the function is ``(vertex index, vertex index, vertex index) -> bool``, i.e. the function expects three vertex IDs for the start, the current, and the next vertex. It must evaluate to ``bool``. Passing the start vertex is unnecessary here. However, the signature is the same as for the other functions for usability reasons. |
A list of vertices describing the shortest path distance to all other nodes in the graph.
The function enforcing contextual constraints is evaluated at each node during shortest path discovery. The function needs to evaluate to ``true`` or ``false`` allowing an edge to be visited or not. As parameters, the function needs to accept the starting node of path traversal, the current node, and the descending node in question. If the function returns False, the descending node is not being visited. Passing the start vertex is unnecessary here. However, the signature is the same as for the other functions for usability reasons.
The three nodes are passed as indices allowing for access of (external) attribute and other associated information.
Note that the decision function is evaluated more than once during path traversal. That means, there should not happen any resource-intense computation inside this function. Also, it does not allow to keep track of the status of calculation, e.g. by calculating the visited edges or something similar.
If the decision function simply returns True all the time, the set of shortest paths is the unaltered set of shortest paths expected by the classical Dijkstra-implementation.
library(RUnit) suppressMessages(library(igraph)) suppressMessages(library(nctx)) file <- system.file("extdata", "bcde.directed.graphml", package="nctx") g_i <- read_graph(file, "graphml") start <- 4 dists <- distances(g_i,start,mode="out",weights=NA) g <- copy_from_igraph(g_i) checker <- function(start, cur, nxt){ TRUE } dists_unaltered <- nctx::shortest_path_ctx(g, start,checker) checkEquals(dists_unaltered, as.numeric(dists))#> [1] TRUE