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

Discussion in 'C Programming' started by aredo3604gif@yahoo.com, Apr 11, 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 11, 2005
    #1
    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:
    677
    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:
    889
    Chris Torek
    Apr 26, 2004
  3. Replies:
    1
    Views:
    325
    Lawrence Kirby
    Apr 12, 2005
  4. Replies:
    0
    Views:
    625
  5. Replies:
    1
    Views:
    888
    Jack Klein
    Apr 13, 2005
Loading...

Share This Page