Resolving total-order using partial-orders

Resolving a total-order using partial-orders can be a tricky code to write. For an example, sorting can not be used because every pair can not be compared directly and doing it by enumerating through the list is also tricky. This is a common problem–among examples are Axis2 handler order resolution, build orders in ant/maven etc, and AI planning based use cases etc.

However, there is a standard way to solve this problem. The solution is creating a graph assigning dependencies as edges in a graph–which is a directed acyclic graph–and then doing a topology sort http://en.wikipedia.org/wiki/Topological_sort . The algorithm takes O(n) time and space where n is number of entities + number of rules, which is pretty reasonable.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s