# Math.Grads

[![Travis](https://img.shields.io/travis/biocad/math-grads.svg)](https://travis-ci.org/biocad/math-grads)
[![hackage](https://img.shields.io/hackage/v/math-grads.svg)](https://hackage.haskell.org/package/math-grads)
[![hackage-deps](https://img.shields.io/hackage-deps/v/math-grads.svg)](https://hackage.haskell.org/package/math-grads)

Math.Grads is library that provides graph-like data structures
and various useful algorithms for analysis of these data structures.

Its main feature is that all of provided type classes, data structures and 
functions are written in most abstract way possible to meet different demands
in functionality.

## Data Structures

### Graph

Graph is a type class that upon being instantiated gives data structure
properties of graph-like object.

### GenericGraph

GenericGraph is a data structure that describes undirected graphs and is
parametrized by type of graph's vertices and type of graph's edges. 
So it's really up to the developer what will be stored in Generic Graph's vertices
and edges.

GenericGraph is honest instance of Graph, therefore it can be used in all functions
that require their parameters to be Graphs.

## Algorithms

### Ullmann's subgraph isomorphism algorithm

Math.Grads contains implementation of Ullmann's subgraph isomorphism 
[algorithm](https://www.cs.bgu.ac.il/~dinitz/Course/SS-12/Ullman_Algorithm.pdf).
There are several functions that one can find helpful in order to check two graphs
for isomorphism or subgraph isomorphism: 

* `isIso` checks whether two graphs are isomorphic;
* `isIsoSub` checks whether second graph has subgraph isomorphic to the first one;
* `getIso` finds matching of vertices of first graph to vertices of subgraph in second graph that
is isomorphic to the first graph;
* `getMultiIso` finds all such matchings.

In order for these functions to work graphs that are being passed to them have to also
be instances of `GComparable` type class.

Definition of this class is as follows:

```haskell
class (Graph g1, Graph g2) => GComparable g1 v1 e1 g2 v2 e2 where
  vComparator :: g1 v1 e1 -> g2 v2 e2 -> VComparator v1 v2
  eComparator :: g1 v1 e1 -> g2 v2 e2 -> EComparator e1 e2

-- | Function that checks whether two vertices are identical.
type VComparator v1 v2 = VertexIndex -> VertexIndex -> Bool

-- | Function that checks whether two edges are identical.
type EComparator e1 e2 = GraphEdge e1 -> GraphEdge e2 -> Bool
```

So, basically, if two `Graph`s are `GComparable` with each other there exist
two functions that are responsible for establishing equality between vertices and edges
of such Graphs.

Here Math.Grads gets its chance to shine, because developer isn't constrained to 
what we (as developers of Math.Grads) thought would be an appropriate way for comparing 
vertices and edges of your data structure. We give the developers opportunity to define 
such relations for their data structures themselves. 

Maybe you want to know surroundings of two vertices in order to compare them, maybe 
you don't — the choice is yours!

### Algorithm for calculation of planar graph's coordinates

Math.Grads provides algorithm for calculation of coordinates of planar graphs.
Its main idea is that most such graphs used in practice can be represented 
as union of systems of conjugated cycles and paths that connect these systems.

So, if you know, that your planar graph looks just like this 
(for example, small molecules from chemistry perfectly fit 
into the definition of graphs that can be drawn correctly by the algorithm), 
you may find `getCoordsForGraph` function quite useful.

Algorithm first draws systems of conjugated cycles, then draws paths between them,
unites systems with path and using random generator samples different conformations
of resulting graph until conformation without self-intersections (that's why graph needs
to be planar) is found.

Once again, in order for you graph to be drawn you need to make it an instance of
special type class:

```haskell
class Graph g => Drawable g v e where
  edgeFixator :: g v e -> EdgeFixator e
  edgeFixator = const $ (,) []
  
type EdgeFixator e = CoordMap -> (EdgeList e, CoordMap)
```

`edgeFixator` is function that given `Graph` returns other function that somehow transforms 
coordinates of graph before sampling and states, which edges of graph shouldn't change their coordinates
during sampling ('fixates' them, if you will). As you can see, `edgeFixator` has default implementation,
so if you don't want such functionality, just instantiate your graph as `Drawable` without
getting into such details.

### Miscellaneous functions on graphs

Math.Grads also provides all other kinds of graph algorithms that you might find useful:
your depth-first searches, breadth-first searches, functions to find cycles in graphs and so on.