Copyright  (c) Matthew Sackman, Ivan Lazar Miljenovic 

License  3Clause BSDstyle 
Maintainer  Ivan.Miljenovic@gmail.com 
Safe Haskell  None 
Language  Haskell2010 
Defines various algorithms for use on DotRepr
graphs. These are
typically reimplementations of behaviour found in existing Graphviz
tools but without the I/O requirement.
Note that one way that these algorithms differ from those found in Graphviz is that the order of clusters is not maintained, which may affect layout in some cases.
 data CanonicaliseOptions = COpts {}
 defaultCanonOptions :: CanonicaliseOptions
 dotLikeOptions :: CanonicaliseOptions
 canonicalise :: DotRepr dg n => dg n > DotGraph n
 canonicaliseOptions :: DotRepr dg n => CanonicaliseOptions > dg n > DotGraph n
 transitiveReduction :: DotRepr dg n => dg n > DotGraph n
 transitiveReductionOptions :: DotRepr dg n => CanonicaliseOptions > dg n > DotGraph n
Canonicalisation Options
For simplicity, many algorithms end up using the canonicalisation
functions to create the new DotGraph
. CanonicaliseOptions
allows
you to configure how the output is generated.
data CanonicaliseOptions Source
COpts  

dotLikeOptions :: CanonicaliseOptions Source
Options that are more like how dot Tcanon
works.
Canonicalisation
These functions implement similar functionality to dot Tcanon
(i.e. creates a canonical form of any DotRepr
graph). without
requiring IO.
Note that due to implementation specifics the behaviour is not identical; in particular:
 Any specified
Attributes
that equal the defaults are stripped out (unless required to override a previous attribute that doesn't apply here).  Grouping of attributes (when
'groupAttributes = True'
) is much more conservative; only those node/edge attributes that are common to all nodes and edges within that cluster (and within subclusters) are made global.  Subgraphs aren't kept, only clusters.
ColorScheme
Attributes are removed (as allColor
values embed any needed color scheme anyway) as the output order of attributes may change (and this matters for the Haskell side of things).
In particular, note that this function will create a single explicit definition for every node in the original graph and place it in the appropriate position in the cluster hierarchy. All edges are found in the deepest cluster that contains both nodes.
canonicalise :: DotRepr dg n => dg n > DotGraph n Source
Canonicalise with some sensible defaults.
canonicaliseOptions :: DotRepr dg n => CanonicaliseOptions > dg n > DotGraph n Source
As with canonicalise
, but allow custom CanonicaliseOptions
.
Dealing with transitive edges
In large, cluttered graphs, it can often be difficult to see what is happening due to the number of edges being drawn. As such, it is often useful to remove transitive edges from the graph before visualising it.
For example, consider the following Dot graph:
digraph { a > b; a > c; b > c; }
This graph has the transitive edge a > c
(as we can reach c
from a
via b
).
Graphviz comes with the tred
program to perform these transitive
reductions. transitiveReduction
and transitiveReductionOptions
are pure Haskell reimplementations of tred
with the following differences:
tred
prints a message to stderr if a cycle is detected; these functions do not.tred
preserves the original structure of the graph; these functions use the canonicalisation functions above to create the new graph (rather than reimplement creation functions for each one).
When a graph contains cycles, an arbitrary edge from that cycle is ignored whilst calculating the transitive reduction. Multiple edges are also reduced (such that only the first edge between two nodes is kept).
Note that transitive reduction only makes sense for directed graphs; for undirected graphs these functions are identical to the canonicalisation functions above.
The caveats for the canonicalisation functions also apply.
transitiveReduction :: DotRepr dg n => dg n > DotGraph n Source
transitiveReductionOptions :: DotRepr dg n => CanonicaliseOptions > dg n > DotGraph n Source