Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Help needed: Is Quick-Union-Find the right solution to this problem ?

Reply
Thread Tools

Help needed: Is Quick-Union-Find the right solution to this problem ?

 
 
aredo3604gif@yahoo.com
Guest
Posts: n/a
 
      04-11-2005
The user can dynamically enter and change the rule connection between
objects. The rule is a "<" and so given two objects:
a < b simply means that b < a can't be set, also it must be a != b.
And with three objects a < b , b < c means a < c

I studied Quick Union Find algorithms a bit and if I understood them
correctly, once the user gives the input setting the rules/connection
between objects, the algorithm will give as output the result of the
solved connections between objects.

As far as I check on the array or given list of objects from user
input that it's never added anything like a = b nor b<a when a<b it's
already in the list, would it work as expected so that I know which
objects in the list are "the strongest" ones as per user given rules ?

I tried thinking about using simple logic like AND,OR,XOR of compare
results values but I couldn't find a way to ensure that the
transitivity rule could be mantained.

So, is a DAG or Quick Union Find the way to go ?

My only concern about Quick Union Find is that it constructs a graph
with a single highest level root like a tree, right ? But if I am not
wrong the user could set things in such a way that the graph would
have more than one "root" .. ?!

Someone please help me to understand what's the right thing I should
use, and the simpler one that would still let me solve the "which is
stronger" among the user given objects and user set rules.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[Solution]: Lisp partial solution - meta-programming help Louis J Scoras Ruby 13 10-05-2005 06:56 AM
Need help: Is Quick-Union-Find the right solution to this problem (Now I don't think so and I think that topological sorting should be the way to go...?) ? aredo3604gif@yahoo.com C Programming 1 04-13-2005 12:48 AM
Help needed: Is Quick-Union-Find the right solution to this problem ? aredo3604gif@yahoo.com C Programming 1 04-12-2005 08:28 PM
Need help: Is Quick-Union-Find the right solution to this problem (Now I don't think so and I think that topological sorting should be the way to go...?) ? aredo3604gif@yahoo.com C Programming 0 04-12-2005 05:06 PM
A problem in storing HTML in database or a problem in finding the right reporting solution? Merek ASP .Net 0 12-03-2003 06:07 PM



Advertisments