topological-sort
    TypeScript icon, indicating that this package has built-in type declarations

    0.3.0 • Public • Published

    Topological sort

    Greenkeeper badge Build Status DevDependency Status

    This package is distributed as Javascript, but you can also use it in your TypeScript project.

    API

    Javascript example

    const { TopologicalSort } = require('topological-sort');
     
    // you can pass nodes as a map into constructor:
    const nodes = new Map();
    nodes.set('variables', variablesObj);
    nodes.set('mixins', mixinsObj);
    const sortOp = new TopologicalSort(nodes);
     
    // ...or add them to existing object instance with addNode() or addNodes():
    sortOp.addNode('block', blocksObj);
    sortOp.addNodes(new Map([
        ['block_mod_val1', blockModObj1],
        ['block_mod_val2', blockModObj2]
    ]));
     
    // then you should add adges between nodes
    sortOp.addEdge('variables', 'mixins'); // from, to
    sortOp.addEdge('mixins', 'block');
    sortOp.addEdge('variables', 'block');
    sortOp.addEdge('block', 'block_mod_val2');
    sortOp.addEdge('block', 'block_mod_val1');
     
    // sorting is simple: it returns a new map wih sorted elements
    // if circular dependency is found, sort() operation throws an AssertionError
    const sorted = sortOp.sort();
    const sortedKeys = [...sorted.keys()]; // ['variables', 'mixins', 'block', 'block_mod_val1', 'block_mod_val2']
     
    // values of the `sorted` map are objects with this shape: `{ children, node }`
    // where node is the node object that you provided
    // and children is a map which values have the same shape
    const { node: variablesObj, children: variablesChildren } = sorted.get('variables');
    const { node: blocksObj1 } = variablesChildren.get('block');
    const { node: blocksObj2 } = sorted.get('block');
    assert(blocksObj1 === blocksObj2); // true

    Typescript example

    import TopologicalSort from 'topological-sort';
     
    // TopologicalSort class instances have a map inside.
    // This map stores the references between your nodes (edges)
    // "NodesKeyType" is the type for your tree node identifiers
    // "NodesValueType" is the type for your tree nodes
    const nodes = new Map<NodesKeyType, NodesValueType>();
    nodes.set('variables', variablesObj);
    nodes.set('mixins', mixinsObj);
    const sortOp = new TopologicalSort<NodesKeyType, NodesValueType>(nodes);
     
    // `sortedKeys` is a topologically sorted list of node keys
    sortOp.addEdge('variables', 'mixins');
    const sorted = sortOp.sort();
    const sortedKeys = [...sorted.keys()]; // ['variables', 'mixins']
     
    // `sorted` contains all nodes and their children
    const { node: variablesObj, children: variablesChildren } = sorted.get('variables');
    const { node: blocksObj1 } = variablesChildren.get('block');
    const { node: blocksObj2 } = sorted.get('block');
    assert(blocksObj1 === blocksObj2); // true

    More info:

    Install

    npm i topological-sort

    DownloadsWeekly Downloads

    34,394

    Version

    0.3.0

    License

    MIT

    Unpacked Size

    45.1 kB

    Total Files

    16

    Last publish

    Collaborators

    • 1999