[Python] Combining topological sort with priority sort

I am writing a Python script that loads a bunch of tools from files to display in a menu. Each tool has a name and an order property, which further has the "other" string property and an int "value" property.

I am looking to combine these two values in sorting such that:

1. If other is None, the value is treated as an absolute priority, otherwise,
2. The tool is placed next to its dependency (other), if the value is negative, it goes before, otherwise it goes after
3. If multiple tools have the same dependency and side (sign of value), the magnitude of the value is used as a tie breaker, where larger values get placed further away from their dependency.
4. Nested dependencies very much exist (i.e. tool A wants to be after tool B, which wants to be before tool C)
5. Ideally if possible, unga bunga cyclic dependencies in (even if they're out of order) with a warning message, but that's more a wish than a requirement

I have successfully handled topological sorting, and priority sorting, but my brain is exploding trying to figure out how to combine the two together.

As a quick example, let's say I have:

class Tool:
name: str
order: Order

def __init__(name, order):
... # set values

class Order:
other: Optional[str]
value: int

def __init__(self, other, value):
... # set values

@staticmethod
def before(other, offset):
return Order(other, -100 - offset)

@staticmethod
def after(other, offset):
return Order(other, 100 + offset)

@staticmethod
def absolute(value):
return Order(None, value)

my_list = [
Tool("a", Order.absolute(0)),
Tool("b", Order.absolute(-10)),
Tool("c", Order.before("a", 1)),
Tool("d", Order.after("c", 1)),
Tool("e", Order.before("d"))
]

def my_sort(tools):
... # not sure how to implement this

my_sort(my_list) # expected: b, c, e, d, a


I tried several approaches.

1. 
   Naive approach where I create a dict with all absolute priority numbers spread out (*10000), and then for all dependencies assign a priority number that is dependent_value + value, but that of course ran into issues when nesting
   
   
2. 
   Retrofitting topo sort with a heapq, most of the time got wildly wrong results
   
   
3. 
   A few others not worth mentioning (or rather is embarrassing to)
   
   
4. 
   As a last resort seeing if GPT4o had any idea
   

Continue reading...