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
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.

  3. Pingback: Learn You a Haskell! | The Math Less Traveled

Comments are closed.