r - 如何使用 igraph 计算最大瓶颈路径？

Question

给定一个具有单个源和单个接收器的容量网络，我如何计算 maximum-bottleneck path (也称为最宽路径或最大容量路径问题)使用 igraph？

我读到(例如 here 甚至使用伪代码 there )，对 Dijkstra 算法进行一些修改是可能的，但我不想深入算法开发，而是使用 igraph。

示例

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
# )

那么对于这个例子，我如何计算从carbs到H2O的最大容量路径？

Answer 1

我不知道这有多高效，但是您可以使用 igraph 查找所有“简单”路径，然后计算每个路径的最小边权重，然后选择最大...

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