I am trying to build a task scheduler that takes into account a task's priority and dependencies. The obvious solution for solving dependencies is the Topological sort Algorithm.
However, while incorporating priority into the solution I am thinking that the solution isn't optimal. A Python code for the rough implementation is shown here.
from collections import defaultdict
from queue import PriorityQueue
def topological_sort_with_priority(graph, priorities):
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
priority_queue = PriorityQueue()
for node in graph:
if in_degree[node] == 0:
priority_queue.put((priorities[node], node))
sorted_tasks = []
while not priority_queue.empty():
_, node = priority_queue.get()
sorted_tasks.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
priority_queue.put((priorities[neighbor], neighbor))
return sorted_tasks
They way it's implemented , each iteration scans the graph for nodes with no depencies and sorts these by inserting them in a priority queue .
Assuming a DAG t worst case There could be n iterations over the whole graph with the graph containing n vertices so the complexity and each insertion over the priority queue is log(m) -> m being the size of it, which should be bounded by (n) so at worst O((n^2) log(n)). The question is, is this approach correct, if so is it efficient?
Also are there reading materials on this? I tried searching for similar problems but didn't find resources on scheduling with dependencies and priority.