@thedesignium/dagmpc
v1.0.4
Published
Algorithm to find a [Minimum Path Cover](https://en.wikipedia.org/wiki/Path_cover) of an arbitary DAG.
Downloads
1
Maintainers
Readme
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 find an example. This works on both of browser and node.
Example Usage
Consider an DAG like this figure.
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:
Installation
npm i @thedesignium/dagmpc
Documentation
It is documented as JSDoc so read it through your editor, or read index.ts directly.