I had issues with FGL in the past, too. Although FGL is really nice to work with, it just uses a ridiculous amount of memory for large graphs.
In the end, I used Data.Graph from containers [1]. This was a lot more reasonable, and let me finish my project relatively easily. Regards, - Clark [1] http://hackage.haskell.org/packages/archive/containers/0.5.0.0/doc/html/Data-Graph.html On Sun, May 20, 2012 at 10:55 AM, Serguey Zefirov <sergu...@gmail.com> wrote: > 2012/5/20 Benjamin Ylvisaker <benjam...@fastmail.fm>: >> I have a problem that I'm trying to use Haskell for, and I think I'm running >> into scalability issues in FGL. However, I am quite new to practical >> programming in Haskell, so it's possible that I have some other bone-headed >> performance bug in my code. I tried looking around for concrete information >> about the scalability of Haskell's graph libraries, but didn't find much. >> So here are the characteristics of the problem I'm working on: >> >> - Large directed graphs. Mostly 10k-100k nodes, but some in the low 100ks. >> - Sparse graphs. The number of edges is only 2-3x the number of nodes. >> - Immutable structure, mutable labels. After initially reading in the >> graphs, their shape doesn't change, but information "flows" around the >> graph, changing the labels on nodes and edges. > > I would like to suggest to you a representation based in 32-bit > integers as vertex index. I.e., "roll your own" > > Use strict IntMap IntSet for neighbor information, it is very efficient. > >> I wrote some code that reads in graphs and some some basic flow computations >> on them. The first few graphs I tried were around 10k nodes, and the >> performance was okay (on the order of several seconds). When I tried some >> larger graphs (~100k), the memory consumption spiked into multiple GB, the >> CPU utilization went down to single digit percentages and the overall >> running time was closer to hours than seconds. > > Looks like your code does not force everything. It leaves some thunks > unevaluated, check for that situation. > > It is common pitfall, not only for computations on graphs. > >> >> Because the graph structure is basically immutable for my problem, I'm >> tempted to write my own graph representation based on mutable arrays. >> Before I embark on that, I wonder if anyone else can share their experience >> with large graphs in Haskell? Is there a library (FGL or otherwise) that >> should be able to scale up to the size of graph I'm interested in, if I >> write my code correctly? > > The above structure (IntMap IntSet) allowed for fast computations on > relatively large arrays, in order of 1M vertices and 16M > undirected/32M directed edges. > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe