## m-bracelets code

[15 January 2013: updated code to work with the latest versions of fgl and graphviz. Thanks to Conal Elliott for the updates!]

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.Text.Lazy (pack, unpack)
> import Data.Graph.Inductive
> import Data.GraphViz
> import Data.GraphViz.Attributes.Complete
>
> 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 :: Int -> DotGraph Node
> dotGraph m = graphToDot (nonClusteredParams { fmtNode = nodeAttrs })
>                         (braceletGraph m)
>
> nodeAttrs :: (Node, Link) -> Attributes
> nodeAttrs (a,_) =
>   [ Label . StrLabel . pack . show \$ a
>   , Shape Circle
>   , BgColor [colors !! a]
>   , FillColor [colors !! a]
>   , Style [SItem Filled []]
>   ]
>
> colors = cycle \$ map toColor [ LightBlue
>                              , Red
>                              , Orange
>                              , Yellow
>                              , Green
>                              , Blue
>                              , Purple
>                              , Brown
>                              , Pink
>                              , Gray
>                              ]
>
> main = do
>   (m:_) <- fmap (fmap read) getArgs
>   putStr . unpack . 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`````` Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, links, pictures, programming and tagged , , , , . Bookmark the permalink.

### 3 Responses to m-bracelets code

1. luc says:

May I ask you where the ColorName come from ? I try and recompile the code and got Not in scope: data constructor `ColorName’

was in a library API at that time ?
( using ghc version 6.12.1)

2. Brent says:

Hi luc, it appears the GraphViz library API has been changed since I wrote this. Try using graphviz-2999.6.0.0, which was the latest version at the time that I wrote this post.