Comments on: Code for Manipulating Graphs in Haskell

By: Ivan Miljenovic

Ivan Miljenovic — Wed, 22 Apr 2009 22:33:49 +0000

Actually, I’m using a Set to store the current canonical graphs found, after much urging by the people on #haskell.

Even so, however, I beg to differ that nubBy is unwise: about 2/3 of my time is spent running canonicGraph (which I do _before_ removing duplicates). Considering that for one test I ran, I had over 2.5 million values out of which only around 140 were unique, nubBy isn’t that much of a problem.

The big advantage of nubBy as opposed to using “map head . group . sort” or “Set.toList . Set.fromList” is that nubBy is _lazy_, so that my program can start spitting out values as soon as it finds them as opposed to having to sort the entire list (which gets _very_ large) before it can start printing values.

By: cdsmith

cdsmith — Wed, 22 Apr 2009 22:00:46 +0000

Ivan, if you have a large enough number of graphs, using nubBy is unwise. You’re actually better off sorting (Graph is an instance of Ord), and then removing consecutive duplicates. (map head . groupBy ((==) `on` snd . sort) would replace your nubBy in that case.

By: Ivan Miljenovic

Ivan Miljenovic — Wed, 22 Apr 2009 01:12:35 +0000

I’ve been using HGAL basically by doing “map fst . nubBy ((==) `on` snd) . map (\f -> (f,canonicGraph . toGraph f))” (where toGraph is function on my data type I’m using). I’m probably going to try re-implementing HGAL on my own directly from Brendan McKay’s paper to see if I can improve performance somehow, as my app spends more time doing canonicGraph than anything else :s

By: cdsmith

cdsmith — Wed, 22 Apr 2009 00:58:29 +0000

I have little doubt that the HGAL implementation of isIsomorphic is considerably faster in most cases, though you could give it a shot. I don’t see anything like isonub in the hgal package, though if I understand correctly, you could map canonicGraph from the Data.Graph.Automorphism package over the list, and then just sort the list and remove consecutive duplicates using the standard Ord and Eq instances.

I was unable to get hgal installed quickly when I wrote this (and again now, I get errors from cabal install, related to building an old version of the array package)… and since my application only had to deal with tens of thousands of graphs of at most about 5 vertices, this worked just as well.

By: Ivan Miljenovic

Ivan Miljenovic — Wed, 22 Apr 2009 00:32:34 +0000

Would you know how your isIsomorphic and isonub functions compare to Jean-Philippe Bernardy’s HGAL package (available via Hackage)? And how do you define “small” graphs? (I’m needing to remove isomorphic duplicates from potentially millions of graphs of various orders…)