Minimum Path Cover of an arbitary DAG.
dagmpc: Algorithm to find adagmpc 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.