On 13/05/12 14:55, Sönke Hahn wrote:

Somehow related questions are: What am I going to do with a dot-graph, that has more than 500 vertices? Is there an intelligent way to reduce the graph?

Setting the `concentrate' parameter to true helps, but dot does not work well with massive graphs. Francesco.

On 05/13/2012 04:16 PM, Francesco Mazzoli wrote:

I found Gephi (https://gephi.org/) quite good when I had to visualize big graphs, and it supports dot files so you can try it out easily.

gephi looks very interesting, thanks.

On 05/14/2012 04:21 PM, Simon Michael wrote:

In a 2000-patch repo it took 22 hours: http://joyful.com/darcsden/simon/hledger/raw/patchdeps.pdf

:)

It should escape double-quotes in patch names, I did that manually.

That should be fixed (in the repo).

On 16 May 2012 19:43, wren ng thornton wrote:

On 5/12/12 8:52 AM, Sönke Hahn wrote:

...

Any comments or suggestions?

Cabalize it and release it on Hackage. But especially the cabalization part :)

You should probably farm out the toDot rendering to one of the libraries that focuses on that[1], since they'll have focused on the efficiency issues--- or if they haven't, then you can contribute improvements there, helping everyone win. In particular, you're using Strings which is a notorious performance sink. Using Text or ByteStrings would be far better.

Also, have you compared your transitive reduction to just outputting the whole graph and then using `tred`? The latter approach has the distinct downside of needing to serialize the whole graph; but it could still be a win unless you intend to implement similar algorithms yourself. The smart algorithms do *much* better than brute force.

I would like to point out that graphviz has a native implementation of tred (well, analogous rather than exact re-implementation). I also haven't joined this discussion before now, but some of the reduction algorithms in Graphalyze [1] (as used in SourceGraph [2]) might be applicable, though I admit they're not the best possible implementations [1]: http://hackage.haskell.org/package/Graphalyze [2]: http://hackage.haskell.org/package/SourceGraph

And of course it'd be nice to be able to pass arguments to the program in order to filter and otherwise manipulate the resulting graph. A lot of that can be done by special programs which only know about the Dot language (e.g., tred), so you should only focus on things which aren't captured by the Dot language or are otherwise only knowable by querying Darcs.

[1] Like graphviz or language-dot:

   http://hackage.haskell.org/package/graphviz    http://hackage.haskell.org/package/language-dot

Though it doesn't look like those are used by the various other foo2dot programs on Hackage:

   http://hackage.haskell.org/package/hs2dot    http://hackage.haskell.org/package/prof2dot    http://hackage.haskell.org/package/scons2dot    http://hackage.haskell.org/package/vacuum-cairo    http://hackage.haskell.org/package/vacuum-opengl

So perhaps there's some issue with those libraries...

-- Live well, ~wren

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

On 17 May 2012 03:31, Stephen Tetley wrote:

...

On 16 May 2012 19:43, wren ng thornton wrote:

...

...

You should probably farm out the toDot rendering to one of the libraries that focuses on that[1], since they'll have focused on the efficiency issues--- or if they haven't, then you can contribute improvements there, helping everyone win. In particular, you're using Strings which is a notorious performance sink. Using Text or ByteStrings would be far better.

I'm not sure swapping to Text or ByteStrings make be much great shakes for this. If you are generating huge files, where it would count - then the files are going to be a real problem for Graphviz to render (unless Graphviz has seen some optimization recently...).

I found with graphviz that switching to Text gave two advantages: 1) Easier to require UTF-8 usage 2) Printing and parsing was faster In part, the speed-up came from switching to wl-pprint-text rather than pretty (the wl-pprint method of pretty-printing seems to have some efficiency improvements in how concatenation is done over pretty) and the Text backend for polyparse lets you use manySatisfy rather than (many . satisfy) which is more efficient. But even in my initial pseudo-port (going via String a lot, etc.) there was a slight speed-up. So I think there is still a valid reason to consider using Text (or possibly ByteString, but I think that has potential issues).

That said, I would recommend Sönke uses a pretty print library rather than Printf as using the former makes for much more idiomatic for Haskell and generally performs well enough for "generational" activities even if it uses Strings internally.

Best wishes

Stephen

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

On 05/16/2012 11:43 AM, wren ng thornton wrote:

Also, have you compared your transitive reduction to just outputting the whole graph and then using `tred`? The latter approach has the distinct downside of needing to serialize the whole graph; but it could still be a win unless you intend to implement similar algorithms yourself. The smart algorithms do *much* better than brute force.

I've done some profiling and found that the executable is spending about half of its time executing my brute force graph algorithm. So doing something smarter here (like using "tred") seems like a good idea. The bad news is that without running my inefficient algorithm the executable still doesn't scale well. Maybe there is a better way to let the darcs library compute the patch dependencies.

And of course it'd be nice to be able to pass arguments to the program in order to filter and otherwise manipulate the resulting graph. A lot of that can be done by special programs which only know about the Dot language (e.g., tred), so you should only focus on things which aren't captured by the Dot language or are otherwise only knowable by querying Darcs.

Sounds reasonable. Command line options would be nice.