Velocity Reviews > 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...?) ?

# 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
Guest
Posts: n/a

 04-12-2005
On Sun, 10 Apr 2005 19:46:32 GMT, http://www.velocityreviews.com/forums/(E-Mail Removed) 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.
>
>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" .. ?!
>
>use, and the simpler one that would still let me solve the "which is
>stronger" among the user given objects and user set rules.

After a bit of searching I think that I should use DAG and Topological
Sorting, right ?
Topological sorting on a DAG graph in which the user input can be
checked to avoid reflexive property to be inserted should do the
trick, no ?
Regarding transitivity property to tell the user that a given rule
can't be accepted I have to build up the topological sort list and
check on it everytime, right ?

Or, is there any simpler way to have all of this work without building
up a graph and doing topological sorting on it and so on ?

Jack Klein
Guest
Posts: n/a

 04-13-2005
On Tue, 12 Apr 2005 17:06:49 GMT, (E-Mail Removed) wrote in
comp.lang.c:

> On Sun, 10 Apr 2005 19:46:32 GMT, (E-Mail Removed) 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.
> >
> >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" .. ?!
> >
> >use, and the simpler one that would still let me solve the "which is
> >stronger" among the user given objects and user set rules.

>
>
> After a bit of searching I think that I should use DAG and Topological
> Sorting, right ?
> Topological sorting on a DAG graph in which the user input can be
> checked to avoid reflexive property to be inserted should do the
> trick, no ?
> Regarding transitivity property to tell the user that a given rule
> can't be accepted I have to build up the topological sort list and
> check on it everytime, right ?
>
> Or, is there any simpler way to have all of this work without building
> up a graph and doing topological sorting on it and so on ?

quoted above. Notice not one single mention of the C programming
language, which is our topic here. Algorithm selection is in fact
programming language independent.

If you want advice on choosing an algorithm, you should ask in a group
like news:comp.programming.

Once you have selected your algorithm, if you have difficulties
implementing it in standard C, then post your code here and explain
your problem with it, and we can help.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html