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

About Brent

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

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

Comments are closed.