Simple-digraph NPM

Simple Digraph

Library with utilities for directed graphs with numerical vertices.

Prerequisites

This project requires npm or yarn.

Usage

Sets

Empty Set

As a convenience, an empty set is available as a constant:

import { EMPTY_SET } from "simple-digraph";
console.log(EMPTY_SET);
// Set(0) {size: 0}

Subset/Superset

import {
  isProperSubsetOf,
  isProperSupersetOf,
  isSubsetOf,
  isSupersetOf,
} from "simple-digraph";
console.log(isSubsetOf(new Set([1]), new Set([1, 2, 3])));
// true
console.log(isSubsetOf(new Set([1, 2, 3]), new Set([1, 2, 3])));
// true
console.log(isProperSubsetOf(new Set([1]), new Set([1, 2, 3])));
// true
console.log(isProperSubsetOf(new Set([1, 2, 3]), new Set([1, 2, 3])));
// false
console.log(isSupersetOf(new Set([1, 2, 3]), new Set([1])));
// true
console.log(isSupersetOf(new Set([1, 2, 3]), new Set([1, 2, 3])));
// true
console.log(isProperSupersetOf(new Set([1, 2, 3]), new Set([1])));
// true
console.log(isProperSupersetOf(new Set([1, 2, 3]), new Set([1, 2, 3])));
// false

Union

import { union } from "simple-digraph";
console.log(union(new Set([1, 2]), new Set([2, 3]), new Set([4, 5])));
// Set(5) {1, 2, 3, 4, 5}

Intersection

import { intersection } from "simple-digraph";
console.log(intersection(new Set([1, 2]), new Set([1, 3]), new Set([1, 4])));
// Set(1) {1}

Difference

import { difference } from "simple-digraph";
console.log(difference(new Set([1, 2, 3]), new Set([3, 4, 5])));
// Set(2) {1, 2}

Graphs

Creating a Directed Graph

import { createGraph } from "simple-digraph";
const graph = createGraph(
  [
    [1, 2],
    [2, 3],
  ],
  new Set([4])
);
console.log(JSON.stringify([[...graph[0]], [...graph[1].values()]]));
// [[1,2,3,4],[[1,2],[2,3]]]

Creating a Directed, Acyclic Graph

A convenience method, createAcyclicGraph, will create a graph but throw an error if there are any cycles.

import { createAcyclicGraph } from "simple-digraph";
const graph = createAcyclicGraph([
  [1, 2],
  [2, 1],
]); // Throws error!

Detecting Cyclicity

import { isCyclic } from "simple-digraph";
const graph = createGraph([
  [1, 2],
  [2, 1],
]);
console.log(isCyclic(graph));
// true

Sinks/Sources

import { createGraph, sinks } from "simple-digraph";
const graph = createGraph([
  [1, 3],
  [2, 3],
]);
const terminals = sinks(graph);
console.log(terminals);
// Set(1) {3}
const initials = sources(graph);
console.log(initials);
// Set(2) {1, 2}

Subgraph

import { createGraph, subgraph } from "simple-digraph";
const graph = createGraph([
  [1, 3],
  [2, 3],
]);
const partial = subgraph(graph, new Set([1, 3]));
console.log(JSON.stringify([[...partial[0]], [...partial[1].values()]]));
// [[1,3],[[1,3]]]

Transitive Closure

import { createGraph, transitiveClosure } from "simple-digraph";
const graph = createGraph([
  [1, 2],
  [2, 3],
]);
const closure = transitiveClosure(graph, new Set([1, 3]));
console.log(JSON.stringify([[...closure[0]], [...closure[1].values()]]));
// [[1,2,3],[[1,2],[1,3],[2,3]]]

Transitive Reduction

import { createGraph, transitiveReduction } from "simple-digraph";
const graph = createGraph([
  [1, 2],
  [1, 3],
  [2, 3],
]);
const closure = transitiveReduction(graph, new Set([1, 3]));
console.log(JSON.stringify([[...closure[0]], [...closure[1].values()]]));
// [[1,2,3],[[1,2],[2,3]]]

Immediate Predecessors/Successors

import {
  createGraph,
  immediatePredecessors,
  immediateSuccessors,
} from "simple-digraph";
const graph = createGraph([
  [1, 3],
  [2, 3],
  [1, 4],
]);
const parents = immediatePredecessors(graph, new Set([3]));
console.log(parents);
// Set(2) {1, 2}
const children = immediateSuccessors(graph, new Set([1]));
console.log(children);
// Set(2) {3, 4}

Maximal/Minimal

Defined here and here.

import { maximal, minimal } from "simple-digraph";
const graph = createGraph([
  [1, 2],
  [1, 3],
]);
console.log(maximal(graph, graph[0]));
// Set(2) {2, 3}
console.log(minimal(graph, graph[0]));
// Set(1) {1}

Predecessor/Successor Union

Defined here and here.

import { predecessorUnion, successorUnion } from "simple-digraph";
const graph = createGraph([
  [1, 2],
  [1, 3],
]);
console.log(predecessorUnion(graph, new Set([2, 3])));
// Set(3) {1, 2, 3}
console.log(successorUnion(graph, new Set([2, 3])));
// Set(3) {2, 3}

Predecessor/Successor Intersection

Defined here and here.

import { predecessorIntersection, successorIntersection } from "simple-digraph";
const graph = createGraph([
  [1, 2],
  [1, 3],
]);
console.log(predecessorIntersection(graph, new Set([2, 3])));
// Set(1) {1}
console.log(successorIntersection(graph, new Set([2, 3])));
// Set(0) {size: 0}

Exclusive Predecessors

Defined here.

import { createGraph, exclusivePredecessors } from "simple-digraph";
const graph = createGraph([
  [1, 2],
  [1, 3],
]);
const parents = exclusivePredecessors(graph, new Set([2]), new Set([3]));
console.log(parents);
// Set(1) {2}