The Math Less Traveled

By popular demand, here is the Haskell code I used to generate the images in my previous post. This post is literate Haskell; you can simply copy and paste this entire post into a file called BraceletGraph.lhs (or anything you like, as long as it ends with .lhs) and run it yourself. Also, I used Robert Greayer’s lovely BlogLiterately tool to write and format this post.

First, a few imports: we use Martin Erwig’s fgl functional graph library for constructing graphcs, and Ivan Miljenovic’s bindings to the Graphviz library in order to output graph descriptions.

> import Data.Graph.Inductive
> import Data.GraphViz
>
> import System.Environment

A "link" in a number bracelet is a pair of digits; knowing a pair of digits completely determines the remainder of the bracelet.

> type Link = (Int,Int)

The next link in a bracelet is obtained by adding and taking the result mod m.

> nextLink :: Int -> Link -> Link
> nextLink m (a, b) = (b, ((a + b) `mod` m))

We construct the list of all possible links.

> braceletLinks m = [ (a,b) | a <- [0..m-1], b <- [0..m-1] ]

We now also construct the list of all the "edges" from one link to the next.

> braceletEdges m = [ (l, nextLink m l) | l <- braceletLinks m ]

We will also need a function to convert a link into a unique numeric representation, since the graph library assumes that vertices are named by integers.

> linkToLabel m (a, b) = a*m + b

The rest of the code simply interfaces with the fgl and graphviz libraries to create a graph and output it as a .dot file. This was the hardest part of the code to write—but it was hard only in the sense that it took me a while to look through the documentation for the fgl and graphviz libraries to figure out how to do what I wanted.

> braceletGraph :: Int -> Gr Link ()
> braceletGraph m = mkGraph (map mkNode (braceletLinks m))
>                           (map mkEdge (braceletEdges m))
>   where mkNode l       = (linkToLabel m l, l)
>         mkEdge (l1,l2) = (linkToLabel m l1, linkToLabel m l2, ())
>
> dotGraph m = graphToDot True (braceletGraph m)
>                              []
>                              linkAttrs
>                              (const [])
>
> linkAttrs (_, (a,b)) =
>   [ Label . StrLabel . show $ a
>   , Shape Circle
>   , Color [colors !! a]
>   , FillColor $ colors !! a
>   , Style [SItem Filled []]
>   ]
>
> colors = cycle $ map ColorName [ "lightblue"
>                                , "red"
>                                , "orange"
>                                , "yellow"
>                                , "green"
>                                , "blue"
>                                , "purple"
>                                , "brown"
>                                , "pink"
>                                , "grey"
>                                ]
>
> main = do
>   (m:_) <- fmap (fmap read) getArgs
>   putStr . printDotGraph $ dotGraph m

We can run this program by passing it the value of m we want to use, and it outputs a file in .dot format, which we can turn into an image using one of graphiz’s graph layout tools, like neato or circo. For example:

$ ghc --make BraceletGraph.lhs
$ ./BraceletGraph 9 > bracelets9.dot
$ neato -Tpng bracelets9.dot > bracelets9.png

Tags: bracelets, graph, graphviz, Haskell, literate

This entry was posted on Friday, November 27th, 2009 at 3:27 pm and is filed under arithmetic, computation, links, pictures, programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.