Not all shortest paths returned by get_multi_paths

[adamsardar]

I've noticed some surprising behaviour in get_multi_paths:

If I use an undirected graph:

Represented by adjacency matrix:

library(igraph)

demoGraphMat =
  matrix(c(0, 1, 0, 0, 1, 0,
           1, 0, 1, 0, 1, 0,
           0, 1, 0, 1, 0, 0,
           0, 0, 1, 0, 1, 1,
           1, 1, 0, 1, 0, 0,
           0, 0, 0, 1, 0, 0), 
         nrow = 6)

demoGraph =  as.undirected(graph_from_adjacency_matrix(demoGraphMat)) 
V(demoGraph)$name = LETTERS[1:vcount(demoGraph)]

Then get_multi_paths does not return all of the paths between nodes B and F:

library(cppRouting)

edgeList =
  demoGraph |>
    igraph::as_data_frame(what = 'edges') |>
    dplyr::mutate(cost = 1) 

nodes = unique(c(edgeList$from, edgeList$to))

graph = makegraph(edgeList, directed = FALSE)

allPathsList =
  get_multi_paths(Graph=graph, 
                               from=nodes, 
                               to=nodes, 
                               long = FALSE) 

allPathsList$B

$B
$B$A
[1] "A" "B"

$B$B
character(0)

$B$C
[1] "C" "B"

$B$D
[1] "D" "C" "B"

$B$E
[1] "E" "B"

$B$F
[1] "F" "D" "C" "B"

There are two degenerate paths from B to F: one via C, which is reported, and one via E, which is not.

Is this a bug or have I used the tool incorrectly? Or assumed that it should return all paths when it wont?

[vlarmet]

Hi, This function return the shortest path between each combination of an OD matrix, more precisely "one of the shortest paths" if there are several ones. Since all edges have cost 1, BCDF and BEDF equals to 3 so the algorithm return the first it has reached (because C has been popped from the priority queue before E). I agree the function name could be misinterpreted...