Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Help needed: Is Quick-Union-Find the right solution to this problem ? (http://www.velocityreviews.com/forums/t437701-help-needed-is-quick-union-find-the-right-solution-to-this-problem.html)

aredo3604gif@yahoo.com 04-12-2005 05:05 PM

Help needed: Is Quick-Union-Find the right solution to this problem ?
 
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.


Lawrence Kirby 04-12-2005 08:28 PM

Re: Help needed: Is Quick-Union-Find the right solution to this problem ?
 
On Tue, 12 Apr 2005 17:05:05 +0000, aredo3604gif wrote:

> 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.


....

There is nothing in your question that obviously relates to the topic of
this newsgroup i.e. the C programming language. Your nest bet would be to
post to an algorithms related newsgroup such as comp.programming.

Lawrence


All times are GMT. The time now is 04:44 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.