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