Security News
Supply Chain Attack Detected in Solana's web3.js Library
A supply chain attack has been detected in versions 1.95.6 and 1.95.7 of the popular @solana/web3.js library.
batching-toposort
Advanced tools
Efficiently sort interdependent tasks into a sequence of concurrently-executable batches.
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 complexityOften 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.
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.)
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
The time complexity is O(|V| + |E|)
for V
task vertices and E
dependency edges.
O(|V|)
rounds (worst case is a linked list of tasks).O(|E|)
handling of all edges is effectively distributed across rounds.O(1)
), are carefully managed to preserve the time complexity.The space complexity is slightly better at O(|V|)
.
|V|
, but not edges, as those are folded into an integer count during map construction.|V|
tasks (distributed among as many or fewer lists).FAQs
Efficiently sort interdependent tasks into a sequence of concurrently-executable batches.
We found that batching-toposort demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
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.
Security News
A supply chain attack has been detected in versions 1.95.6 and 1.95.7 of the popular @solana/web3.js library.
Research
Security News
A malicious npm package targets Solana developers, rerouting funds in 2% of transactions to a hardcoded address.
Security News
Research
Socket researchers have discovered malicious npm packages targeting crypto developers, stealing credentials and wallet data using spyware delivered through typosquats of popular cryptographic libraries.