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 ?