Feature request: make Bellman-Ford & Johnson algorithms available for shortest_path()

[jfb-h]

Following up on this post, I would like to make a feature request for the Bellman-Ford and Johnson algorithms to be added as an option for the shortest_path() and all_shortest_paths() functions.

This would allow for the identification of longest (critical) paths by negating positive edge weights.

Thanks a lot for the hard work and the amazing package, Jakob

[clpippel]

This seems to work:

library("igraph")
sessionInfo()

other attached packages: [1] igraph_1.2.4.1

loaded via a namespace (and not attached): [1] compiler_3.6.1 magrittr_1.5 pkgconfig_2.0.3

g <- make_tree(7)
g

IGRAPH 3e34400 D-W- 7 6 -- Tree attr: name (g/c), children (g/n), mode (g/c), weight (e/n) edges from 3e34400: [1] 1->2 1->3 2->4 2->5 3->6 3->7

lyt <- layout.sugiyama(g, hgap = 1, vgap = 1)       # create layout and plot
plot(g, layout=lyt$layout, main = "Tree with Sugiyama Layout")

E(g)$weight <- -1                                   # longest path = shortest negative, no neg. cycles
dis <- (-shortest.paths(g, v=(V(g)), mode="out"))   # matrix of VxV distances
layers <- apply(dis, 1, max)                        # max per row
print(layers)

[1] 2 1 1 0 0 0 0

lyt$layout[,2] <- layers[] + 1
dev.new()
plot(g, layout=lyt$layout, main = "Tree with Sugiyama Layout (2)")
g[]

[jfb-h]

Interesting, I think I was using shortest_paths() , like so:

g <- make_tree(7)
E(g)$weight <- -c(1,2,1,3,2,1)
dis <- shortest_paths(g, from=1, to=c(4,5,6,7), mode="out")

which throws an error:

Error in shortest_paths(g, from = 1, to = c(4, 5, 6, 7), mode = "out") : 
  At structural_properties.c:4521 : Weight vector must be non-negative, Invalid value

[clpippel]

shortest_paths(g, from=1, to=c(4,5,6,7), mode="out") does not work

but

shortest.paths(g, 1, to=c(4,5,6,7), mode="out") gives:

      [,1] [,2] [,3] [,4]
 [1,]   -2   -4   -4   -3

[clpippel]

shortest.paths and shortest_paths are different.

> shortest.paths
function (graph, v = V(graph), to = V(graph), mode = c("all", 
    "out", "in"), weights = NULL, algorithm = c("automatic", 
    "unweighted", "dijkstra", "bellman-ford", 
    "johnson")) 
{...}

> shortest_paths
function (graph, from, to = V(graph), mode = c("out", "all", 
    "in"), weights = NULL, output = c("vpath", "epath", 
    "both"), predecessors = FALSE, inbound.edges = FALSE) 
{...}

So, shortest.paths supports bellman-ford, but shortes_path does not.

[jfb-h]

shortest.paths() seems to be the same as distances() as it doesn't actually return the paths such as shortest_paths() does but the distances of the shortest paths. This is also basically what my original post was about: distances() seems to have access to the algorithms necessary for handling negative edge weights (and they are available in the c API) while shortest_paths() and all_shortest_paths() do not.

[clpippel]

@jbf-h, I think you are right. I mislead myself by thinking shortest_paths and shortest.paths are supposed to be identical.

[jfb-h]

Well I think that’s a reasonable expectation :) I could imagine that shortest.paths() is a relict of some refactoring of the code base for shortest paths as it seems that many functions were renamed from the classical R naming convention using the . as a separator to the more modern _ propagated by the tidyverse.

[ntamas]

Okay, I took a look at this and it is a mess.

Indeed, shortest.paths() was deprecated a while ago and it was renamed to distances(). At the same time, get.shortest.paths() was renamed to shortest_paths(). This can be tracked in R/zzz-deprecate.R. The deprecations all happened in 2014 so I guess it's been a while now and it would be time to start removing the old functions, but as no deprecation warning was given so far, I cannot do it for 1.3.0. But this is unrelated to the original issue anyway.

As for the original issue:

• it seems like distances() (which used to be shortest.paths()) supports the Bellman-Ford and Johnson algorithms
• shortest_paths() (which used to be get.shortest.paths()) and all_shortest_paths() (which used to be get.all.shortest.paths()) does not support Bellman-Ford and Johnson
• In the underlying C library, the Johnson algorithm is not implemented for igraph_get_shortest_paths() and igraph_get_all_shortest_paths(), but the Bellman-Ford algorithm is implemented

So, what we can do for 1.3.0 is to expose Bellman-Ford for shortest_paths() and all_shortest_paths().

[ntamas]

Correction: igraph_get_all_shortest_paths() does not support Bellman-Ford either, so I simply extended shortest_paths() to support the Bellman-Ford algorithm. This is now done in https://github.com/igraph/rigraph/commit/e938189a87cb1928311cfac39b2a7fc3faf2a388