You can profile your code to see what exactly is slow. Gabor On Fri, Nov 14, 2014 at 7:49 AM, Ananya Muddukrishna <[email protected]> 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 > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
