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}

Running the tests

To run unit tests, use:

yarn test

Linting

To check linting, use:

yarn lint

To fix some errors while linting, use:

yarn format && yarn lint --fix

Contributing

Please read CONTRIBUTING.md for details on our code of conduct, and the process for submitting pull requests to us.

Versioning

We use SemVer for versioning. For the versions available, see the tags on this repository.

Authors

• T. Michael Keesey - Creator - keesey

License

This project is licensed under the MIT License - see the LICENSE.md file for details