computation time of distances() significantly increases with edge weights?!

Usage
,
1

Hi,

I am new to igraph and this forum. So, hopefully, this is the right place to report or clarify my issue. I use igraph with R but as it is likely related to the underlying C code, I tagged it with R and C.

In order to calculate the maximum distance of vertices to the root(s) of a graph, I apply igraph::distances() and an edge weight of -1. The computation time more than doubles compared to distances without any weight. For me, such a difference is quite surprising but may be there is an explanation. There is no difference between weight=-1 and weight=1.

Thanks,
Andreas

Example code (note: in this case the output should not depend on the weight)

# dag with 10000 edges
kk <- data.frame(from=seq(10000))
kk$to <- kk$from+1
g <- igraph::graph_from_data_frame(kk)
inlets <- igraph::degree(g, mode="in")
inlets <- inlets[inlets==0]
g.1 <- igraph::set.edge.attribute(g, name="weight", value=-1)
# only for comparison: the weight value has no impact
g.2 <- igraph::set.edge.attribute(g, name="weight", value=1)
# without weight, make sure we use the same algorithm
# note: I do not use the algorithm argument
microbenchmark::microbenchmark({mm <- igraph::distances(g, mode="in", to=names(inlets), algorithm="bellman-ford")}, times=3)
microbenchmark::microbenchmark({mm <- -igraph::distances(g.1, mode="in", to=names(inlets), algorithm="bellman-ford")}, times=3)
microbenchmark::microbenchmark({mm <- igraph::distances(g.2, mode="in", to=names(inlets), algorithm="bellman-ford")}, times=3)
# next steps
# mm[is.infinite(mm)] <- -1
# res <- apply(mm, 1, max)
2

I think when you don’t have negative edges, the work is passed on to Dijkstra’s algorithm, because it’s faster.

1 Like
3

This is expected. Different algorithms are used for:

  1. The unweighted case (simple breadth-first search).
  2. Weighted graph with non-negative weights (Dijkstra’s algorithm).
  3. Weighted graph with some negative weights (Bellman–Ford algorithm).

This is true even if you set the algorithm parameter.

(1) will be faster (has better complexity) than (2) or (3). You can look up the complexities of these algorithms in the C/igraph documentation.

1 Like
4

Thanks for the explanation and pointing to the doucmentation and the complexities!