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

[Bin Jin]

sorry, it's 15 seconds. It's a typo

On Wed, May 11, 2011 at 3:20 PM, Bin Jin <bjin1990 at gmail.com> wrote:

> 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/0d4e1453/attachment.htm>