Help needed: Is Quick-Union-Find the right solution to this problem ?

Discussion in 'C Programming' started by aredo3604gif@yahoo.com, Apr 12, 2005.

  1. Guest

    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.
     
    , Apr 12, 2005
    #1
    1. Advertising

  2. On Tue, 12 Apr 2005 17:05:05 +0000, aredo3604gif 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.


    ....

    There is nothing in your question that obviously relates to the topic of
    this newsgroup i.e. the C programming language. Your nest bet would be to
    post to an algorithms related newsgroup such as comp.programming.

    Lawrence
     
    Lawrence Kirby, Apr 12, 2005
    #2
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Matt Garman
    Replies:
    1
    Views:
    694
    Matt Garman
    Apr 25, 2004
  2. Peter Dunker

    union in struct without union name

    Peter Dunker, Apr 26, 2004, in forum: C Programming
    Replies:
    2
    Views:
    932
    Chris Torek
    Apr 26, 2004
  3. Replies:
    0
    Views:
    390
  4. Replies:
    0
    Views:
    648
  5. Replies:
    1
    Views:
    914
    Jack Klein
    Apr 13, 2005
Loading...

Share This Page