Page 3 of 6 FirstFirst 123456 LastLast
Results 31 to 45 of 84

Math Help - Set Membership Cycles: The Axiom of Regularity in ZF Set Theory.

  1. #31
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    So here's an attempt at a traversing algorithm. My apologies for the psuedo-code/C++ mixture here. My questions:

    1. Have I got the recursion right?
    2. Is this a relatively efficient algorithm?

    Code:
    initialize check_stack = NULL;
    initialize assemblies;
    
    boolean preorder(node x, check_stack)
    {
       check_stack.push(x);
       if there are any repeats in check_stack 
       then
          check_stack.pop();
          return FALSE;
       else
          boolean check_children = TRUE;
          for all y in x.children
          {
             check_children = check_children AND preorder(y, check_stack);
          }
          check_stack.pop();
          return check_children;
       end if
    }
    
    int main(void)
    {
       boolean all_checked_out = TRUE;
       for all x in assemblies
       {
          all_checked_out = all_checked_out AND preorder(x, check_stack);
       }
       print(all_checked_out);
       return 0;
    }
    Follow Math Help Forum on Facebook and Google+

  2. #32
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Ackbeet View Post
    So here's an attempt at a traversing algorithm. My apologies for the psuedo-code/C++ mixture here. My questions:

    1. Have I got the recursion right?
    2. Is this a relatively efficient algorithm?

    Code:
    initialize check_stack = NULL;
    initialize assemblies;
    
    boolean preorder(node x, check_stack)
    {
       check_stack.push(x);
       if there are any repeats in check_stack 
       then
          check_stack.pop();
          return FALSE;
       else
          boolean check_children = TRUE;
          for all y in x.children
          {
             check_children = check_children AND preorder(y, check_stack);
          }
          check_stack.pop();
          return check_children;
       end if
    }
    
    int main(void)
    {
       boolean all_checked_out = TRUE;
       for all x in assemblies
       {
          all_checked_out = all_checked_out AND preorder(x, check_stack);
       }
       print(all_checked_out);
       return 0;
    }
    Hmm I tend to avoid custom stacks if possible just to reduce complexity (hence why I usually write depth-first rather than breadth-first). So I have some difficulty following your code, which I think reflects more on me than on the code. A question on logistics: Is it easy to parse through a stack in your language of choice, e.g., to see whether it contains a certain object, or to check for duplicates? Easy both in terms of writing the code, and in terms of time complexity, as in how would the speed compare to iterating through an array, etc.

    I will need time to read the code, and probably will be busy today, also I won't mind sharing the recursive approach I mentioned earlier without a custom stack, when I have time to implement.
    Follow Math Help Forum on Facebook and Google+

  3. #33
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Hmm I tend to avoid custom stacks if possible just to reduce complexity...
    I would, too, except that at each node, I've got to know the entire list of ancestor nodes in order to check for duplicates. A stack seems the most appropriate data structure there.

    Question as to parsing a stack: I've thought about that. I think that should be easy enough:

    Initialize a second stack.
    Pop all the values of the first stack into the second stack. As you go, also put the items in an array.
    Pop all the values of the second stack back into the first stack. (Two order reversals gets you back to the original order.)
    Check the array for duplicates.

    I suppose you could argue that the way to go here would be to simply use an array the whole time, and pass an index into the sub-function as well as a reference to the array. That might be faster, I agree. But it's been so long since I've done C++ that I didn't want to trust my syntax with pointers and such. The important point, of course, is that at each node we're processing, we know exactly what path along the directed (hopefully) acyclic graph we traversed to get there.

    Theoretically, it should take n(n-1)/2 comparisons to check for duplicates in an array of size n, correct?

    I would be interested in seeing your implementation - in psuedo-code. I'm not particularly interested in the innards of Java, I'm afraid.

    Thanks again!
    Follow Math Help Forum on Facebook and Google+

  4. #34
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Ackbeet View Post
    I would, too, except that at each node, I've got to know the entire list of ancestor nodes in order to check for duplicates. A stack seems the most appropriate data structure there.

    ...
    Understandable points regarding stacks. But with limited experience I can't say for sure how appropriate it is to use a stack here.

    Quote Originally Posted by Ackbeet View Post
    Theoretically, it should take n(n-1)/2 comparisons to check for duplicates in an array of size n, correct?
    I thought the exact same thing at first, but I think we can do much much better by using a boolean array, where each item in your inventory has a unique id that gets mapped to an index in the array; initialize the array to all false; then just go through your list/stack one by one and set the corresponding boolean array index to true, checking first whether it's already true - which would indicate that there's a duplicate.

    Quote Originally Posted by Ackbeet View Post
    I would be interested in seeing your implementation - in psuedo-code. I'm not particularly interested in the innards of Java, I'm afraid.
    Also very understandable! I'm thinking then of writing something in Python because it tends to be very compact and readable. (In fact, it can look a lot like pseudo-code.) I'm not as familiar with it, but it shouldn't be too hard as it won't be very specialized code.

    Quote Originally Posted by Ackbeet View Post
    Thanks again!
    You're welcome! Thanks for the interesting question.
    Follow Math Help Forum on Facebook and Google+

  5. #35
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by undefined View Post
    Understandable points regarding stacks. But with limited experience I can't say for sure how appropriate it is to use a stack here.



    I thought the exact same thing at first, but I think we can do much much better by using a boolean array, where each item in your inventory has a unique id that gets mapped to an index in the array; initialize the array to all false; then just go through your list/stack one by one and set the corresponding boolean array index to true, checking first whether it's already true - which would indicate that there's a duplicate.
    I haven't followed your discussion of the code in detail, but it seems to me that what you are proposing here amounts to a marking algorithm to detect cycles during a depth-first traversal of the directed graph: Every node on the stack needs to have its mark bit set true, and upon return from a node one needs to set its bit to false again.
    So, for efficiency reasons, you'd better not use a mark bit to just check the stack for duplicates over and over again, but, instead, just make this setting/clearing of the mark bit an integral part of the depth-first traversal (set the mark bit when you push a node, clear it when you pop a node), because then you never have to traverse the stack just in order to search for duplicates.
    A cycle is detected if and only if you try to push a node onto the stack that has its mark bit already set.
    Follow Math Help Forum on Facebook and Google+

  6. #36
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I thought the exact same thing at first, but I think we can do much much better by using a boolean array, where each item in your inventory has a unique id that gets mapped to an index in the array; initialize the array to all false; then just go through your list/stack one by one and set the corresponding boolean array index to true, checking first whether it's already true - which would indicate that there's a duplicate.
    For this to be efficient, the mapping from id to index would have to be efficient. I suppose everything in sight here could be sorted, implying that you could use binary search with O(log(n)) operations every time you indexed. That's not too bad, I suppose. Of course, you'd have to sort everything. So you're looking at an O(n log(n)) efficiency hit there, unless it's already sorted. Given the usage of the database, an insertion sort might be the way to go, depending on the internal representation. On the other hand, you'd only need to do that once every time you want to change the assemblies in the database.
    Follow Math Help Forum on Facebook and Google+

  7. #37
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Failure View Post
    I haven't followed your discussion of the code in detail, but it seems to me that what you are proposing here amounts to a marking algorithm to detect cycles during a depth-first traversal of the directed graph: Every node on the stack needs to have its mark bit set true, and upon return from a node one needs to set its bit to false again.
    So, for efficiency reasons, you'd better not use a mark bit to just check the stack for duplicates over and over again, but, instead, just make this setting/clearing of the mark bit an integral part of the depth-first traversal (set the mark bit when you push a node, clear it when you pop a node), because then you never have to traverse the stack just in order to search for duplicates.
    A cycle is detected if and only if you try to push a node onto the stack that has its mark bit already set.
    That sounds right, I haven't actually reviewed the algorithm of post #31 enough to see whether the recursion scheme etc. makes sense, I was just commenting on how best to search for duplicates in an arbitrary list.
    Last edited by undefined; July 21st 2010 at 10:55 AM. Reason: added reference to post # for clarity
    Follow Math Help Forum on Facebook and Google+

  8. #38
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Reply to failure at post #35:

    I haven't followed your discussion of the code in detail, but it seems to me that what you are proposing here amounts to a marking algorithm to detect cycles during a depth-first traversal of the directed graph: Every node on the stack needs to have its mark bit set true, and upon return from a node one needs to set its bit to false again.
    So, for efficiency reasons, you'd better not use a mark bit to just check the stack for duplicates over and over again, but, instead, just make this setting/clearing of the mark bit an integral part of the depth-first traversal (set the mark bit when you push a node, clear it when you pop a node), because then you never have to traverse the stack just in order to search for duplicates.
    A cycle is detected if and only if you try to push a node onto the stack that has its mark bit already set.
    Does the fact that a part can be used in multiple different assemblies (even immediate parents) change this idea at all?
    Follow Math Help Forum on Facebook and Google+

  9. #39
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Ackbeet View Post
    For this to be efficient, the mapping from id to index would have to be efficient. I suppose everything in sight here could be sorted, implying that you could use binary search with O(log(n)) operations every time you indexed. That's not too bad, I suppose. Of course, you'd have to sort everything. So you're looking at an O(n log(n)) efficiency hit there, unless it's already sorted. Given the usage of the database, an insertion sort might be the way to go, depending on the internal representation. On the other hand, you'd only need to do that once every time you want to change the assemblies in the database.
    If memory is not a concern then there's no need to make a special mapping, just use the id as your index, and let the size of the array be 1 greater than the highest possible id.
    Follow Math Help Forum on Facebook and Google+

  10. #40
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Ackbeet View Post
    For this to be efficient, the mapping from id to index would have to be efficient.
    Isn't perhaps your id a small sequential number anyway so that the id itself could be the index into the array of mark bits?
    Or, another idea, could you perhaps extend the database record of every node with a mark bit field? In that case, a mapping would not even be necessary.
    Follow Math Help Forum on Facebook and Google+

  11. #41
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Ackbeet View Post
    Reply to failure at post #35:



    Does the fact that a part can be used in multiple different assemblies (even immediate parents) change this idea at all?
    Well, it is just using the idea that you are doing a depth-first traversal of a directed graph and you want to detect whether this traversal loops back on itself at some point. So no, I don't think it has anything to do with the question of what the in-degree and/or out-degre of a node happens do be. The only problem is that you need to do this starting with every node in the database: thus this doesn't seem particularly efficient to me. But it would be great for what I proposed in the case of a database that one already knows to be cycle free: in that case, only in the case of modifying an existing assembly by adding an already existing assembly as a component would one have to execute this marking depth-first serach for a cycle beginning at the node that is about to be modified, because: if this modification introduces a cycle in the formerly cycle-free database, this assembly that is about to be modified must be part of the cycle.

    Actually, you don't even need an explicit stack: you can just use the invocation stack of recursive calls if you like (but, of course, you don't have to: using an explicit stack might perhaps be a little more efficient).
    Last edited by Failure; July 21st 2010 at 11:37 AM. Reason: changed "directed tree" to "directed graph"
    Follow Math Help Forum on Facebook and Google+

  12. #42
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Hmm. At some point, hardware efficiency ceases to be a virtue, and programmer efficiency becomes paramount. The most efficient algorithm in the world won't help me if the programmer who needs to code it up (which is not me, by the way) can't do it. The programmer in question does have reasonable chops; but extensive senior-level CS-type code is probably not suitable.

    So, I guess what I'm looking for is a fairly simple, straight-forward algorithm with reasonable run-time efficiency that is also straight-forward to code. The coding language is likely going to be Visual Basic for Applications, since the database is in Microsoft Access 2010 (I know this isn't the most robust database - we'll migrate over to SQL Server, probably, when we run into scaling issues; the advantage of Access is that the learning curve is easy.) Incidentally, I'm definitely NOT interested in getting into language-specific concerns in this thread. I want the pseudo-code version of an algorithm that fits the above criteria.

    So whenever you get a chance, an evaluation of the correctness of my algorithm in post # 31 would be terrific, and any suggestions for blatant inefficiencies would also be appreciated. Thanks!
    Follow Math Help Forum on Facebook and Google+

  13. #43
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Reply to failure at post # 41:

    Well, I wouldn't count on the knowing the database is already cycle-free. We may want to import a whole bunch of data wholesale into the database, and check that out. On the other hand, we have an entire table devoted to listing all the assemblies. So we don't have to guess which parts are assemblies and which are not.
    Follow Math Help Forum on Facebook and Google+

  14. #44
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Regarding code language: I plan on using a real language (in this case Python) because then I'll be able to test to make sure there are no bugs. But if it comes out not looking pseudo-cody enough, then I can rewrite. Won't be able to look at algorithm in post #31 in depth for a little while.
    Follow Math Help Forum on Facebook and Google+

  15. #45
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Ackbeet View Post
    So whenever you get a chance, an evaluation of the correctness of my algorithm in post # 31 would be terrific, and any suggestions for blatant inefficiencies would also be appreciated.
    Your algorithm #31 seems correct to me. The main inefficiencies are, in my opinion, twofold:
    1. The inefficiency of repeatedly checking the stack for duplicates (i.e. for the case that the depth-first traversal loops back on itself). We have talked about that and you know what I suggest to get rid of this problem (almost) entirely.
    2. The inefficiency of using depth-first search for all assemblies in the database: because this will make your algorithm traverse the same subtrees repeatedly (because it cannot remember that those subtrees have already been traversed earlier). For imagine a rather deeply nested chain of assemblies of assemblies: for every assembly in that chain, your program is going to be executed, although if you had known in advance that this was a chain, you could have just done a single depth first traversal beginning at the root node of that chain, and dispensed width doing traversals for the other assemblies lower down in the chain.
    Follow Math Help Forum on Facebook and Google+

Page 3 of 6 FirstFirst 123456 LastLast

Similar Math Help Forum Discussions

  1. Axiom of Regularity Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 20th 2010, 10:44 AM
  2. graph theory question about walks and cycles
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 29th 2010, 08:44 PM
  3. Graph theory regarding cycles
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 15th 2009, 04:42 PM
  4. ZF Axiom of Regularity and Russell's Paradox
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 17th 2009, 04:14 PM
  5. ZF Axiom of regularity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 12th 2009, 11:37 AM

/mathhelpforum @mathhelpforum