Solved
Looking for information about a kind of partial ordering
Posted on 2004-08-20
This is a very Computer-Science-type question. I'm looking for information about algorithms, data structures, books, and implementation techniques to help me efficiently create what I call a minimal partial ordering graph, explained below.
I have a bunch of objects (say, 50 thousand) and a partial ordering function. I want to find the minimal partial ordering graph for all of these objects. I want to get the objects organized in terms of the partial ordering function.
Partial ordering function: f(a_i,a_j) that returns '+' if a_i exceeds a_j, '-' if a_j exceeds a_i, and '?' if there is no sure ordering between a_i and a_j. This function has the transitive and reflexive properties you would expect from a comparison function (f(a,a) == '?', f(a,b)=='+' and f(b,c)=='+' implies f(a,c)=='+', f(a,b)=='?' iff f(b,a)=='?', f(a,b)=='+' iff f(b,a)=='-')
Partial ordering graph: A directed acyclic graph that completely reflects the partial ordering function. You can brute-force construct a valid one in O(n^2) space and time by performing the ordering function on all pairs of objects, adding an edge (a,b) whenever f(a,b)=='+'.
Minimal partial ordering graph: A partial ordering graph with all redundant edges removed. For instance, if the edges (a,b), (b,c), and (a,c) are in a partial ordering graph, the (a,c) edge is redundant because you can deduce it from the transitive property.
Creating a minimal PO graph is obviously brute-forceable in O(n^3) time and O(n^2) space, but I suspect it can be done faster than O(n^2) and with space proportional to the number of edges in the minimal graph. I would also like to efficiently remove nodes from and add nodes to a minimal graph.
Is this unexplored territory, or has someone already solved this problem? Should I be thinking about this problem in a different way?