Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

batching-toposort

Package Overview
Dependencies
Maintainers
1
Versions
3
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

batching-toposort

Efficiently sort interdependent tasks into a sequence of concurrently-executable batches.

  • 1.2.0
  • latest
  • Source
  • npm
  • Socket score

Version published
Maintainers
1
Created
Source

Batching-Toposort

npm version Build Status code style: prettier

Efficiently sort interdependent tasks into a sequence of concurrently-executable batches.

batchingToposort :: { DependencyId : [DependentId] } -> [[TaskId]]
  • O(t + d) time complexity (for t tasks and d dependency relationships)
  • O(t) space complexity
  • Zero package dependencies
  • Thoroughly tested (including invariant tests)
  • Errors on cyclic graphs

Motivation

Often one needs to schedule interdependent tasks. In order to determine task order, the classic solution is to use topological sort. However, toposort typically outputs a list of individual tasks, without grouping those that can be executed concurrently. Batching-Toposort takes this additional consideration into account, producing a list of lists of tasks. The outer list is ordered; each inner list is unordered.

Usage

npm install batching-toposort

Batching-Toposort expects a directed acyclic graph (DAG) implemented via adjacency list. In other words, construct an object whose keys are dependency IDs, and whose values are lists of dependent IDs.

const batchingToposort = require('batching-toposort')

// DAG :: { DependencyId : [DependentId] }
const DAG = {
    a: ['c', 'f'], // `a` is a dependency of `c` and `f`
    b: ['d', 'e'],
    c: ['f'],
    d: ['f', 'g'],
    e: ['h'],
    f: ['i'],
    g: ['j'],
    h: ['j'],
    i: [],
    j: [],
}

// batchingToposort :: DAG -> [[TaskId]]
const taskBatches = batchingToposort(DAG)
// [['a', 'b'], ['c', 'd', 'e'], ['f', 'g', 'h'], ['i', 'j']]

(If there is demand, Batching-Toposort may one day include a small DAG API and/or DOT support for convenience, but as of now it is the developer's role to construct the graph.)

Implementation

In short, Batching-Toposort adapts Kahn's Algorithm by inserting each round of root tasks into sublists rather than appending tasks directly to the main output list.

The classic DAG toposort keeps track of each task's in-degree (number of dependencies). As root tasks (those with no dependencies) are added to the output list, their dependents' in-degree counts are decremented. For a task to become a root, all of its dependencies must have been accounted for. The core algorithm is illustrated below in pseudocode (the actual implementation is in src/index.js).

given G = adjacency list of tasks and dependents (~O(1) lookup):

let N = map from tasks to in-degree counts (~O(1) lookup / update)
let L = [] (empty output list) (~O(1) append)
let R1 = list of root tasks (~O(1) addition, ~O(n) iteration)

while R1 is nonempty
    append R1 to L
    let R2 = [] (empty list for next batch) (~O(1) append)
    for each task T in R1
        for each dependent D of T (as per G)
            decrement in-degree count for D (in N)
            if D's in-degree (as per N) is 0
                add D to R2
    R1 = R2

return L

Performance

The time complexity is O(|V| + |E|) for V task vertices and E dependency edges.

  • The algorithm loops through rounds of roots, and every task is only a root only once, contributing to O(|V|) rounds (worst case is a linked list of tasks).
  • Each round handles a disjoint set of dependency edges (those rooted in that round's tasks), so the O(|E|) handling of all edges is effectively distributed across rounds.
  • Other operations, e.g. querying a node's in-degree (average case O(1)), are carefully managed to preserve the time complexity.

The space complexity is slightly better at O(|V|).

  • The in-degree map size is proportional to the number of vertices |V|, but not edges, as those are folded into an integer count during map construction.
  • The output by definition contains |V| tasks (distributed among as many or fewer lists).
  • Again, other operations are controlled to keep space complexity low.

Keywords

FAQs

Package last updated on 16 Mar 2019

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc