[Haskell-cafe] need help on building a huge graph

[Bin Jin]

Hi, cafe

I'm recently solving some algorithm puzzles from previous Google Code Jam
rounds, and today I met some problem I can't solve now.
It's a problem (Round 3 2010, B) that the solution require to find a
shortest path in a graph with about 100,000 vertices
and 50 edges from each vertex.  Apart from find shortest path, I find that
building graph also takes a lot of time.
Yes, I know it's unnecessary to dump the entire graph to the memory, but I
want to know if it's possible to build such graph in some reasonable time.

following is a snippet of code building the graph, runs about 15 mins on
Core 2 Duo 2.40GHz without any RTS flags

>
> > import Data.Array
> >
> > main = graph `seq` putStrLn "Finished"
> >
> > n = 100000
> > bnds = (0, n-1)
> >
> > buildGraph bnds edges = accumArray (flip (:)) [] bnds edges
> >
> > graph = buildGraph bnds edges
> >
> > edges = [ (i, (y, 1 - x::Int))
> >         | i <- range bnds
> >         , j <- [2..50]
> >         , let (x, y) = if i + j >= n then (1, i + j - n) else (0, i + j)
> >         ]
> >
>

Regards,
Bin Jin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110511/6ccf2278/attachment.htm>