Skip to content

Latest commit

 

History

History
208 lines (154 loc) · 4.72 KB

README.md

File metadata and controls

208 lines (154 loc) · 4.72 KB
Raw

fp-ts-graph

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

type Graph<Id, Edge, Node> = ...
Quality y/n
directed yes
cyclic yes
multiple edges no

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

Table of Contents

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

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

Docs

API Docs

Examples

Define Types

// 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<string, string, string> = Cod.string;

// With this we can define a customized Graph type

export type MyGraph = Graph<MyId, MyEdge, MyNode>;

Build Graph

// 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<MyId, MyEdge, MyNode>();
const insertNode = G.insertNode(MyIdCodec);
const insertEdge = G.insertEdge(MyIdCodec);

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

export const myGraph: Option<MyGraph> = 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] }))
);

Debug graph visually

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

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>