algebraic-graphs: A library for algebraic graph construction and transformation

[ algebra, algorithms, data-structures, graphs, library, mit ] [ Propose Tags ]

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory and implementation details.

The top-level module Algebra.Graph defines the main data type for algebraic graphs Graph, as well as associated algorithms. For type-safe representation and manipulation of non-empty algebraic graphs, see Algebra.Graph.NonEmpty. Furthermore, algebraic graphs with edge labels are implemented in Algebra.Graph.Labelled.

The library also provides conventional graph data structures, such as Algebra.Graph.AdjacencyMap along with its various flavours: adjacency maps specialised to graphs with vertices of type Int (Algebra.Graph.AdjacencyIntMap), non-empty adjacency maps (Algebra.Graph.NonEmpty.AdjacencyMap), and adjacency maps with edge labels (Algebra.Graph.Labelled.AdjacencyMap). A large part of the API of algebraic graphs and adjacency maps is available through the Foldable-like type class Algebra.Graph.ToGraph.

The type classes defined in Algebra.Graph.Class and Algebra.Graph.HigherKinded.Class can be used for polymorphic construction and manipulation of graphs. Also see Algebra.Graph.Fold that defines the Boehm-Berarducci encoding of algebraic graphs.

This is an experimental library and the API is expected to remain unstable until version 1.0.0. Please consider contributing to the on-going discussions on the library API.


[Skip to Readme]
Versions 0.0.1, 0.0.2, 0.0.3, 0.0.4, 0.0.5, 0.1.0, 0.1.1, 0.1.1.1, 0.2, 0.3
Change log CHANGES.md
Dependencies array (>=0.4 && <0.6), base (>=4.7 && <5), base-compat (>=0.9.1 && <0.11), containers (>=0.5.5.1 && <0.8), deepseq (>=1.3.0.1 && <1.5), mtl (>=2.1 && <2.3), semigroups (==0.18.3.*) [details]
License MIT
Copyright Andrey Mokhov, 2016-2018
Author Andrey Mokhov <andrey.mokhov@gmail.com>, github: @snowleopard
Maintainer Andrey Mokhov <andrey.mokhov@gmail.com>, github: @snowleopard, Alexandre Moine <alexandre@moine.me>, github: @nobrakal
Category Algebra, Algorithms, Data Structures, Graphs
Home page https://github.com/snowleopard/alga
Source repo head: git clone https://github.com/snowleopard/alga.git
Uploaded by snowleopard at Thu Nov 29 23:38:58 UTC 2018
Distributions LTSHaskell:0.2, NixOS:0.3, Stackage:0.3
Downloads 1906 total (107 in the last 30 days)
Rating 2.5 (votes: 4) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-11-29 [all 1 reports]
Hackage Matrix CI

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for algebraic-graphs-0.3

[back to package description]

Algebraic graphs

Hackage version Linux &amp; OS X status Windows status

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this Haskell Symposium paper and the corresponding talk for the motivation behind the library, the underlying theory and implementation details. There is also a Haskell eXchange talk, and a tutorial by Alexandre Moine.

Main idea

Consider the following data type, which is defined in the top-level module Algebra.Graph of the library:

data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)

We can give the following semantics to the constructors in terms of the pair (V, E) of graph vertices and edges:

  • Empty constructs the empty graph (∅, ∅).
  • Vertex x constructs a graph containing a single vertex, i.e. ({x}, ∅).
  • Overlay x y overlays graphs (Vx, Ex) and (Vy, Ey) constructing (Vx ∪ Vy, Ex ∪ Ey).
  • Connect x y connects graphs (Vx, Ex) and (Vy, Ey) constructing (Vx ∪ Vy, Ex ∪ Ey ∪ Vx × Vy).

Alternatively, we can give an algebraic semantics to the above graph construction primitives by defining the following type class and specifying a set of laws for its instances (see module Algebra.Graph.Class):

class Graph g where
    type Vertex g
    empty   :: g
    vertex  :: Vertex g -> g
    overlay :: g -> g -> g
    connect :: g -> g -> g

The laws of the type class are remarkably similar to those of a semiring, so we use + and * as convenient shortcuts for overlay and connect, respectively:

  • (+, empty) is an idempotent commutative monoid.
  • (*, empty) is a monoid.
  • * distributes over +, that is: x * (y + z) == x * y + x * z and (x + y) * z == x * z + y * z.
  • * can be decomposed: x * y * z == x * y + x * z + y * z.

This algebraic structure corresponds to unlabelled directed graphs: every expression represents a graph, and every graph can be represented by an expression. Other types of graphs (e.g. undirected) can be obtained by modifying the above set of laws. Algebraic graphs provide a convenient, safe and powerful interface for working with graphs in Haskell, and allow the application of equational reasoning for proving the correctness of graph algorithms.

To represent non-empty graphs, we can drop the Empty constructor -- see module Algebra.Graph.NonEmpty.

To represent edge-labelled graphs, we can switch to the following data type, as explained in my Haskell eXchange 2018 talk:

data Graph e a = Empty
               | Vertex a
               | Connect e (Graph e a) (Graph e a)

Here e is the type of edge labels. If e is a monoid (<+>, zero) then graph overlay can be recovered as Connect zero, and <+> corresponds to parallel composition of edge labels.

How fast is the library?

Alga can handle graphs comprising millions of vertices and billions of edges in a matter of seconds, which is fast enough for many applications. We believe there is a lot of potential for improving the performance of the library, and this is one of our top priorities. If you come across a performance issue when using the library, please let us know.

Some preliminary benchmarks can be found here.

Blog posts

The development of the library has been documented in the series of blog posts:

Algebraic graphs in other languages

See draft implementations in Agda and Scala.