get_shortest_path {rsppfp}

igraph Shortest Path

Description

A original node N_i can appear on a transformed gStar as different N_i* equivalent nodes. Therefore, this becomes a limitation when searching for a shortest path inside gStar. As a result: all N_i* need to be considered as possible destination nodes when looking for the shortest path. This function is a wrapper for this behavior, providing a straightforward implementation using igraph capabilities. However, it aims to provide guidance on how to build a similar algorithm for different path-finding algorithms.

It is important to mention that new nodes are only considered as destination nodes, and they are not search for origin nodes. This is because N* nodes can only be reached after traveling through gStar nodes. For example, a node "f|e|r" is actually indicating that "r" has been reached after traveling through the nodes "f" and "e".

Usage

get_shortest_path(g, origin, dest, weightColName = NULL)

Arguments

g

A gStar digraph in data frame format, translated using one of the available functions. The weight or cost attribute of each arc of the graph must be stored in a specific column named weight.

origin

The name of the starting node from G for the path. It must be written as it appears in G, and it is preferable to use a character format, but this can also be of any simple type. No lists or vectors are allowed.

dest

The name of the destination node from G for the path. It must be written as it appears in G, and it is preferable to use a character format, but this can also be of any simple type. No lists or vectors are allowed.

weightColName

The name of the weight column used in the dataframe. If the column does not exist, a name _must_ be provided so that a new weight column is generated.

Value

The shortest path from origin node to dest node, calculated in G*, to include the forbidden paths. It uses igraph's functionalities.

Examples

# Given a specific gStar graph:
gStar <- data.frame(from = c("u|v", "s|u|v", "s|u", "s", "s", "u", "w", "w", "x", "x", 
                             "v", "v", "y", "y", "s", "s|u", "u", "u|v"),
                    to = c("t", "u|v|y", "w", "w", "x", "w", "v", "y", "w", "y", "y", "t", 
                            "t", "u", "s|u", "s|u|v", "u|v", "u|v|y"), 
                   weight = c(12L, 3L, 5L, 9L, 7L, 5L, 11L, 10L, 1L, 2L, 3L, 12L, 13L, 0L,
                              8L, 4L, 4L, 3L), 
                   stringsAsFactors = FALSE)
gStar

# Obtain the shortest path
get_shortest_path(gStar, "s", "v", "weight")