5
Cho một danh sách các lớp kế thừa từ cơ sở này:Thuật toán sạch để sắp xếp một đối tượng theo các phụ thuộc được xác định?
class Plugin(object):
run_after_plugins =()
run_before_plugins =()
... và các quy tắc sau:
- Plugins có thể cung cấp một danh sách các plugin rằng họ phải chạy sau.
- Plugin có thể cung cấp danh sách plugin mà họ phải chạy trước đó.
- Danh sách các plugin có thể chứa hoặc không chứa tất cả các plugin đã được chỉ định trong các ràng buộc đặt hàng.
Có ai có thể cung cấp thuật toán sạch đẹp để đặt hàng danh sách plugin không? Nó sẽ cần phải phát hiện phụ thuộc vòng tròn cũng ....
def order_plugins(plugins):
pass
Tôi đã đưa ra một vài phiên bản nhưng không particuarlly gọn gàng: Tôi chắc chắn một số bạn Art of Computer Programming loại sẽ thích thử thách :)
[lưu ý: câu hỏi được đưa ra bằng Python nhưng rõ ràng không chỉ là một câu hỏi Python: mã giả trong bất kỳ ngôn ngữ nào sẽ làm]
@Eli: Tôi đã tìm thấy câu hỏi này (http://stackoverflow.com/questions/952302/how-to-sort-based-on-dependencies) đã đề cập đến loại sắp xếp đó ngay bây giờ nhưng ví dụ đã cho không có hai loại phụ thuộc riêng biệt cần được sắp xếp: có thể xử lý được trường hợp này không? – jkp
@jkp: nó có thể được chuyển đổi thành biểu diễn đó. tức là A nói rằng B phải chạy trước nó, nhưng C sau đó. Vì vậy, chỉ với các ràng buộc "sau", chúng tôi nói rằng A là sau B và C là sau A. –
@Eli: haha! vâng, tôi đoán khi bạn bật nó lên đầu của nó như thế nó được áp dụng một cách sạch sẽ. A trước khi ràng buộc trên một plugin chỉ là một ràng buộc sau cho một plugin khác :) – jkp