Menu
Given a list of classes inheriting from this base:
class Plugin(object):
run_after_plugins = ()
run_before_plugins = ()
...and the following rules:
Can anyone provide a nice clean algorithm for ordering a list of plugins? It will need to detect circular dependencies as well....
def order_plugins(plugins):
pass
I've come up with a few versions but nothing particuarlly neat: I'm sure some of you Art of Computer Programming types will relish the challenge :)
[note: question given in Python but it's clearly not only a Python question: pseudocode in any language would do]
351
Topological Sorting can be done by both DFS as well as BFS,this post however is concerned with the BFS approach of topological sorting popularly know as Khan's Algorithm.
The topological sort algorithm takes a directed graph and returns an array of the nodes where each node appears before all the nodes it points to. The ordering of the nodes in the array is called a topological ordering.
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.
Under the understanding that "topological" means "pertaining to shape", a "topological sort" simply means "a spacial sort."
This is called topological sorting.
The canonical application of topological sorting (topological order) is in scheduling a sequence of jobs or tasks; topological sorting algorithms were first studied in the early 1960s in the context of the PERT technique for scheduling in project management (Jarnagin 1960). The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes to dry). Then, a topological sort gives an order in which to perform the jobs.
54
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
