Nectar of the Programming Masses

    simple-digraph
    TypeScript icon, indicating that this package has built-in type declarations

    1.0.1 • Public • Published

    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

    Install

    npm i simple-digraph

    DownloadsWeekly Downloads

    49

    Version

    1.0.1

    License

    MIT

    Unpacked Size

    32.3 kB

    Total Files

    64

    Last publish

    Collaborators

    • keesey