@okcontract/graph

graph, a small directed graph library

Graph is a simple directed graph library with no runtime dependency written in TypeScript, that provides:

• Ability to add and remove node and edges
• (Partial) topological sort
• Cache paths for cases with (much) more reads than writes
• Export to graphviz .dot files

Walkthrough

import { Graph } from "@okcontract/graph";

// nodes are strings
let graph = new Graph<string>();

// add nodes and edges
graph.addNode("a");
graph.addNode("b");
graph.addNode("c");
graph.addNode("d");
graph.addEdge("a", "b");
graph.addEdge("b", "c");
graph.addEdge("c", "d");

// partial topological sort for node "a"
expect(graph.partialTopologicalSort("a")).toEqual(["d", "c", "b", "a"]);

// generate dot graph, with optional types and styles for each node type
console.log(
  graph.toDot(
    {
      string: ["a", "d"],
      number: ["b"],
      object: ["c"]
    },
    {
      string: "style=filled,fillcolor=aquamarine",
      number: "style=filled,fillcolor=gold",
      object: "style=filled,fillcolor=hotpink"
    }
  )
);

About

graph is written by the team at OKcontract and is released under the MIT license.

We aim for ease of use and correction. Chasing down any bug is our top priority.

Contributors are welcome, feel free to submit PRs directly for small changes. You can also reach out in our Discord or contact us on Twitter in advance for larger contributions.

This work is supported in part by a RFG grant from Optimism.

Development

Building and testing graph requires a system installation of bun. Bun is deliberately not included in the project's dependencies.

bun install --frozen-lockfile
bun run test
bun run build
bun run definitions

biome is also deliberately not included as a project dependency. Install it as a system binary to run bun run format or bun run check. The standard bun run build script formats the source before bundling, so it also expects biome to be available on PATH; direct use of bun build does not require Biome.