CODEWITHSUNDEEP
rigraphgraph-theory
Holger Brandl
Holger Brandl

Reputation: 11222

How to calculate a maximum-bottleneck path with igraph?

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

enter image description here

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

Upvotes: 4

Views: 1285

Answers (2)

cgrafe
cgrafe

Reputation: 443

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

Upvotes: 2

CJ Yetman
CJ Yetman

Reputation: 8848

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

Upvotes: 4

Related Questions