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

java-programmer, Is There a Java Class for this Kind of Data Structure? 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

java-programmer >> Is There a Java Class for this Kind of Data Structure?
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.

java-programmer >> Is There a Java Class for this Kind of Data Structure? 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

java-programmer >> Is There a Java Class for this Kind of Data Structure? In article <email***@***.com>,
Hal Vaughan <email***@***.com> 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 - email***@***.com - http://www.pvv.org/~bcd
powered by emacs

java-programmer >> Is There a Java Class for this Kind of Data Structure?
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.

java-programmer >> Is There a Java Class for this Kind of Data Structure?
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>

java-programmer >> Is There a Java Class for this Kind of Data Structure?
"Hal Vaughan" <email***@***.com> wrote in message
news:email***@***.com...
>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

java-programmer >> Is There a Java Class for this Kind of Data Structure? 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

java-programmer >> Is There a Java Class for this Kind of Data Structure?
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>

java-programmer >> Is There a Java Class for this Kind of Data Structure?
"Hal Vaughan" <email***@***.com> wrote in message
news:email***@***.com...
>
> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure? Oliver Wong wrote:

>
> "Hal Vaughan" <email***@***.com> wrote in message
> news:email***@***.com...
>>
>> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure?
"Hal Vaughan" <email***@***.com> wrote in message
news:email***@***.com...
> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure? Oliver Wong wrote:

>
> "Hal Vaughan" <email***@***.com> wrote in message
> news:email***@***.com...
>> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure? "Hal Vaughan" <email***@***.com> wrote in message
news:email***@***.com...
> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure? Oliver Wong wrote:

> "Hal Vaughan" <email***@***.com> wrote in message
> news:email***@***.com...
>> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure?
"Hal Vaughan" <email***@***.com> wrote in message
news:email***@***.com...
> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure? Oliver Wong wrote:

>
> "Hal Vaughan" <email***@***.com> wrote in message
> news:email***@***.com...
>> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure?
"Hal Vaughan" <email***@***.com> wrote in message
news:email***@***.com...
> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure? Roedy Green wrote:

> On Thu, 12 Jul 2007 05:34:12 -0400, Hal Vaughan
> <email***@***.com> 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

java-programmer >> Is There a Java Class for this Kind of Data Structure? Oliver Wong wrote:

>
> "Hal Vaughan" <email***@***.com> wrote in message
...
> 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.

I checked out the Wikipedia article on acyclic directed graphs. In some
ways that is close to what I was doing. Each table contained a list of its
dependent tables and, of course, they had lists of their dependent tables
too. I made sure they always went to the next level so no path would go to
a table on the same or a previous level.

> 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".

It's a setting editor for another system (which is mostly in Perl, since it
handles a LOT of text). For various reasons, I don't want this program
interacting directly with the database, in part because this would be
accessible from the web and nothing else is. The settings data from the
database is converted to text in what is almost XML, but is something I set
up that made it easy to read and write the data easily and quickly from
Java and Perl, saved in files on the server, and this reads them in and
creates the tables. Basically, this program is a GUI that lets me edit the
settings quickly with point-and-click which, for me, is much faster than
dealing with all the SQL commands and the interrelations of the different
settings.

> 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).

After what you're saying, I'd say it's more in the acyclic directed graph.
I had never heard of a data structure like that before, but it fits better
than a tree.

Side note here: on some forums when I ask questions like the one I started
with, I get treated like I'm an idiot because I don't know what a lot of
people think is something basic. On this group, I've noticed that it may
happen once in a while, so I usually include that I'm self taught in my
first post. I've found that once people see that I have taught myself,
they understand why there are holes in what I know and people here often
give me a lot of info that goes way beyond answering my current question
and helps me later.

[A good explanation of acyclic directed graphs snipped for brevity.]
...
> 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.

I didn't really know what recursion was until after I had created several
recursive subroutines on my own. Then I found that "recursion" described
what I had been doing. All the examples I saw were routines calling
themselves, but when I thought about it, and what I did here amounted to
something like this:

while (!isDone) {
//All sorts of stuff to be done
if (no more tables)
isDone = true;
}

It doesn't call itself, but it keeps going and repeating itself until it's
done. It does essentially the same thing as a recursive subroutine. I did
something slightly different. I used a LinkedList and each node is another
LinkedList of all the tables on a particular level that need updating, so I
did this:

private void updateTables(MyTable firstTable) {
int iLevel = 0;
LinkedList updateTables = new LinkedList(), oneLevel = new LinkedList();
oneLevel.add(firstTable);
updateTables.add(oneLevel);
while (intLevel < updateTables.size() {
//Go through all the tables in oneLevel and get a list of all their child
// child tables. Put them in a new LinkedList and add it to updateTables as
// the next node. If there are none, we don't add a node to updateTables so
// it doesn't increase in length, but intLevel will increase and be the
// same as the size of updateTables. That is the flag that we're out of
// dependent or child tables
intLevel++;
}
// code to go through updateTables and update all tables we've found.
return;
}

[More of explanation snipped for brevity]
...
> 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.

What I've ended up with is a routine that will start at any table, start
reading all the dependent ones from it, then get their dependents and so
on. It tracks which level each one is on and update them by going through
each level and updating each table in that level before moving on to the
next. I can start on the root table or on any other tables after it and
still do the same thing.

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

At this point, I've got something that does close to that. Maybe I figured
it out without the actual terms?!

Thank you for all the time and effort I know it took to write up a clear
explanation. It was a help!

Hal