topo-kahn

!npm bundle size
!NPM
!npm

Topological sort (Kahn algorithm) an oriented graph containing any kind of node, using ES6 Maps & Sets.

Examples

let's start with some family members :

``js
import sort, { reverseMatrix } from topo-kahn ;

const g = { name: "George" };
const mt = { name: "Marie-Thérèse" };
const p = { name: "Patrice" };
const j = { name: "Josette" };
const pj = { name: "Pierre-Jean" };
const m = { name: "Mathias" };
const pandj = new Set([p, j]);

...
`

$3

`js
...

const parents = new Map([
[m, pandj],
[g, null],
[pj, pandj],
[mt, null],
[p, new Set([g, mt])],
[j, null],
]);

const sorted = sort(parents); // sorted = new Set([g, mt, j, p, pj, m]);
`

$3

`js
...

const family = new Set([m, g, pj, mt, p, j]);

const getParents = member => {
switch (member) {
case m:
return pandj;
case g:
return null;
case pj:
return pandj;
case mt:
return null;
case p:
return new Set([g, mt]);
case j:
default:
return null;
}
};

const sorted = sort(family, { generator: getParents }); // same result !
`

$3

`js
// reverseMatrix is a util function provided by this package
const sorted = sort(reverseMatrix(parents), { type: 'children' }); // same result !

// or

const sorted = sort(family, { generator: getChildren, type: 'children' }); // same result !
`

FAQ

- Why should I use it ?
- If you like this way to express a graph
- Or if you already have a function that defines dependencies between nodes
- If you want / need to define any kind of node (objects, strings, numbers, ...) by using ES6 Maps & Sets
- What if there's a loop in my graph ? topo-kahn will throw an error
- What if I have a matrix containing node's children, and not parents ? Just pass a type option set to children

`js
import sort from topo-kahn ;

const sorted = sort(children, { type: 'children' });
// eq. to const sorted = sort(parents);
`

Reverse a matrix

topo-kahn exports a specific function called reverseMatrix` if you need to.