Re: Nary trees
--- Eric M. Monsler [EMAIL PROTECTED] wrote:
etienne buxin wrote:
hi,
i'd like to use a structure similar to glib's Nary tree, but with the difference
that many
parent
nodes can share one or several children nodes.
any clue?
This is going to be rather difficult.
Unless you enforce a policy that only sibling-nodes can share child
nodes, you are going to have a lot of trouble. Even then, any trivial
operation on a child node (e.g., remove from tree) will require
searching over the full set of parent-siblings and checking the child
pointers against the full set of siblings for the child-node.
Don't do it.
If a fellow developer at work suggested such a data-storage approach, I
would require a tone of convincing that this was a reasonable thing to do.
If you do, I strongly suggest that you do not base it off of the current
glib n-ary tree implimentation. At a minimum, I would enforce a policy
that a node has a numbered depth N, that all children are depth N+1 and
parents are N-1. This may seem obvious, but in a multi-parent scenario
it would be easy to violate if moving a set of nodes within the tree.
A suggested structure:
struct eb_manymany {
uint node_level;
uint num_parents;
uint num_par_max;
struct eb_manymany **par_ptr_array;
uint num_children;
uint num_child_max;
struct eb_manymany **chd_ptr_array;
gpointer data;
}
That lets you reference count the parents and children, so that, for
example, when removing a node you can go to all the parents and remove
that child from their list of children.
The _max allows dynamix allocation of the pointer arrays, if you
previously allocated space for 12 children and need a 13th, you can
reallocate that array up to size 24 or somthing, with 13 places occupied.
If the above doesn't make sense after a few readings, you're not ready
to tackle this. I have done a two-level parent-child that was
many-to-many, where entities were by definitions either parents or
children, and by the time I had the appropriate API and error checking
all in place it was very cumersome.
For example, what policy do you generically implement if a the last
parent of a node is freed? In my application, that meant that the child
was now a discard and could be freed, but that may or may not be
appropriate for a generic storage library. Specify a calllback for the
child node in that situation, defaulting to freeing? Complexity!
If you do get it working as infinite level many-to-many, please post the
code. :)
Eric
hello,
in fact, i'd like to create a structure to represent events. i investigated trees
because i need
a parent-child relationship between events, with the parent event being a consequence
of his child
events. Because one event may have several consequences, it must be able to have many
parents (of
different depht levels, moreover). i could duplicate the child for each of his
parents, but this
is not too good, because each event has _a lot_ of info carried with ( *data in glib's
Nary tree)
and this will consume a lot of ressources.
has someone an idea?
thanks,
E.
__
Do you Yahoo!?
Faith Hill - Exclusive Performances, Videos More
http://faith.yahoo.com
___
gtk-list mailing list
[EMAIL PROTECTED]
http://mail.gnome.org/mailman/listinfo/gtk-list
Re: Nary trees
etienne buxin wrote:
--- Eric M. Monsler [EMAIL PROTECTED] wrote:
A suggested structure:
struct eb_manymany {
uint node_level;
uint num_parents;
uint num_par_max;
struct eb_manymany **par_ptr_array;
uint num_children;
uint num_child_max;
struct eb_manymany **chd_ptr_array;
gpointer data;
}
(snip)
in fact, i'd like to create a structure to represent events. i investigated trees
because i need
a parent-child relationship between events, with the parent event being a
consequence of his child
events. Because one event may have several consequences, it must be able to have
many parents (of
different depht levels, moreover). i could duplicate the child for each of his
parents, but this
is not too good, because each event has _a lot_ of info carried with ( *data in
glib's Nary tree)
and this will consume a lot of ressources.
has someone an idea?
The structure I proposed above should handle it, just remove the
node-level. Do you really mean that consequences are *parents* of
events, not *children* of events? My family tree reads differently, but
whatever.
Let me call them causes and consequences, rather than parents and children.
If your set of operations is fairly limited, you should be OK. For
example, if the API was only Add(with list of causes and consequences
pointers) and Remove(severing all cause/consequence, and also removing
all unconnected nodes caused), it shouldn't be too complex. Might be OK
for creating a user-traversable set of nodes for a visualization exercise.
But, attempting to traverse the mesh is going to be a really tough problem.
Good luck.
Eric
___
gtk-list mailing list
[EMAIL PROTECTED]
http://mail.gnome.org/mailman/listinfo/gtk-list
Re: Nary trees
etienne buxin wrote:
hi,
i'd like to use a structure similar to glib's Nary tree, but with the difference
that many parent
nodes can share one or several children nodes.
any clue?
This is going to be rather difficult.
Unless you enforce a policy that only sibling-nodes can share child
nodes, you are going to have a lot of trouble. Even then, any trivial
operation on a child node (e.g., remove from tree) will require
searching over the full set of parent-siblings and checking the child
pointers against the full set of siblings for the child-node.
Don't do it.
If a fellow developer at work suggested such a data-storage approach, I
would require a tone of convincing that this was a reasonable thing to do.
If you do, I strongly suggest that you do not base it off of the current
glib n-ary tree implimentation. At a minimum, I would enforce a policy
that a node has a numbered depth N, that all children are depth N+1 and
parents are N-1. This may seem obvious, but in a multi-parent scenario
it would be easy to violate if moving a set of nodes within the tree.
A suggested structure:
struct eb_manymany {
uint node_level;
uint num_parents;
uint num_par_max;
struct eb_manymany **par_ptr_array;
uint num_children;
uint num_child_max;
struct eb_manymany **chd_ptr_array;
gpointer data;
}
That lets you reference count the parents and children, so that, for
example, when removing a node you can go to all the parents and remove
that child from their list of children.
The _max allows dynamix allocation of the pointer arrays, if you
previously allocated space for 12 children and need a 13th, you can
reallocate that array up to size 24 or somthing, with 13 places occupied.
If the above doesn't make sense after a few readings, you're not ready
to tackle this. I have done a two-level parent-child that was
many-to-many, where entities were by definitions either parents or
children, and by the time I had the appropriate API and error checking
all in place it was very cumersome.
For example, what policy do you generically implement if a the last
parent of a node is freed? In my application, that meant that the child
was now a discard and could be freed, but that may or may not be
appropriate for a generic storage library. Specify a calllback for the
child node in that situation, defaulting to freeing? Complexity!
If you do get it working as infinite level many-to-many, please post the
code. :)
Eric
___
gtk-list mailing list
[EMAIL PROTECTED]
http://mail.gnome.org/mailman/listinfo/gtk-list
