Re: [igraph] Longest path in weighted DAG

[Gábor Csárdi]

You can profile your code to see what exactly is slow. Gabor

On Fri, Nov 14, 2014 at 7:49 AM, Ananya Muddukrishna <address@hidden> wrote:
> 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-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help