Need help: Is Quick-Union-Find the right solution to this problem (Now I don't think so and I think

A

aredo3604gif

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

Jack Klein

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top