Skip to content

Algorithm to find a Minimum Path Cover of an arbitary DAG in JS/TS.

License

Notifications You must be signed in to change notification settings

TheDesignium/dagmpc-js

Repository files navigation

dagmpc: Algorithm to find a Minimum Path Cover of an arbitary DAG.

dagmpc provides a function which finds a minimum path cover of a DAG. This can't list all answers but finds an example. This works on both of browser and node.

Example Usage

Consider an DAG like this figure.

Example DAG

Input the number of node and the all edges to this library, like here:

import { minimumPathCover } from 'dagmpc';

const n = 7;
const edges = [
  [0, 3],
  [0, 4],
  [0, 5],
  [1, 0],
  [1, 3],
  [1, 4],
  [1, 5],
  [1, 6],
  [2, 3],
  [2, 4],
  [2, 5],
  [2, 6],
  [6, 4],
];

const paths = minimumPathCover(n, edges);
console.log(paths);

It outputs:

[[[1, 0, 3], [2, 5], [6, 4]]]

This means the calcurated MPC is the 3 paths, 1 -> 0 -> 3, 2 -> 5 and 6 -> 4. As figure:

Example MPC

Installation

npm i @thedesignium/dagmpc

Documentation

It is documented as JSDoc so read it through your editor, or read index.ts directly.