Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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" .. ?!
>
>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.



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 ?

 
Reply With Quote
 
 
 
 
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" .. ?!
> >
> >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.

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


Look back at your question, and your follow-up to your own question,
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
 
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
problem in running a basic code in python 3.3.0 that includes HTML file Satabdi Mukherjee Python 1 04-04-2013 07:48 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
Help needed: Is Quick-Union-Find the right solution to this problem ? aredo3604gif@yahoo.com C Programming 0 04-11-2005 11:52 AM
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
So, should I think no one has a solution to this? ani ASP .Net 9 11-12-2003 02:34 PM



Advertisments