How to calculate a maximum-bottleneck path with igraph?

Question

Given a capacity network with a single source and a single sink, how can I calculate the maximum-bottleneck path (also known as the widest path or maximum capacity path problem) using igraph?

I've read (e.g. here or even with pseudocode there) that it is possible with some modifications to Dijkstra’s algorithm, but I do not want to dive into algortihm development but use igraph instead.

Example

library(igraph)
set.seed(21)

nodes = cbind(
'id' = c('Fermenters', 'Methanogens', 'carbs', 'CO2', 'H2', 'other', 'CH4', 'H2O')
)

from <- c('carbs', rep('Fermenters', 3), rep('Methanogens', 2), 'CO2', 'H2')
to <- c('Fermenters', 'other', 'CO2', 'H2', 'CH4', 'H2O', rep('Methanogens', 2))
weight <- sample(1 : 20, 8)

links <- data.frame(from, to, weight, stringsAsFactors = FALSE)


net = graph_from_data_frame(links, vertices = nodes, directed = T)

## Calculate max-bottleneck here !


# # disabled because just vis
# plot(net, edge.width = E(net)$weight)

# require(networkD3)
# require(tidyverse)
# 
# d3net <- igraph_to_networkD3(net, group = rep(1, 8))
# forceNetwork(
#     Links = mutate(d3net$links, weight = E(net)$weight), Nodes = d3net$nodes,
#     Source = 'source', Target = 'target',
#     NodeID = 'name', Group = "group", Value = "weight", 
#     arrows = TRUE, opacity = 1, opacityNoHover = 1
# )

So with respect to the example, how would I calculate the maximum capacity path from carbs to H2O?

Max-Flow solves a related but imho different problem, which is to calculate the largest possible flow between 2 vertices. The problem which I'm interested in is about _finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path._ (copied from wikipedia). — Holger Brandl, Aug 21 '19 at 08:50

score 4 · Answer 1 · answered Aug 23 '19 at 00:17

4

I don't know how efficient this would be, but you could use igraph to find all "simple" paths, then calculate the minimum edge weight of each, then choose the max...

require(tibble)
require(igraph)

nodes = data_frame('id' = c('A', "B", "C", "D"))

links = tribble(
  ~from, ~to, ~weight,
  "A" , "B", 10,
  "B", "C", 10,
  "C", "D", 6,
  "A", "D", 4,
)

net = graph_from_data_frame(links, vertices = nodes, directed = T)

simple_paths <- all_simple_paths(net, "A", "D")

simple_paths[which.max(
    sapply(simple_paths, function(path) {
      min(E(net, path = path)$weight)
    })
)]

# [[1]]
# + 4/4 vertices, named, from 061ab8d:
# [1] A B C D

answered Aug 23 '19 at 00:17

CJ Yetman

8,373
2
24
56

That indeed would be a solution (to be accepted later if nobody comes up with a more efficient approach). As you correctly pointed out, performance (and also memory requirements) would become an issue for real-world graphs (1k+ nodes) – Holger Brandl Aug 23 '19 at 07:56
On my actual usecase, which is a rather linear graph with just a few loops and ~1k nodes this solution does not compute in finite time. That's why I did not tag it as accepted. – Holger Brandl Aug 29 '19 at 07:30
Out of curiosity, which part of it? `min`, `sapply`, `$`, and `which.max` are all highly optimized base functions and they're only working with a list of numerics at that point, which they should be able to handle easily. `igraph::all_simple_paths` is some magic that I don't understand, so I don't know how performant that should be. How many simple paths exist in your use case? Maybe it's `igraph::E`'s extraction of edges in the `sapply`? – CJ Yetman Aug 29 '19 at 07:45
help file warns: "Note that potentially there are exponentially many paths between two vertices of a graph, and you may run out of memory when using this function, if your graph is lattice-like." – CJ Yetman Aug 29 '19 at 07:56
I totally agree. I've seen the help warning as well. It never comes back from `igraph::all_simple_paths` which enumerates all paths, which will fail for larger directed graphs if the have loops etc. As said before, I also consider the solution just a workaround. The correct solution would be an adopted dijstra (aka shortest path) implementation that takes the nature of the problem into account (see refs in question). – Holger Brandl Aug 29 '19 at 10:59

score 2 · Answer 2 · answered Aug 26 '19 at 19:58

2

You could try the same idea as in IGRAPH IN R: Find the path between vertices that maximizes the product of edge attributes. Invert the weights, divide by the total to keep the weights < 1 (to keep the log-weights positive), and take the min:

x<-shortest_paths(net,3,8, weights=-log(E(net)$weight/sum(E(net)$weight)), output="epath")[[2]]
E(net)[x[[1]]]
min(E(net)$weight[x[[1]]])

which gives

+ 4/8 edges from 57589bc (vertex names):
[1] carbs      ->Fermenters  Fermenters ->H2          H2         ->Methanogens Methanogens->H2O
[1] 10

answered Aug 26 '19 at 19:58

cgrafe

443
1
6
14

1

As discussed in a (unfortunately author-deleted answer) the shortest path with just edge rescaling does not compute the maximum bottlneck path. To do so dijkstra needs to be changed to use a different argmax over the minimal width. See http://www.cs.cmu.edu/~avrim/451f08/lectures/lect1007.pdf section 13.3 for details. – Holger Brandl Aug 27 '19 at 08:20

How to calculate a maximum-bottleneck path with igraph?

2 Answers2