tag:blogger.com,1999:blog-5195188167565410449.post1490295420919800739..comments2016-09-19T07:11:19.884+01:00Comments on Haskell for Maths: Graph symmetriesDavidAhttp://www.blogger.com/profile/16359932006803389458noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-5195188167565410449.post-54143554296527214722009-06-23T21:06:14.970+01:002009-06-23T21:06:14.970+01:00Mark,
If you want to see where I'm heading, y...Mark,<br /><br />If you want to see where I'm heading, you could take a peek at the source.<br /><br />Groups are mainly represented by a list of generators. However, there is also an implementation of Schreier-Sims algorithm, which leads to a representation as a set of transversals for stabilisers. Either way, we can efficiently represent and work with groups with millions or trillions of elements (eg the Rubik's cube group).<br /><br />For finding graph symmetries, the main improvement is to use distance partitions to narrow down the choices at each step - that is, having chosen to map x1 to y1, then if x2 is at distance d from x1 (eg distance 1 for a neighbour), then for y2 we need only consider vertices at distance d from y1. When it comes to x3 and y3, we get a kind of triangulation effect, and so on, quickly narrowing down the possibilities.DavidAhttp://www.blogger.com/profile/16359932006803389458noreply@blogger.comtag:blogger.com,1999:blog-5195188167565410449.post-37651598423653466592009-06-23T19:08:54.650+01:002009-06-23T19:08:54.650+01:00I hope you discuss this at greater length, because...I hope you discuss this at greater length, because I am very eager to see wher eyou are going. Around 1993 I wrote some programs in SML for calculating automorphism groups of graphs. I implemented a dfs algorithm, but I didn't (and still don't) know a better one.<br /><br />Also I would like to see how you represent groups. I am hoping that you will use a more space-efficient representation than just a list of elements. I was interested in vertex-transitive graphs, and for these the automorphism group is symmetric, and so the size of the list-of-elements representation is exponential in the size of the graph.Mark Dominushttp://www.blogger.com/profile/17698641253266210249noreply@blogger.comtag:blogger.com,1999:blog-5195188167565410449.post-80171834487660789202009-06-17T12:19:53.765+01:002009-06-17T12:19:53.765+01:00Very cool! I look forward to reading more. =)Very cool! I look forward to reading more. =)byorgeyhttp://byorgey.wordpress.com/noreply@blogger.com