I have a list of tasks that are inter-dependent:

let tasks = {
  a: {
    job: function () {
      console.log('Tasks A running')
    },
    dependency: ['c', 'b'],
  },
  b: {
    job: function () {
      console.log('Tasks B running')
    },
    dependency: [],
  },
  c: {
    job: function () {
      console.log('Tasks C running')
    },
    dependency: ['b'],
  },
}

The idea is that we should first run the task that with no dependency, which b in this case, and once it runs, we run c which depends on b and then finally we run a.

The solution I came up with is

function runTasks(tasks) {
  while (Object.keys(tasks).length) {
    for (let [key, { dependency, job }] of Object.entries(tasks)) {
      if (dependency.length === 0) {
        job()
        deleteAllOccurance(tasks, key)
        delete tasks[key]
      }
    }
  }
}

function deleteAllOccurance(tasks, name) {
  for (let [key, { dependency }] of Object.entries(tasks)) {
    tasks[key].dependency = dependency.filter((x) => x !== name)
  }
}
runTasks(tasks)

It worked but I think it is not ideal:

1. I mutated the original tasks object
2. it might be slow because for every time we need to find all the occurrences in other tasks' dependency lists.

Therefore I am trying to find a better solution here.

CodePudding user response：

I'd do it this way:

function runTasks(tasks) {
  const done = {};
  const execute = (name) => {
    if (!done[name]) {
      const {dependency, job} = tasks[name];
      dependency.forEach(execute);
      job();
      done[name] = true;
    }
  }
  for (const name in tasks) {
    execute(name);
  }
}

It's easy to see that this algorithm will execute each task exactly once, and dependencies before the jobs themselves.

The time complexity is O(t d), where t is the number of tasks, and d the total number of dependencies. Your code is O(t td).

For instance, if we look at the worst possible dependency graph, where a task depends on all previous tasks, d = t*(t-1)/2, making my algorithm O(t^2), but yours O(t^3). Or if we look at a minimal dependency graph, where each tasks depends on a single previous task, d = t-1, making my algorithm O(t), but yours O(t^2).

Also, if the dependency graph were to contain a cycle, my code throws an error, while your code would loop forever.

CodePudding user response：

One possibility would be to have a recursive function that identifies an available task, runs it, and adds its key to the finished pile. Then, that key can be removed from the object and it can recursively call itself.

let tasks={a:{job:function(){console.log("Tasks A running")},dependency:["c","b"]},b:{job:function(){console.log("Tasks B running")},dependency:[]},c:{job:function(){console.log("Tasks C running")},dependency:["b"]}};

const findTask = (tasks, done = new Set()) => {
  const result = Object.entries(tasks)
    .find(([, task]) => task.dependency.every(dep => done.has(dep)))
  if (!result) {
    // done
    return;
  }
  const [key, { job }] = result;
  job();
  done.add(key);
  const { [key]: _, ...restTasks } = tasks;
  findTask(restTasks, done);
};
findTask(tasks)

You could also invert the dependencies by mapping each possible subtask for a task object directly onto that task object. That way, you only need to iterate over the possible subtasks for one task to see which of them have had all dependencies fulfilled, rather than over the entire input array.

This way, for example, given

  a: {
    dependency: ['c', 'b'],
  },
  b: {
    dependency: [],
  },
  c: {
    dependency: ['b'],
  }

you could first construct

  b: {
    dependants: ['a', 'c'],
  }, c: {
    dependants: ['a']
  }

and then, upon completing b (for example), search through only a and c to see if either of them are ready.

This could be a lot faster if the input is large, but requires some nontrivial setup ahead of time.

let tasks={a:{job:function(){console.log("Tasks A running")},dependency:["c","b"]},b:{job:function(){console.log("Tasks B running")},dependency:[]},c:{job:function(){console.log("Tasks C running")},dependency:["b"]}};

const dependentsByTask = {};
for (const [key, { dependency }] of Object.entries(tasks)) {
  for (const dependent of dependency) {
    dependentsByTask[dependent] ??= [];
    dependentsByTask[dependent].push(key);
  }
}
const tasksWithDependants = Object.fromEntries(
  Object.entries(tasks).map(
    ([key, task]) => [key, { ...task, dependantsKeys: dependentsByTask[key], id: key }]
  )
);
for (const task of Object.values(tasksWithDependants)) {
  task.dependants = (task.dependantsKeys || []).map(key => tasksWithDependants[key]);
}
const linkedTasksWithDependants = Object.values(tasksWithDependants);
const tryRunTask = (task, done = new Set()) => {
  if (!task.dependency.every(key => done.has(key))) {
    return;
  }
  task.job();
  done.add(task.id)
  for (const subtask of task.dependants) {
    tryRunTask(subtask, done);
  }
};
tryRunTask(linkedTasksWithDependants.find(task => (!task.dependency.length)));

CodePudding user response：

const pending = new Set(Object.keys(tasks))

while (pending.size)
    for (const p of pending)
        if (!tasks[p].dependency.some(d => pending.has(d))) {
            tasks[p].job()
            pending.delete(p)
        }

CodePudding user response：

Just run them all, recurse on dependencies, and memoise the results:

const tasks={a:{job:function(){console.log("Tasks A running")},dependency:["c","b"]},b:{job:function(){console.log("Tasks B running")},dependency:[]},c:{job:function(){console.log("Tasks C running")},dependency:["b"]}};

const done = new Set();
function run(name) {
  if (done.has(name)) return;
  done.add(name);
  const task = tasks[name];
  for (const dep of task.dependency) run(dep);
  task.job();
}
for (const name in tasks) run(name);

You can extend this to detect circular dependencies and throw an exception.