Is There a Java Class for this Kind of Data Structure?

Discussion in 'Java' started by Hal Vaughan, Jul 12, 2007.

  1. Hal Vaughan

    Hal Vaughan Guest

    I think if I weren't self taught, I'd know the terms to describe what I'm
    trying to do and might even know what kind of class to look for in the Java
    API. I'm hoping there's a Java class that will do what I need to do. I
    think it's some kind of tree structure, but I've only heard the term used
    and what I found (like TreeMap) doesn't seem to do what I need. Any info I
    find on Trees, though, seems to go back to JTree and I don't need a GUI for
    this.

    I have a number of data tables and many of them have dependent tables based
    on matching certain criteria. These dependent tables often have other
    dependent tables. There is no limit to the levels of dependents and to the
    number of dependents for each table, but in reality, I doubt any would go
    deeper than 5-6 levels.

    I have a list of the main tables and each table has its own list of its
    immediate dependents (isn't the correct term children?) and, of course,
    each child has a list of its own children and so on.

    This has worked fine so far, but if a main table is modified, I need to
    update all the tables that depend on it, no matter how many levels removed.
    There are more details I don't want to go into, but what I'd like to do is
    have one structure that a main table has access to that is a list of all
    the dependent tables. I can't use a regular list for this because I need
    for all the tables at one level to be listed at that level. I was thinking
    of something like a LinkedList of LinkedLists.

    For instance, the main table would be the first item in the main LinkedList.
    The 2nd item would be a LinkedList of all it's children and the 3rd item
    would be a another LinkedList of all the grandchilren and so on.

    Yes, I can do this with lists of lists, but isn't here some kind of tree or
    other kind of branching list that will do this?

    Thanks for suggestions!

    Hal
     
    Hal Vaughan, Jul 12, 2007
    #1
    1. Advertising

  2. Hal Vaughan

    Jeff Higgins Guest

    Hal Vaughan wrote:
    >
    > Yes, I can do this with lists of lists, but isn't here some kind of tree
    > or
    > other kind of branching list that will do this?
    >


    Have you looked at DefaultTreeModel?
    Even though it's in the Swing package
    it can be used nicely standalone.
     
    Jeff Higgins, Jul 12, 2007
    #2
    1. Advertising

  3. Hal Vaughan

    Hal Vaughan Guest

    Jeff Higgins wrote:

    >
    > Hal Vaughan wrote:
    >>
    >> Yes, I can do this with lists of lists, but isn't here some kind of tree
    >> or
    >> other kind of branching list that will do this?
    >>

    >
    > Have you looked at DefaultTreeModel?
    > Even though it's in the Swing package
    > it can be used nicely standalone.


    Okay. I either missed that or excluded it because it cam up as connected to
    Swing. There are two problems that I can see:

    1) The root has to be a TreeNode so I'm not clear if I can set a root object
    and then add my object as its own root.

    2) I don't see a way to add Objects to the tree.

    Hal
     
    Hal Vaughan, Jul 12, 2007
    #3
  4. In article <>,
    Hal Vaughan <> wrote:
    >Jeff Higgins wrote:
    >>
    >> Have you looked at DefaultTreeModel?

    >
    >Okay. I either missed that or excluded it because it cam up as connected to
    >Swing. There are two problems that I can see:
    >
    >1) The root has to be a TreeNode so I'm not clear if I can set a root object
    >and then add my object as its own root.


    I'm not exactly sure what you are saying, but one generally has two
    alternatives:

    1) Write your own "MyTreeNodeType implements TreeNode" which can, of
    course, do whatever you need it to do.

    2) Use DefaultMutableTreeNode for the root and put your own object for
    that node into the node as a user object (see
    DefaultMutableTreeNode.setUserObject).

    >2) I don't see a way to add Objects to the tree.


    You don't add objects to the tree as such. You set a root object in
    the tree model's constructor and then you add child objects to this
    root object.

    Typically, you may use a DefaultMutableTreeNode as the root and also
    for all other nodes in the tree. DefaultMutableTreeNode has add(),
    children(), etc.

    Note that in a TreeModel, there can only be one root object so if you
    want multiple roots you will have to make your roots children of the
    "real" root and just ignore the real root as much as possible.

    Cheers
    Bent D
    --
    Bent Dalager - - http://www.pvv.org/~bcd
    powered by emacs
     
    Bent C Dalager, Jul 12, 2007
    #4
  5. Hal Vaughan

    Jeff Higgins Guest

    Hal Vaughan wrote:
    > 1) The root has to be a TreeNode so I'm not clear if I can set a root
    > object
    > and then add my object as its own root.
    >
    > 2) I don't see a way to add Objects to the tree.
    >

    All nodes in DefaultTreeModel are TreeNodes.
    DefaultMutableTreeNode wraps an userObject.
    You can construct DefaultMutableTreeNode(Object userObject).
    Your userObject might be an object that wraps a Table reference
    and a Table id or name for example.
    Node.getUserObject, Node.setUserObject(), Node.getUserObjectPath() etc.
     
    Jeff Higgins, Jul 12, 2007
    #5
  6. Hal Vaughan

    Jeff Higgins Guest

    As an addition to what Bent said,
    You can also extend DefaultMutableTreeNode.
    An example that I liked is located here:
    <http://www.java2s.com/Code/Java/Swing-JFC/AtreemodelusingtheSortTreeModelwithaFilehierarchyasinput.htm>
     
    Jeff Higgins, Jul 12, 2007
    #6
  7. Hal Vaughan

    Oliver Wong Guest

    "Hal Vaughan" <> wrote in message
    news:...
    >I think if I weren't self taught, I'd know the terms to describe what I'm
    > trying to do and might even know what kind of class to look for in the
    > Java
    > API. I'm hoping there's a Java class that will do what I need to do. I
    > think it's some kind of tree structure, but I've only heard the term
    > used
    > and what I found (like TreeMap) doesn't seem to do what I need. Any
    > info I
    > find on Trees, though, seems to go back to JTree and I don't need a GUI
    > for
    > this.
    >
    > I have a number of data tables and many of them have dependent tables
    > based
    > on matching certain criteria. These dependent tables often have other
    > dependent tables. There is no limit to the levels of dependents and to
    > the
    > number of dependents for each table, but in reality, I doubt any would
    > go
    > deeper than 5-6 levels.
    >
    > I have a list of the main tables and each table has its own list of its
    > immediate dependents (isn't the correct term children?) and, of course,
    > each child has a list of its own children and so on.


    Yes, children is the correct term.

    >
    > This has worked fine so far, but if a main table is modified, I need to
    > update all the tables that depend on it, no matter how many levels
    > removed.
    > There are more details I don't want to go into, but what I'd like to do
    > is
    > have one structure that a main table has access to that is a list of all
    > the dependent tables. I can't use a regular list for this because I
    > need
    > for all the tables at one level to be listed at that level. I was
    > thinking
    > of something like a LinkedList of LinkedLists.


    In Java, there's an interface called "List", and from the
    program-behaviour point of view, it doesn't really matter whether the List
    interface is implemented via an ArrayList or a LinkedList or some other
    type of List. The term "regular list" is ambiguous and it's unclear what
    you are referring to by it (an easy way to clear ambiguity is to post your
    source code, since the meaning of the Java language is very precisely
    defined -- see http://www.physci.org/codes/sscce.html)

    In other words, a LinkedList does not do anything above and beyond
    what a plain List can do, so replacing whatever you've got now iwth a
    LinkedList is almost guaranteed to not solve your problem.

    >
    > For instance, the main table would be the first item in the main
    > LinkedList.
    > The 2nd item would be a LinkedList of all it's children and the 3rd item
    > would be a another LinkedList of all the grandchilren and so on.


    If the first element of your list is of type "MainTable", and the
    second element of your list is of type "LinkedList", then you've got a
    heterogenous list, and they're a big pain to work with.

    >
    > Yes, I can do this with lists of lists, but isn't here some kind of tree
    > or
    > other kind of branching list that will do this?


    When you wrote...

    > I have a list of the main tables and each table has its own list of its
    > immediate dependents (isn't the correct term children?) and, of course,
    > each child has a list of its own children and so on.


    ... you demonstrated that you already have a tree implemented. So I
    don't think your problem is "how do I add a tree data structure somewhere
    in my program?" because you've already done so. I think your problem is
    more that you haven't actually identified what your problem is.

    You write that you want to "update all the tables that depend on it,
    no matter how many levels removed", so why don't you go ahead and do that?
    What is it about your current data structure that is preventing you from
    being able to write code which does exactly what you want?

    - Oliver
     
    Oliver Wong, Jul 12, 2007
    #7
  8. Hal Vaughan

    Hal Vaughan Guest

    Oliver Wong wrote:

    ....
    > When you wrote...
    >
    >> I have a list of the main tables and each table has its own list of its
    >> immediate dependents (isn't the correct term children?) and, of course,
    >> each child has a list of its own children and so on.

    >
    > ... you demonstrated that you already have a tree implemented. So I
    > don't think your problem is "how do I add a tree data structure somewhere
    > in my program?" because you've already done so. I think your problem is
    > more that you haven't actually identified what your problem is.
    >
    > You write that you want to "update all the tables that depend on it,
    > no matter how many levels removed", so why don't you go ahead and do that?
    > What is it about your current data structure that is preventing you from
    > being able to write code which does exactly what you want?


    First, thanks (to you and everyone else) for a lot of good information.

    I did have a method I could call in one table that would step through all
    the dependent tables and update them and the Swing components that used
    them for setting data, the problem was it was easiest to go through the
    list of all dependent tables and for each one call the update, which would
    go to that table and do the same. In essence the update would start at the
    trunk and follow one branch, then take one fork and so on through to the
    end of one branch, then it would back up and go through the next branch.

    That worked, or mostly worked, but I found the problem was that tables
    several levels down would be updated before some tables only 1 level down
    were updated and that would effect what was displayed on the Swing
    components. The reason I want to store the tables in a tree is so I can
    get more easily make sure I update all tables 1 level down then move to 2
    levels down and so on. That way I update all the tables in each level
    before moving on to the next level.

    From what I can see, there is no way to get all the objects from a tree at
    one level. I was considering using the DefaultTreeModel, but that one
    issue kept me back. At this point, because I want to go level by level,
    I'm thinking of using one list and each item is a list of all the tables at
    that level.

    Hal
     
    Hal Vaughan, Jul 12, 2007
    #8
  9. Hal Vaughan

    Jeff Higgins Guest

    Hal Vaughan wrote:

    > At this point, because I want to go level by
    > level,
    > I'm thinking of using one list and each item is a list of all the tables
    > at
    > that level.
    >

    This online book was an big help to me
    in understanding tree traversals.
    <http://www.brpreiss.com/books/opus5/html/book.html>
     
    Jeff Higgins, Jul 12, 2007
    #9
  10. Hal Vaughan

    Oliver Wong Guest

    "Hal Vaughan" <> wrote in message
    news:...
    >
    > I did have a method I could call in one table that would step through
    > all
    > the dependent tables and update them and the Swing components that used
    > them for setting data, the problem was it was easiest to go through the
    > list of all dependent tables and for each one call the update, which
    > would
    > go to that table and do the same. In essence the update would start at
    > the
    > trunk and follow one branch, then take one fork and so on through to the
    > end of one branch, then it would back up and go through the next branch.
    >
    > That worked, or mostly worked, but I found the problem was that tables
    > several levels down would be updated before some tables only 1 level
    > down
    > were updated and that would effect what was displayed on the Swing
    > components. The reason I want to store the tables in a tree is so I can
    > get more easily make sure I update all tables 1 level down then move to
    > 2
    > levels down and so on. That way I update all the tables in each level
    > before moving on to the next level.


    If "ordering" is an issue, see
    http://en.wikipedia.org/wiki/Tree_traversal

    Note that the problem may also be that your data objects are correctly
    being updated, but your GUI is not being updated to reflect the new values
    stored in memory.


    >
    > From what I can see, there is no way to get all the objects from a tree
    > at
    > one level. I was considering using the DefaultTreeModel, but that one
    > issue kept me back. At this point, because I want to go level by level,
    > I'm thinking of using one list and each item is a list of all the tables
    > at
    > that level.


    You can do that, but this particular configuration of having a list of
    list of elements at a given level doesn't sound like it would be conducive
    to writing a recursive algorithm. The usual way to go about it is to take
    care of a single node, and then to take care of all of its children. So
    rather than working with lists, you'd be working with trees. See
    http://en.wikipedia.org/wiki/Recursion

    - Oliver
     
    Oliver Wong, Jul 12, 2007
    #10
  11. Hal Vaughan

    Hal Vaughan Guest

    Oliver Wong wrote:

    >
    > "Hal Vaughan" <> wrote in message
    > news:...
    >>
    >> I did have a method I could call in one table that would step through
    >> all
    >> the dependent tables and update them and the Swing components that used
    >> them for setting data, the problem was it was easiest to go through the
    >> list of all dependent tables and for each one call the update, which
    >> would
    >> go to that table and do the same. In essence the update would start at
    >> the
    >> trunk and follow one branch, then take one fork and so on through to the
    >> end of one branch, then it would back up and go through the next branch.
    >>
    >> That worked, or mostly worked, but I found the problem was that tables
    >> several levels down would be updated before some tables only 1 level
    >> down
    >> were updated and that would effect what was displayed on the Swing
    >> components. The reason I want to store the tables in a tree is so I can
    >> get more easily make sure I update all tables 1 level down then move to
    >> 2
    >> levels down and so on. That way I update all the tables in each level
    >> before moving on to the next level.

    >
    > If "ordering" is an issue, see
    > http://en.wikipedia.org/wiki/Tree_traversal
    >
    > Note that the problem may also be that your data objects are correctly
    > being updated, but your GUI is not being updated to reflect the new values
    > stored in memory.


    That was a problem I think I fixed earlier today. It was tied in to the
    fact that my old update would go all the way through one branch and update
    the tables, THEN update the components and sometimes the values in the
    components were used to figure out the contents of some of the tables.

    >
    >>
    >> From what I can see, there is no way to get all the objects from a tree
    >> at
    >> one level. I was considering using the DefaultTreeModel, but that one
    >> issue kept me back. At this point, because I want to go level by level,
    >> I'm thinking of using one list and each item is a list of all the tables
    >> at
    >> that level.

    >
    > You can do that, but this particular configuration of having a list of
    > list of elements at a given level doesn't sound like it would be conducive
    > to writing a recursive algorithm. The usual way to go about it is to take
    > care of a single node, and then to take care of all of its children.


    That's what I was doing, but then I'd have one branch updated and when
    updating the next branch, it would change tables that could effect
    components that effected the first branch.

    > So
    > rather than working with lists, you'd be working with trees. See
    > http://en.wikipedia.org/wiki/Recursion


    I've got recursion. Actually, I think it's kind of fun!

    Hal
     
    Hal Vaughan, Jul 13, 2007
    #11
  12. Hal Vaughan

    Oliver Wong Guest

    "Hal Vaughan" <> wrote in message
    news:...
    > Oliver Wong wrote:
    >

    [context is working with trees]

    >> The usual way to go about it is to take
    >> care of a single node, and then to take care of all of its children.

    >
    > That's what I was doing, but then I'd have one branch updated and when
    > updating the next branch, it would change tables that could effect
    > components that effected the first branch.


    Just to clarify, let's say your tree structure looks like:

    A
    |- B
    |- C
    `- D

    So "B", "C" and "D" are children of A. Changes to "A" may affect "B",
    "C" and "D", so when you update "A", you must also update "B", "C" and
    "D".

    Are you saying that in addition to this, changes to "B" affect "C" and
    "D", so that when you update "B", you must also update "C" and "D" and
    vice versa?

    - Oliver
     
    Oliver Wong, Jul 13, 2007
    #12
  13. Hal Vaughan

    Hal Vaughan Guest

    Oliver Wong wrote:

    >
    > "Hal Vaughan" <> wrote in message
    > news:...
    >> Oliver Wong wrote:
    >>

    > [context is working with trees]
    >
    >>> The usual way to go about it is to take
    >>> care of a single node, and then to take care of all of its children.

    >>
    >> That's what I was doing, but then I'd have one branch updated and when
    >> updating the next branch, it would change tables that could effect
    >> components that effected the first branch.

    >
    > Just to clarify, let's say your tree structure looks like:
    >
    > A
    > |- B
    > |- C
    > `- D


    More like (and I hate to do diagrams because I know spacing is different on
    different fonts):


    A
    |-+-+
    B C D
    | |
    E F

    > So "B", "C" and "D" are children of A. Changes to "A" may affect "B",
    > "C" and "D", so when you update "A", you must also update "B", "C" and
    > "D".
    >
    > Are you saying that in addition to this, changes to "B" affect "C" and
    > "D", so that when you update "B", you must also update "C" and "D" and
    > vice versa?


    It's more like D might provide prompt data to a Swing component that might
    effect F just like C does so I have to update C and D at the same time
    before E and F are updated. It may just be a different way of drawing the
    table, so we may be saying the same thing, but I'm just trying to make sure
    we're all saying the same thing. In other words, a table 3 or 4 levels
    down could be effected by not 1 but 2 tables at level 2. Theoretically
    it's possible it could be effected by more than 2 tables at level 2, but in
    practice I would doubt it.

    Hal
     
    Hal Vaughan, Jul 13, 2007
    #13
  14. Hal Vaughan

    Oliver Wong Guest

    "Hal Vaughan" <> wrote in message
    news:...
    > Oliver Wong wrote:
    >>
    >> Just to clarify, let's say your tree structure looks like:
    >>
    >> A
    >> |- B
    >> |- C
    >> `- D

    >
    > More like (and I hate to do diagrams because I know spacing is different
    > on
    > different fonts):
    >
    >
    > A
    > |-+-+
    > B C D
    > | |
    > E F


    Who are the children of who in this notation?

    [...]
    >>
    >> Are you saying that in addition to this, changes to "B" affect "C"
    >> and
    >> "D", so that when you update "B", you must also update "C" and "D" and
    >> vice versa?

    >
    > It's more like D might provide prompt data to a Swing component that
    > might
    > effect F just like C does so I have to update C and D at the same time
    > before E and F are updated. It may just be a different way of drawing
    > the
    > table, so we may be saying the same thing, but I'm just trying to make
    > sure
    > we're all saying the same thing. In other words, a table 3 or 4 levels
    > down could be effected by not 1 but 2 tables at level 2. Theoretically
    > it's possible it could be effected by more than 2 tables at level 2, but
    > in
    > practice I would doubt it.


    I don't have the information I'm looking for, so let me rephrase my
    question:

    Are tables only affected by their parents, grandparents,
    great-grand-parents, etc., or is it possible that they are affected by
    uncles/aunts, siblings, etc.

    Or to phrase it another way, if you draw a line between a node, and
    every node that might affect it, does the line always go towards the root
    (which I think is drawn at the top in both our diagrams), or does it
    sometimes go up, and then back down?

    - Oliver
     
    Oliver Wong, Jul 13, 2007
    #14
  15. Hal Vaughan

    Hal Vaughan Guest

    Oliver Wong wrote:

    > "Hal Vaughan" <> wrote in message
    > news:...
    >> Oliver Wong wrote:
    >>>
    >>> Just to clarify, let's say your tree structure looks like:
    >>>
    >>> A
    >>> |- B
    >>> |- C
    >>> `- D

    >>
    >> More like (and I hate to do diagrams because I know spacing is different
    >> on
    >> different fonts):
    >>
    >>
    >> A
    >> |-+-+
    >> B C D
    >> | |
    >> E F

    >
    > Who are the children of who in this notation?


    B, C, and D. The grandchildren are E & F.

    >
    > [...]
    >>>
    >>> Are you saying that in addition to this, changes to "B" affect "C"
    >>> and
    >>> "D", so that when you update "B", you must also update "C" and "D" and
    >>> vice versa?

    >>
    >> It's more like D might provide prompt data to a Swing component that
    >> might
    >> effect F just like C does so I have to update C and D at the same time
    >> before E and F are updated. It may just be a different way of drawing
    >> the
    >> table, so we may be saying the same thing, but I'm just trying to make
    >> sure
    >> we're all saying the same thing. In other words, a table 3 or 4 levels
    >> down could be effected by not 1 but 2 tables at level 2. Theoretically
    >> it's possible it could be effected by more than 2 tables at level 2, but
    >> in
    >> practice I would doubt it.

    >
    > I don't have the information I'm looking for, so let me rephrase my
    > question:
    >
    > Are tables only affected by their parents, grandparents,
    > great-grand-parents, etc., or is it possible that they are affected by
    > uncles/aunts, siblings, etc.


    They can be affected by uncles/aunts, but NOT by siblings.

    > Or to phrase it another way, if you draw a line between a node, and
    > every node that might affect it, does the line always go towards the root
    > (which I think is drawn at the top in both our diagrams), or does it
    > sometimes go up, and then back down?


    Always goes up, but could go diagonally up.

    This is beginning to remind me of early spreadsheets where there were times
    you'd need a value in a column way to the right to be used for something
    back towards the left and if you had it set for manual recalc, you'd have
    to recalc twice to keep it all in sync.

    Hal
     
    Hal Vaughan, Jul 13, 2007
    #15
  16. Hal Vaughan

    Oliver Wong Guest

    "Hal Vaughan" <> wrote in message
    news:...
    > Oliver Wong wrote:
    >

    [talking about trees where the nodes are tables]

    >> Are tables only affected by their parents, grandparents,
    >> great-grand-parents, etc., or is it possible that they are affected by
    >> uncles/aunts, siblings, etc.

    >
    > They can be affected by uncles/aunts, but NOT by siblings.
    >
    >> Or to phrase it another way, if you draw a line between a node, and
    >> every node that might affect it, does the line always go towards the
    >> root
    >> (which I think is drawn at the top in both our diagrams), or does it
    >> sometimes go up, and then back down?

    >
    > Always goes up, but could go diagonally up.
    >
    > This is beginning to remind me of early spreadsheets where there were
    > times
    > you'd need a value in a column way to the right to be used for something
    > back towards the left and if you had it set for manual recalc, you'd
    > have
    > to recalc twice to keep it all in sync.


    That is essentially the situation you've got right now. Trees
    typically don't lend themselves well to modeling things where uncle/aunt
    relationships are important. Are you using the tree structure for other
    reasons than this updating-algorithm? If not, you might instead want to
    look into using a directed acyclic graph, where each edge in the graph
    represents a dependency. That way, when a change in one table occurs, it
    can notify all of its dependents (which may be children, nephew/nieces)
    who in turn notify their dependents and so on.

    Otherwise, if the tree structure is important, you could modify your
    updating-algorithm so that it uses a breadth-first traversal instead of a
    depth-first traversal. Usually this means making your method
    non-recursive, and instead having a queue with a list of nodes that need
    to be updated, and you iterate over the queue until it's empty (meaning
    all your work is done). A breadth-first traversal means that all the nodes
    at level N will be updated before all the nodes at level N+1.

    - Oliver
     
    Oliver Wong, Jul 13, 2007
    #16
  17. Hal Vaughan

    Hal Vaughan Guest

    Oliver Wong wrote:

    >
    > "Hal Vaughan" <> wrote in message
    > news:...
    >> Oliver Wong wrote:
    >>

    > [talking about trees where the nodes are tables]
    >
    >>> Are tables only affected by their parents, grandparents,
    >>> great-grand-parents, etc., or is it possible that they are affected by
    >>> uncles/aunts, siblings, etc.

    >>
    >> They can be affected by uncles/aunts, but NOT by siblings.
    >>
    >>> Or to phrase it another way, if you draw a line between a node, and
    >>> every node that might affect it, does the line always go towards the
    >>> root
    >>> (which I think is drawn at the top in both our diagrams), or does it
    >>> sometimes go up, and then back down?

    >>
    >> Always goes up, but could go diagonally up.
    >>
    >> This is beginning to remind me of early spreadsheets where there were
    >> times
    >> you'd need a value in a column way to the right to be used for something
    >> back towards the left and if you had it set for manual recalc, you'd
    >> have
    >> to recalc twice to keep it all in sync.

    >
    > That is essentially the situation you've got right now. Trees
    > typically don't lend themselves well to modeling things where uncle/aunt
    > relationships are important. Are you using the tree structure for other
    > reasons than this updating-algorithm?


    I was looking into a tree because I thought that would be the easiest way to
    list all the tables by level or generation and step through them.
    Remember, I'm self taught. There have been references in this thread (and
    in others when I've asked a question) that have been a huge help to me in
    not only answering a question, but in giving me more information about data
    structures and algorithms that I did not know. I had a few classes back in
    the '70s and '80s in high school and college, but I was not a programming
    major and was mostly using Assembler on my Apple //e so a lot of the
    concepts in OOP are fairly new to me and I've basically had to learn what I
    needed at any particular point in the process. It's a big help when
    someone points out what they know are good online resources in this field.
    While I find some on my own in Google, often something I think explains a
    point well can leave out a lot of info I should know but am unaware of.


    > If not, you might instead want to
    > look into using a directed acyclic graph, where each edge in the graph
    > represents a dependency. That way, when a change in one table occurs, it
    > can notify all of its dependents (which may be children, nephew/nieces)
    > who in turn notify their dependents and so on.


    Actually, that's part of how I was thinking of using the tree. Whenever the
    table data was changed, update() was called and would step through all the
    dependent tables. The problem, as I've said, is I didn't have them listed
    by level, but just by following a branch.

    > Otherwise, if the tree structure is important, you could modify your
    > updating-algorithm so that it uses a breadth-first traversal instead of a
    > depth-first traversal. Usually this means making your method
    > non-recursive, and instead having a queue with a list of nodes that need
    > to be updated, and you iterate over the queue until it's empty (meaning
    > all your work is done). A breadth-first traversal means that all the nodes
    > at level N will be updated before all the nodes at level N+1.


    Right now I'm experimenting with a loop that I wouldn't actually label as
    recursive but is close. It starts with a table, makes that table the first
    node in the list, then the loop starts. It gets the children of that table
    and makes a list with them as nodes and that new sublist becomes the next
    node in the main list. Then it looks at all the grandchild tables and
    makes another sublist of them and that becomes the 3rd node on the main
    list. I end up with a main list and each node is a sublist. The first
    sublist is only 1 item long, containing the initial table. The 2nd
    node/sublist is all the children, the 3rd node/sublist is the grandchildren
    and so on.

    I looked into it several ways since I don't like writing a loop to gather
    data, then another to go through that same data, but found if I tried one
    loop to process, there were times I'd have to step back one level, so I
    decided to list it all. The only actual recursion at this point is getting
    a list of tables from one table, then doing the same from each table in the
    list.

    Hal
     
    Hal Vaughan, Jul 13, 2007
    #17
  18. Hal Vaughan

    Roedy Green Guest

    On Thu, 12 Jul 2007 05:34:12 -0400, Hal Vaughan
    <> wrote, quoted or indirectly quoted someone
    who said :

    >
    >Thanks for suggestions!


    have a look at javax.swing.tree.DefaultTreeModel.

    I have not looked closely, but it may be suitable for non-GUI use too.

    To roll your own tree is not very difficult. Your Node class has a
    ArrayList of child Nodes.. You create the obvious methods to add a
    child, remove a child, create a node, chase depth first and breadth
    first with the Visitor pattern.

    Then to use, you extend the Node Class with extra fields.

    If you rarely have new children, you can use an array of children, and
    replace it whenever the number of children changes.

    You also have a pointer from child to parent.

    TreeModel defines a basic interface to a tree.
    --
    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Jul 13, 2007
    #18
  19. Hal Vaughan

    Oliver Wong Guest

    "Hal Vaughan" <> wrote in message
    news:D...
    > Oliver Wong wrote:
    >
    >> Trees
    >> typically don't lend themselves well to modeling things where
    >> uncle/aunt
    >> relationships are important. Are you using the tree structure for other
    >> reasons than this updating-algorithm?

    >
    > I was looking into a tree because I thought that would be the easiest
    > way to
    > list all the tables by level or generation and step through them.
    > Remember, I'm self taught.


    Picking the right data structure for a given problem is one of those
    things you just acquire through experience, I think. It's difficult for me
    to say for sure, because I don't know what you're doing with your tables,
    but based on what I heard so far, an acyclic directed graph sounds like
    the the data structure I'd used to model the dependencies between your
    tables.

    Presumably, your program is trying to "do something": model global
    warming, schedule airplane flights, track inventory in a warehouse, etc.
    This "thing" that it is trying to do exists independently of your program;
    that is, you could do it manually if you needed to, but it might be
    painful, boring, repetitive, etc. This "thing" that is independent of your
    program is your "problem domain".

    So what I'm wondering is whether the entities in your problem domain
    naturally have a tree-like structure to them. If so, then it might be
    worth it to stick with trees in your program that reflect the structure of
    the problem domain, and use the queue-based algorithm mentioned below.
    Otherwise, it might be worth chucking the trees in favour of the acyclic
    directed graph (http://en.wikipedia.org/wiki/Acyclic_directed_graph).

    A "directed graph" basically means that edges between nodes have
    directions associated with them. Here's a non-directed graph:

    a---b----c
    | |
    | |
    +--------+

    And here's a directed graph:

    a-->b<-->c
    | ^
    | |
    +--------+

    An acyclic directed graph is simply a direct graph in which there are no
    cycles. Or to put it another way, it's a graph in which when you follow
    the directions of the arrows, no matter where you start, it's impossible
    to end up in the same location you've been to previously.

    The above directed graph is not acyclic, because you can start at C, then
    go to B, then go to C again. If you make this minor change, the graph
    becomes an acyclic one:

    a-->b<---c
    | ^
    | |
    +--------+

    From A, you can go to B or C. At B, you're stuck. And C, you can only go
    to B. There's no way for you to visit a node twice while following the
    edges.


    >> If not, you might instead want to
    >> look into using a directed acyclic graph, where each edge in the graph
    >> represents a dependency. That way, when a change in one table occurs,
    >> it
    >> can notify all of its dependents (which may be children, nephew/nieces)
    >> who in turn notify their dependents and so on.

    >
    > Actually, that's part of how I was thinking of using the tree. Whenever
    > the
    > table data was changed, update() was called and would step through all
    > the
    > dependent tables. The problem, as I've said, is I didn't have them
    > listed
    > by level, but just by following a branch.


    Dependencies are usually best modelled as an acyclic graph. To take
    your earlier example, with nodes A, B, C, D, E, F, G, the graph would look
    like:

    ,-<-B<-.
    E<-\ / \
    *-<-*---<-C<---*-<-A
    F<-/ \ /
    `-<-D<-'

    That is, A has 3 edges, one pointing to B, one pointing to C and one
    pointing to D. B, C and D each have 2 edges, one pointing to E, and one
    pointing to F.

    When you do your updates, you just follow all possible paths along the
    graph. So if you update B, you know you also need to update E and F. When
    you update A, you know you need to update the whole graph.

    The reason the graph needs to be acyclic is to avoid infinite update
    looks. Let's say you had the following cyclic graph:

    A<-->B

    And you wanted to update A. This would trigger an update in B, which would
    then trigger an update in A, and so on back and forth forever.

    An easy way to implement this is to have each node (or table) keep a list
    of all of the other nodes it needs to notify when it gets updated. So A
    would keep B, C and D in its list. B would keep E and F in its list, and
    so on.


    >
    >> Otherwise, if the tree structure is important, you could modify
    >> your
    >> updating-algorithm so that it uses a breadth-first traversal instead of
    >> a
    >> depth-first traversal. Usually this means making your method
    >> non-recursive, and instead having a queue with a list of nodes that
    >> need
    >> to be updated, and you iterate over the queue until it's empty (meaning
    >> all your work is done). A breadth-first traversal means that all the
    >> nodes
    >> at level N will be updated before all the nodes at level N+1.

    >
    > Right now I'm experimenting with a loop that I wouldn't actually label
    > as
    > recursive but is close. It starts with a table, makes that table the
    > first
    > node in the list, then the loop starts. It gets the children of that
    > table
    > and makes a list with them as nodes and that new sublist becomes the
    > next
    > node in the main list. Then it looks at all the grandchild tables and
    > makes another sublist of them and that becomes the 3rd node on the main
    > list. I end up with a main list and each node is a sublist. The first
    > sublist is only 1 item long, containing the initial table. The 2nd
    > node/sublist is all the children, the 3rd node/sublist is the
    > grandchildren
    > and so on.
    >
    > I looked into it several ways since I don't like writing a loop to
    > gather
    > data, then another to go through that same data, but found if I tried
    > one
    > loop to process, there were times I'd have to step back one level, so I
    > decided to list it all. The only actual recursion at this point is
    > getting
    > a list of tables from one table, then doing the same from each table in
    > the
    > list.


    What you've written is essentially what I described as being a
    breadth-first traversal using a queue (except you need not make these
    sublists). I think generally, it would not be considered a form of
    recursion. I think (but am not sure) that the technical definition of
    recursion requires a method to call itself either directly or indirectly.

    To clarify a potential confusion: when you're using this breadth-first
    traversal algorithm you need to be working with the tree data structure,
    and not the acyclic directed graph data structure.

    Recall that the tree was:

    A
    |
    +-+-+
    B C D
    | |
    E F

    with A as the root, B, C, D as its children, and E the child of B, F the
    child of C.

    If you wanted to update A, for example, you'd add A to the queue. Now,
    you take the first element out of the queue (which is "A", leaving the
    queue now empty), and then you do whatever updates you need to do on "A",
    and then add all of its children in the queue (B, C and D). If the queue
    is empty, you're done. But it's not empty, so you repeat: Take the first
    element out of the queue (which is "B", leaving the queue as {C,D}),
    update it, and add all of B's children to the queue (the queue is now
    {C,D,E}). You keep repeating this until the queue is completely empty,
    which should result in your processing each node exactly once.

    The drawback of this algorithm is that you must always process the
    entire tree. That is, you cannot, for example, only update B and its
    dependents, because adding B to the queue will eventually trigger the
    processing of E, but you'll miss the processing of F.

    Having the dependency list as an acyclic graph allows you to only
    process the parts of the trees that need to be processed.

    - Oliver
     
    Oliver Wong, Jul 13, 2007
    #19
  20. Hal Vaughan

    Hal Vaughan Guest

    Roedy Green wrote:

    > On Thu, 12 Jul 2007 05:34:12 -0400, Hal Vaughan
    > <> wrote, quoted or indirectly quoted someone
    > who said :
    >
    >>
    >>Thanks for suggestions!

    >
    > have a look at javax.swing.tree.DefaultTreeModel.
    >
    > I have not looked closely, but it may be suitable for non-GUI use too.


    That was one thing I considered, but was hoping to find one already
    existing. With my limited experience, I'm surprised to find that there are
    data types I know about that aren't easily implemented in Java.
    DefaultTreeModel was close, but I could not get all the nodes in one level
    easily.

    Thanks for the idea!

    Hal
     
    Hal Vaughan, Jul 14, 2007
    #20
    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. Mike Chen
    Replies:
    6
    Views:
    527
    Mike Chen
    Jan 29, 2007
  2. steve
    Replies:
    3
    Views:
    268
    Paul Boddie
    Oct 23, 2006
  3. Ramon F Herrera
    Replies:
    2
    Views:
    549
    Nigel Wade
    Oct 29, 2007
  4. Replies:
    14
    Views:
    458
    Jerry Coffin
    Feb 17, 2008
  5. A
    Replies:
    27
    Views:
    1,648
    Jorgen Grahn
    Apr 17, 2011
Loading...

Share This Page