I needed some graph visualizations for the chapter on logic and computability in The notes and I really didn't want to write about 20 pieces of repetitively constructed Graphviz code. Less than one week later, Haphviz allowed me to generate those graphs with only a few lines of Haskell code.
Ever since I've learned about lattices, I've wanted to generate a Hasse diagram of natural numbers with 'divides' as the partial order. Of course it's impossible to generate an infinite diagram but I would settle for a parametric arbitrarily big diagram.
We'll generate a node in the graph for every natural number starting from $1$. Now, as far as the maths go, there should be an edge between two nodes labeled $a$ and $b$ if $a$ is divisible by $b$ and there doesn't exist a node labeled $c$ that has edges from $a$ and to $b$.
As the math is not the focus of this post, let's see how you would generate code to visualize this graph with Haphviz.
renderToStdOut $ graph directed "divisors" $ do nodes <- forM [1..n] $ node . T.pack . show let ns = zip [1..] nodes sequence_ [ni --> nj | (i, ni) <- ns, (j, nj) <- ns, i > j, primary i j]
primary :: Integer -> Integer -> Bool function determines wether there should be an edge between two nodes.
That wasn't so hard, was it?
dot on the generate graphiz code with
n = 10 yields the following image.
Finite state automata.
Having a Turing-complete encoding system for graph visualization means that we can simplify the process of visualizing graphs with a predictable structure.
Haphviz has a module Text.Dot.FSA with a single function
fsaGraph that allows you to easily generate graphs for finite state automata.
The following code generates Graphviz code for a simple finite state automaton.
renderToStdOut $ fsaGraph [a, b, c] -- States a -- Starting state [b] -- Accepting states [(a, b, p), (b, b, q), (b, c, p)] -- Edges where (a, b, c, p, q) = ("a", "b", "c", "p" ,"q")
The design of the internals of this library is based on the design of HaTeX internals.
A single data type
Dot represents the contents of a graph.
Generating graphs by generating a
Dot structure is certainly possible but it is a tad tedious.
DotGen monad allows you to generate graphs in a simpler way.
Now you only have to declare how you want to the graph to look and let the combinators take care of constructing a
Further extensions of this libraries are certainly possible. Here are some of such extensions I propose. Feel free to have a go at implementing them if you need them.
More predictable graph generation
As far as predictable graph generation goes, there is, at the time of writing, only support for finite state automata visualization in Haphviz For The notes, I made a similar piece of code that allowed me to generate Store-Heap model visualizations.
In future work on this library, code could be written to make visualizations of other predictable graphs easier:
- Visualizations of trees from Data.Tree
- Other automata from the domain of computability: Pushdown automata and Turing machines
- Flow networks
A Graph type class
Data.Tree is just one example of a data type that could be represented as a tree. Others may well be visualizable too.
I propose a type class
Graph a with a single function
graph :: a -> DotGen () that generates its visualization.
DotGen Monad transformer
DotGen is just a monad.
It's currently not possible to do
IO while generating a graph.
DotGenT m monad transformer would allow you to compose the graph generation monad with other monads like
This would be fairly trivial as
DotGen is already a type synonym for
StateT State (WriterT Dot Identity).