algebraic-graphs/typescript

Algebraic graphs implementation in TypeScript

Algebraic graphs implementation in TypeScript

alga-ts is a library for algebraic construction and manipulation of graphs in TypeScript. This is a TypeScript port of alga and alga-scala.

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.

N.B. Please note that this project is WIP, so use it at your own discretion.

Installation

The main library, alga-ts, is available at the NPM. As it uses fp-ts for higher-kinded types, be sure to install it as well:

npm install --save alga-ts fp-ts

Usage

To begin using alga-ts, you first need to obtain an instance of it's API for the given Eq of your target data type. Consider the example:

import { getStructEq, eqNumber, eqString } from 'fp-ts/lib/Eq';
import { getInstanceFor } from 'alga-ts';

interface User {
  name: string;
  age: number;
}

const eqUser = getStructEq({
  name: eqString,
  age: eqNumber,
});

const G = getInstanceFor(eqUser);

Now G is a module containing all methods & constructors required to work with graphs of User:

const user1: User = { name: 'Alice', age: 32 };
const user2: User = { name: 'Bob', age: 41 };
const user3: User = { name: 'Charlie', age: 28 };

const graph1 = G.connect(
  G.edge(user1, user2),
  G.edge(user2, user3),
);

console.log(G.hasEdge(user1, user3, graph1)); // => true

Pipeable graphs

Algbraic graphs happen to have type class instances for Monad (and, consequently, for Functor and Applicative) and Alternative. API instance, obtained via getInstanceFor, exposes methods from these type classes in a data-last form, so they could be used with pipe from fp-ts:

import { pipe } from 'fp-ts/lib/pipeable';
import { getInstanceFor } from 'alga-ts';

const GS = getInstanceFor(eqString);

...

const graph2 = pipe(
  graph1,
  G.map(u => u.name),
);

console.log(GS.hasEdge('Alice', 'Charlie', graph2)); // => true

typescript's Issues

Release AdjacencyMap and AdjacencyLists

On master there are utilities for getting AdjacencyMaps and AdjacencyLists but the most recent version on npm doesn't contain them. Can we get a release so we can use these?