@kingjs/poset.for-each

Perform a depth first walk of a poset expressed as an adjacency list.

Downloads in past

Stats

StarsIssuesVersionUpdatedCreatedSize
@kingjs/poset.for-each
081.0.144 years ago4 years agoMinified + gzip package size for @kingjs/poset.for-each in KB

Readme

@kingjs/poset.for-each
Invokes a callback on vertices of a poset such that dependent vertices are called back first.

Usage

Given a poset where 'a' depends on 'b' and 'c' which, in turn, both depend on 'd' generate a total ordering like this:
var forEach = require('@kingjs/poset.for-each');

//    a
//   / \
//  b   c
//   \ /
//    d
var poset = {
  a: [ 'b', 'c' ],
  b: [ 'd' ],
  c: [ 'd' ]
};

var totalOrder = [];

forEach.call(poset, function(vertex) {
  totalOrder.push(vertex);
});

totalOrder;
result:
[ 'd', 'b', 'c', 'a' ] 
// or
[ 'd', 'c', 'b', 'a' ]

API

declare function forEach(
  this: AdjacencyList,
  action: (vertex) => void,
  roots?: string | string[]
)

Interfaces

Parameters

  • this: A poset expressed as an descriptor where each property represents a named vertex and each property value is an array of strings each representing the name of adjacent vertices.
  • action: Action to take when visiting a vertex.
- vertex: The name of the vertex being visited.
  • roots: The vertex or vertices from which to commence the traversal. If none are provided, all vertices are used as roots.

Remarks

If a cycle is detected, then an exception is thrown listing the vertices involved in the cycle.
Algorithm will randomly decide the direction to traverse the adjacency vertices. This helps callers ensure they only rely on dependencies defined in the adjacency list and not on dependencies that are artifacts of its expression. This is why the example in the usage section may generate two different results.

Install

With npm installed, run
$ npm install @kingjs/poset.for-each

License

MIT
Analytics
poset: https://www.npmjs.com/package/@kingjs/poset adjacency list:(https://en.wikipedia.org/wiki/Adjacencylist