This function constructs a graph in C++ and uses Yen's Algorithm to find shortest paths through the graph, starting and ending at specified nodes.
k_shortest_paths(graph_df, from, to, k = 1, col_from = 1, col_to = 2, col_weights = "weight", edge_penalty = 0, verbose = getOption("yenpathy.verbose", FALSE))
| graph_df | A data frame representing the graph's edges, with columns, in order, for start node, end node, and weight or cost. May also be an iGraph or tidygraph object. |
|---|---|
| from | The number or name of the starting vertex. |
| to | The number or name of the ending vertex. |
| k | The maximum number of paths to find, default 1. |
| col_from, col_to, col_weights | columns of the the start node, end node, and weight of edges in `graph_df`. May be integer or character. |
| edge_penalty | A constant to be added to each edge, if you wish to penalize routes with many edges. |
| verbose | Be more verbose. |
A list of vectors representing paths through the network, ordered from shortest to longest.
Your graph's nodes can be integers or characters. If they're character vectors, the function creates an integer version behind the scenes, but gives you back a list of character vectors paths.
my_graph <- data.frame(source = c(1, 4, 5, 1, 1, 8, 1, 2, 7, 3), sink = c(4, 5, 6, 6, 8, 6, 2, 7, 3, 6), weight = c(1, 1, 1.5, 5, 1.5, 2.5, 1.5, 0.5, 0.5, 0.5)) k_shortest_paths(graph_df = my_graph, from = 1, to = 6, k = 4)#> [[1]] #> [1] 1 2 7 3 6 #> #> [[2]] #> [1] 1 4 5 6 #> #> [[3]] #> [1] 1 8 6 #> #> [[4]] #> [1] 1 6 #>k_shortest_paths(graph_df = my_graph, from = 1, to = 6, k = 4, edge_penalty = 2)#> [[1]] #> [1] 1 6 #> #> [[2]] #> [1] 1 8 6 #> #> [[3]] #> [1] 1 4 5 6 #> #> [[4]] #> [1] 1 2 7 3 6 #>