Solved

Looking for information about a kind of partial ordering

Posted on 2004-08-20
5
366 Views
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?
0
Comment
Question by:NovaDenizen
  • 2
  • 2
5 Comments
 
LVL 2

Expert Comment

by:kouroshparsa
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...
0
 

Expert Comment

by:Claudix
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 :
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm

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
0
 
LVL 22

Author Comment

by:NovaDenizen
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.



0
 

Accepted Solution

by:
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
0
 
LVL 22

Author Comment

by:NovaDenizen
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.
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
withoutTen challenge 14 88
topping2 challenge 13 59
topping3 challenge 14 50
How  do I get an older program to run in Windows 10? 20 80
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
This article will show, step by step, how to integrate R code into a R Sweave document
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

758 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now