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.

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.