Published
Edited
Jul 14, 2020
1 fork
8 stars
tasks = [1, 2, 3, 4, 5, 6, 7, 8]
dependencies = [[1, 3], [2, 3], [2, 4], [3, 4], [5, 2], [8, 2], [6, 7], [6, 3]]
topologicalSort(tasks, dependencies)
topologicalSort([1, 2, 3, 4], [[1, 3], [2, 3], [2, 4], [3, 4]])
function topologicalSort(tasks, deps) {
const taskToDeps = deps.reduce((acc, curr) => {
const [dep, task] = curr;
if (!acc.has(task)) {
acc.set(task, new Set([dep]));
} else {
acc.get(task).add(dep);
}
return acc;
}, new Map());
const depToTasks = deps.reduce((acc, curr) => {
const [dep, task] = curr;
if (!acc.has(dep)) {
acc.set(dep, new Set([task]));
} else {
acc.get(dep).add(task);
}
return acc;
}, new Map());
const tasksSet = new Set(tasks);
const tasksWithoutDependencies = Array.from(tasksSet).flatMap(task =>
taskToDeps.has(task) ? [] : task
);
let order = [];
while (order.length !== tasksSet.size) {
if (!tasksWithoutDependencies.length) {
return [];
}
const task = tasksWithoutDependencies.pop();
order.push(task);
if (depToTasks.has(task)) {
for (let taskToUpdate of depToTasks.get(task)) {
depToTasks.get(task).delete(taskToUpdate);
taskToDeps.get(taskToUpdate).delete(task);
if (!taskToDeps.get(taskToUpdate).size) {
tasksWithoutDependencies.push(taskToUpdate);
taskToDeps.delete(taskToUpdate);
}
}
depToTasks.delete(task);
}
}
return order;
}
d3 = {
const d3_base = await require('d3');
const d3_dag = await require('d3-dag@0.3.0');
return Object.assign({}, d3_base, d3_dag);
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
