Sorting Tasks with Dependency and Priority

119 Views Asked by At

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.

0

There are 0 best solutions below