[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[igraph] Longest path in weighted DAG
From: |
Ananya Muddukrishna |
Subject: |
[igraph] Longest path in weighted DAG |
Date: |
Fri, 14 Nov 2014 13:49:25 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0 |
Hi,
I have implemented longest path calculation of a weighted DAG using R
igraph.
My implementation shown below is slow for large graphs.
I would greatly appreciate any hints to speed it up. Any thoughts on how
far my implementation is from the best known/typical algorithm is also
welcome.
Thanks!
# 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)
--
Best regards,
Ananya
--
Ananya Muddukrishna
Ph.D. student
KTH Royal Institute of Technology
http://www.kth.se/profile/ananya/
- [igraph] Longest path in weighted DAG,
Ananya Muddukrishna <=