Library containing graph data structures and graph algorithms.

Library containing graph data structures and graph algorithms.

Graph data structures:

• Graph type class;

• GenericGraph data structure.

Graph algorithms:

• Ullmann's subgraph isomorphism algorithm;

• drawing of planar graphs.

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

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 Graphs 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:

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.