Самый длинный путь взвешенного DAG с использованием R igraph

Question

Я реализовал вычисление длинного пути взвешенного DAG с помощью R igraph.

Моя реализация (показанная ниже) медленна для больших графиков. Я был бы очень признателен за любые подсказки, чтобы ускорить его. Любые мысли о том, насколько далеко моя реализация от самого известного / типичного алгоритма, также приветствуются.

Спасибо!

# g is the igraph DAG
# g <- graph.tree(10000, 2, mode="out")
# E(g)$weight <- round(runif(length(E(g))),2) * 50 
# Topological sort
tsg <- topological.sort(g)    
# Set root path attributes
# Root distance
V(g)[tsg[1]]$rdist <- 0
# Path to root
V(g)[tsg[1]]$rpath <- tsg[1]
# Get longest path from root to every node        
for(node in tsg[-1])
{
  # Get distance from node's predecessors
  w <- E(g)[to(node)]$weight
  # Get distance from root to node's predecessors
  d <- V(g)[nei(node,mode="in")]$rdist
  # Add distances (assuming one-one corr.)
  wd <- w+d
  # Set node's distance from root to max of added distances 
  mwd <- max(wd)
  V(g)[node]$rdist <- mwd
  # Set node's path from root to path of max of added distances
  mwdn <- as.vector(V(g)[nei(node,mode="in")])[match(mwd,wd)]
  V(g)[node]$rpath <- list(c(unlist(V(g)[mwdn]$rpath), node))      
}
# Longest path length is the largest distance from root
lpl <- max(V(g)$rdist)    
# Enumerate longest path
lpm <- unlist(V(g)[match(lpl,V(g)$rdist)]$rpath)    
V(g)$critical <- 0
g <- set.vertex.attribute(g, name="critical", index=lpm, value=1)    

Answer 1

У меня также была медленная версия R. Это заняло ~20 минут для 200k ребер и 30k вершин, поэтому я сломался и реализовал get.shortest.paths() для графиков с отрицательными весами ребер, которые можно использовать для поиска длинных путей путем инвертирования всех весов ребер. Вы можете попробовать мою вилку R igraph здесь

Я испытал ускорение от 100x до 1000x при переключении с моей реализации R на C.