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

Discussion in 'C Programming' started by, 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. Advertisements

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
    Matt Garman
    Apr 25, 2004
  2. Peter Dunker

    union in struct without union name

    Peter Dunker, Apr 26, 2004, in forum: C Programming
    Chris Torek
    Apr 26, 2004
  3. Replies:
    Lawrence Kirby
    Apr 12, 2005
  4. Replies:
  5. Replies:
    Jack Klein
    Apr 13, 2005

Share This Page