Cách sắp xếp dựa trên phụ thuộc?

Question

Tôi có một lớp có danh sách "phụ thuộc" trỏ đến các lớp khác thuộc cùng một loại cơ sở.

class Foo(Base): 
    dependencies = [] 

class Bar(Base): 
    dependencies = [Foo] 

class Baz(Base): 
    dependencies = [Bar] 

Tôi muốn sắp xếp các trường hợp mà các lớp này tạo dựa trên phụ thuộc của chúng. Trong ví dụ của tôi, tôi mong đợi các trường hợp của Foo đến trước, sau đó là Bar, sau đó là Baz.

Cách tốt nhất để sắp xếp điều này là gì?

Answer 1

Nó được gọi là một loại topo.

def sort_deps(objs): 
    queue = [objs with no dependencies] 
    while queue: 
     obj = queue.pop() 
     yield obj 
     for obj in objs: 
      if dependencies are now satisfied: 
       queue.append(obj) 
    if not all dependencies are satisfied: 
     error 
    return result 

Answer 2

Tôi đã có câu hỏi tương tự chỉ tuần trước - tôi muốn biết về Stack Overflow! Tôi săn lùng xung quanh một chút cho đến khi tôi nhận ra rằng tôi có một số DAG (Được chỉ định Tuần hoàn Đồ thị vì phụ thuộc của tôi không thể đệ quy hoặc tròn). Sau đó, tôi tìm thấy một vài tài liệu tham khảo cho các thuật toán để sắp xếp chúng. Tôi đã sử dụng một traversal chiều sâu đầu tiên để có được các nút lá và thêm chúng vào danh sách được sắp xếp đầu tiên.

Dưới đây là một trang mà tôi thấy hữu ích:

Directed Acyclic Graphs