Looking for information about a kind of partial ordering

Posted on 2004-08-20
Last Modified: 2012-08-13
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?
Question by:NovaDenizen
  • 2
  • 2

Expert Comment

ID: 11857031
I'm not sure what you want in what programming language. What type of objects? If you know the basics, and you're looking for a solution...Well
I have had similar projects with functions...
Let's say you're comparing f(a,b) and f(d,e)
if you read it as a string from index=2 to just before ")" you'll get:   a,b     and     d,e
Now, if you remove commas:  ab       and     de
Then you can compare them as strings...

The similar thing goes with f(a_i,a_j)... by removing "_"
I personally analyse or derive mathematics or physics functions using strings...

Expert Comment

ID: 11858030
What you are talking about is actually topological sort
which can be done in time proportional to O(V+E)
which could mean n^2 if you have the number
of edges(E) close to n^2

here is a quick link :

Now about the graph.You can get the edges you don't need off using
depth first search and the edge classification it produces like
this following book explains

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms

the basic summary is that you remove the edges that span from a node ,from the
tree you build there, to its descendent
LVL 22

Author Comment

ID: 11862003
kouroshparsa:  I don't think you get the question very well.

Claudix:  You're close, but I don't think I made myself quite clear enough.  My problem is closely related to topological sorts, except coming from the opposite direction.  

I have a bunch of nodes, and a comparison function that tells me whether a node is greater than, less than, or of indeterminate comparison with another node.  I want to use the information I get from the comparison function to efficiently build a minimal directed acyclic graph, "efficiently" being the most important term.


Accepted Solution

Claudix earned 500 total points
ID: 11863706
Well, if calling f is expensive and you want to get the minimal graph without
constructing the hole graph in the first place you can build it incrementally:

you have a directed graph where an edge means a>b and the inverted graph
where an edge means a>b(you'll see where you need this one)

you made the minimal graph out of the first n nodes
now you want to get the n+1th in there
here is how you do it with the fewest calls to f():

1)you call f(i,n+1) until you get a + or -
you insert n+1 according to this in each graph
(the normal and the inverted one)

2)you depth first in each graph starting with n+1 and through the
edge you just entered (from n+1 to i) to find out for which nodes you need not
call f(j,n+1) for and you keep them in a vector( callFor[ j ] = 0 )
(if you find a path between n and k you know their relationship is
+ or - so you don't need to call f() for them again)

3)you start iterating i from where you left off in step 1(or 3) checking to see
if you need to call f ( callFor [ i ] != 0 ) until you get + or -
then you insert your new edge between i and n+1 an go to step 2

4) you go to the next node you need to process

one optimisation to step 2 is that if you find callFor[ j ] = 0  you
never need to continue a DF started in node n+1 that reaches node j again

I'm not sure this gets you the minimal graph I'll let you check that
LVL 22

Author Comment

ID: 11884369
Actually, f is quite cheap.   Not that that matters in terms of O() notation.  

I don't think your algorithm will keep a graph minimal.   I think I have found an N^2 algorithm inspired by yours, though.  That DFS can be pretty useful.

Each node must have a "dfsID" field, which will contain the index of the originating node from the last time a DFS search traversed this node.

This is an insertion algorithm for a new node going into a minimal graph.  New node is node n+1

// This loop is O(n+edges) because, in total, the DFS's will iterate over at most all existing nodes and edges.  Marking the dfsIDs keeps the DFS from doing redundant work
for i = 1 to n {
    if node i dfsID == n+1 then next i
    if f(n+1, i) == '+' {
        if node i dfsID != n+1 {
            DFS in the '-' direction from node i.  If any node j traversed already has its dfsID==n+1, then remove edge (j, n+1) if it exists and don't continue the DFS down this node.  Set dfsID on each traversed node to n+1.
            add edge (i, n+1)
    } else if f(n+1,i) == '-' {
        if node i dfsID != n+1 {
              DFS in the '+' direction from node i.  If any node j traversed already has its dfsID==n+1, then remove edge (n+1, j) if it exists and don't continue the DFS down this node.  Set dfsID on each traversed node to n+1.
               add edge(n+1, i)

// since none of the nodes < n+1 should be pointing directly at nodes > n+1, get rid of those edges.  This loop is <= O(nodes + edges)
for all i such that edge (i, n+1) exists {
        remove all edges (i, j) where node j dfsID == (n+1)

The removal algorithm is tricky, and can take longer than O(n+edges), something like O((# of predecessors i such that edge(i, r) exists)*(avg. # nodes of indeterminate comparison to r and greater than some predecessors)), not counting the set operations.  To remove node r:
Create set A of all nodes such that edge (a, r) exists.
Create set B of all nodes such that edge (r, b) exists.
DFS from all nodes in B, in the '+' direction, and mark these nodes 'out of bounds'
Remove all edges (i,r) and (r,i)
For all a in set A {
    let set T = B
    dfs from a in the '+' direction.  When a traversed node j is in set T, remove j from set T.  do not traverse 'out of bounds' nodes.
    for all nodes t left in set T, add edge (a, t)

I've got a couple other ideas that might bring the insertion below O(n) or the wholesale creation of the graph below O(n^2), but I'll have to actually implement them to see if they work OK.  Thanks for your help.

Featured Post

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
groupSum6 challenge 6 114
Looking for a network enabled locker remotely controlled like Amazon locker 2 103
Generate Unique ID in VB.NET 21 104
batch file or script 4 50
Does the idea of dealing with bits scare or confuse you? Does it seem like a waste of time in an age where we all have terabytes of storage? If so, you're missing out on one of the core tools in every professional programmer's toolbox. Learn how to …
Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…

726 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question