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

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

  1. Guest

    On Sun, 10 Apr 2005 19:46:32 GMT, 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.
    >
    >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 ?
     
    , Apr 12, 2005
    #1
    1. Advertising

  2. Jack Klein Guest

    On Tue, 12 Apr 2005 17:06:49 GMT, wrote in
    comp.lang.c:

    > On Sun, 10 Apr 2005 19:46:32 GMT, 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.
    > >
    > >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 ?


    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 news:comp.programming.

    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.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Apr 13, 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:
    680
    Matt Garman
    Apr 25, 2004
  2. Replies:
    0
    Views:
    385
  3. Replies:
    1
    Views:
    329
    Lawrence Kirby
    Apr 12, 2005
  4. Replies:
    0
    Views:
    636
  5. OldButStillLearning

    Now You See It Now You Don't

    OldButStillLearning, Dec 11, 2007, in forum: ASP .Net
    Replies:
    6
    Views:
    311
    Juan T. Llibre
    Dec 12, 2007
Loading...

Share This Page