Monday, December 22, 2008

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.

No comments: