fp-ts-graph

Immutable, functional, highly performant graph data structure for fp-ts.

``ts
type Graph = ...
`

| Quality | y/n |
| -------------- | --- |
| directed | yes |
| cyclic | yes |
| multiple edges | no |

In the future a granular distinction of graph qualities may be supported, see roadmap.

$3

- What it's not
- Install
- Docs
- Examples
- Define Types
- Build Graph
- Debug graph visually
- Roadmap / to do

What it is

What it's not

A rendering engine or anything that has to do with a visual representation of a graph. However, for for debugging purpose we provide simple graphviz dotfile generator.

Install

`bash
npm install fp-ts @no-day/fp-ts-graph
`

Docs

API Docs

Examples

$3

`ts
// examples/types.ts

import { Graph } from '@no-day/fp-ts-graph';
import { Codec } from 'io-ts/Codec';
import * as Cod from 'io-ts/Codec';

// First, let's define some custom Id, Edge and Node type for our Graph

export type MyId = string;

export type MyNode = { firstName: string; lastName: string; age: number };

export type MyEdge = { items: number[] };

// Define codec for encoding and decoding Id to string

export const MyIdCodec: Codec = Cod.string;

// With this we can define a customized Graph type

export type MyGraph = Graph;
`

$3

`ts
// examples/build-graph.ts

import Graph, * as G from '../src';
import * as N from 'fp-ts/number';
import { pipe } from 'fp-ts/function';
import * as O from 'fp-ts/Option';
import { Option } from 'fp-ts/Option';

// We import our types from the previous section
import { MyEdge, MyId, MyNode, MyGraph, MyIdCodec } from './types';

// To save some writing, we define partially applied versions of the builder functions

const empty = G.empty();
const insertNode = G.insertNode(MyIdCodec);
const insertEdge = G.insertEdge(MyIdCodec);

// Then, let's fill the graph with Data.

export const myGraph: Option = pipe(
// We start out with and empty graph.
empty,

// And add some nodes to it.
insertNode('TC', {
firstName: 'Tonicha',
lastName: 'Crowther',
age: 45,
}),
insertNode('SS', {
firstName: 'Samual',
lastName: 'Sierra',
age: 29,
}),
insertNode('KW', {
firstName: 'Khushi',
lastName: 'Walter',
age: 40,
}),
insertNode('RR', {
firstName: 'Rian',
lastName: 'Ruiz',
age: 56,
}),

// Then we connect them with edges, which can have data, too

O.of,
O.chain(insertEdge('TC', 'SS', { items: [2, 3] })),
O.chain(insertEdge('SS', 'KW', { items: [4] })),
O.chain(insertEdge('TC', 'KW', { items: [9, 4, 3] })),
O.chain(insertEdge('KW', 'RR', { items: [2, 3] }))
);
`

$3

`ts
// examples/debug-visually.ts

import * as G from '../src';
import * as O from 'fp-ts/Option';
import { flow, pipe } from 'fp-ts/function';

// We import our graph from the previous section
import { myGraph } from './build-graph';

// We import Id codec
import { MyIdCodec } from './types';

pipe(
myGraph,

// We need to map over the graph as it may be invalid
O.map(
flow(
// Then turn the edges into strings
G.mapEdge(({ items }) => items.join(', ')),

// The same we do with the nodes
G.map(
({ firstName, lastName, age }) => ${lastName}, ${firstName} (${age})
),

// For debugging, we generate a simple dot file
G.toDotFile(MyIdCodec)((_) => _.toString())
)
),

// Depending on if the graph was valid
O.fold(
// We either print an error
() => console.error('invalid graph!'),

// Or output the dot file
console.log
)
);
`

If you have graphviz installed you can run the following in the terminal:

`bash
ts-node examples/debug-visually.ts | dot -Tsvg > graph.svg
chromium graph.svg
`

Roadmap / to do

- Add instances
- Functor
- Eq
- Ord
- Foldable
- ...
- Add functions
- deleteNode
- deleteEdge
- outgoingIds
- incomingIds
- mapEdgeWithIndex
- mapWithIndex
- topologicalSort
- ...
- Ideas
- Represent different qualities of a graph on the type level
Like: Graph<{directed: true, multiEdge: true, cyclic: false}, Id, Edge, Node>`