У меня есть класс, подобный Foo ниже, который имеет атрибут «depends_on», который представляет собой массив других экземпляров Foo. Я хотел бы иметь возможность взять список Foos и отсортировать их так, чтобы foo, который зависит от другого foo, был больше, чем он. Например, если foo b зависит от foo a, массив должен быть в порядке [a,b]. Я подумал, что было бы лучше дать каждому foo поле order и сортировать по этому полю, а не использовать __lt__.
class Foo(object):
def __init__(self, name, depends_on=[]):
self.order = 0
self.name = name
self.depends_on = depends_on
a = Foo('a')
b = Foo('b', [a])
c = Foo('c', [b])
d = Foo('d')
e = Foo('e')
f = Foo('f', [e])
g = Foo('g', [f, b])
foos = [a,b,c,d,e,f,g]
Я сделал рекурсивную функцию, подобную этой, и она работает, но я думаю, что есть лучший способ.
При первом проходе я сравниваю каждый объект в массиве друг с другом. Если объект x зависит от объекта y, я увеличиваю поле order объекта x на единицу.
На втором проходе я сравниваю только foos с order больше или равным 1; т. е. foo, которые зависят по крайней мере от одного другого foo. Опять же, я увеличиваю поле order этого подмножества foos, если они зависят друг от друга.
Я продолжаю этот шаблон до тех пор, пока не останется больше сравнений.
def recursive_order(order=0):
compared = 0
for fooa in [foo for foo in foos if foo.order >= order]:
for foob in [foo for foo in foos if foo.order >= order]:
compared += 1
if fooa in foob.depends_on:
foob.order += 1
if compared == 0:
return
recursive_order(order + 1)
recursive_order()
foos.sort(key=lambda foo: foo.order)
print [(foo.name, foo.order) for foo in foos]
[('a', 0), ('d', 0), ('e', 0), ('b', 1), ('f', 1), ('c', 2), ('g', 2)]
Мне нужен список foo, учитывающий "порядок зависимости". Например, foo a и foo b не имеют зависимостей и поэтому равны. Foo b зависит от Foo a, поэтому foo a ‹ foo b ([a,b]. Foo c зависит от Foo b, поэтому [a,b,c].
Изменить
Спасибо Мартину Питерсу за ссылку на топологическую сортировку. Вот моя реализация:
def topological_sort(foos):
provided = set()
while foos:
remaining_foos = []
emitted = False
for foo in foos:
if set(foo.depends_on).issubset(provided):
yield foo
provided.add(foo)
emitted = True
else:
remaining_foos.append(foo)
if not emitted:
raise raise ValueError("cyclic dependency detected")
foos = remaining_foos
print [foo.name for foo in topological_sort(foos)]
['e', 'd', 'a', 'f', 'b', 'g', 'c']
