@kingjs/poset.for-each

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

Stats

StarsIssuesVersionUpdatedCreatedSize
@kingjs/poset.for-each
1.0.143 years ago3 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

  • AdjacencyList: see @kingjs/poset

    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

If you find any bugs or have a feature request, please open an issue on github!

The npm package download data comes from npm's download counts api and package details come from npms.io.