Simple utilities for processing directed graphs with numerical vertices.
npm install simple-digraphLibrary with utilities for directed graphs with numerical vertices.
This project requires npm or yarn.
As a convenience, an empty set is available as a constant:
``javascript`
import { EMPTY_SET } from "simple-digraph";
console.log(EMPTY_SET);
// Set(0) {size: 0}
#### Subset/Superset
`javascript`
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
`javascript`
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
`javascript`
import { intersection } from "simple-digraph";
console.log(intersection(new Set([1, 2]), new Set([1, 3]), new Set([1, 4])));
// Set(1) {1}
#### Difference
`javascript`
import { difference } from "simple-digraph";
console.log(difference(new Set([1, 2, 3]), new Set([3, 4, 5])));
// Set(2) {1, 2}
#### Creating a Directed Graph
`javascript`
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.
`javascript`
import { createAcyclicGraph } from "simple-digraph";
const graph = createAcyclicGraph([
[1, 2],
[2, 1],
]); // Throws error!
#### Detecting Cyclicity
`javascript`
import { isCyclic } from "simple-digraph";
const graph = createGraph([
[1, 2],
[2, 1],
]);
console.log(isCyclic(graph));
// true
#### Sinks/Sources
`javascript`
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
`javascript`
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
`javascript`
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
`javascript`
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
`javascript`
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
`javascript`
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
`javascript`
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
`javascript`
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.
`javascript`
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}
To run unit tests, use:
`shell`
yarn test
To check linting, use:
`shell`
yarn lint
To fix some errors while linting, use:
`shell``
yarn format && yarn lint --fix
Please read CONTRIBUTING.md for details on our code of conduct, and the process for submitting pull requests to us.
We use SemVer for versioning. For the versions available, see the tags on this repository.
- T. Michael Keesey - _Creator_ - keesey
This project is licensed under the MIT License - see the LICENSE.md file for details