Defines various algorithms for use on DotRepr graphs. These are typically re-implementations 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.

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.

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 sub-clusters) are made global.
• Sub-graphs aren't kept, only clusters.
• ColorScheme Attributes are removed (as all Color 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.

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 re-implementations 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 re-implement 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.