x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 185

# data structure suggestion

A few months ago I posted a question in here
http://www.experts-exchange.com/topics/comp/lang/c/Q.10068034
which was about keyword searching but not very clear in what I wanted to do....now..finally I got a clear idea....so here is the revised version....

I want to build a tree ( or any other data structure ) where each node can have any number of child nodes and each child node can belong to any number of parent nodes. I want to do a bottom up search in order to find all those child nodes which have common parent nodes somewhere in this hierarchial structure .....

I think this hierarchial structure will be very highly interlinked...so there is a possibility that they may be cylic...and I may go into infinite loops....

can some suggest an effective algorithm/data structure?
thanks
0
mabo
1 Solution

Commented:
the correct name for the data stucture is a graph
see
http://www.cs.sunysb.edu/~algorith/implement/c.shtml
for listings of some books on the topic

0

Commented:
a directed graph

one common representation for a highly connected graph is a connectivity matrix.
0

Commented:
If your data is truely dynamic, I'd suggest something like this...

typedef struct Node Node;

Node* pParent;
Node* pChild;
};

struct Node {
Link* pChildren; /* all children of this node */
Link* pParents; /* all parents of this node */
/* other data */
};

}

You might want to use doubly linked lists for the pSameParent and pSameChild to make deletion easier (if you ever delete a relationship).

I'm not sure what your requirements are for the algorithm(s).  Do you want a list of all children that have the same given ancestor?  Or do you want to find a common ancestor for a given pair (or set) of children? Or what?

0

Author Commented:
Thanks for all the responses....
>Do you want a list of all children that have the same given >ancestor?  Or do you want to find a common ancestor for a given >pair (or set) of children? Or what?

the answer is I want to find common ancestor(s)for a given pair (or set) of children...but How?...I have no idea....
The problem is I have to do a bottom up search and check for common ancestor(s) at each level of the hierarchy....

any suggestions....
0

Commented:
I'd build a list of ansectors for the first child (including itself), following each path up until there is not parent, or until a parent is reached that is already on the list.

Do the same for the next child in the set.

Now go thru the two lists of parents and remove any that are not in both lists.

Repeat for any other children.

If you only want the closest ancestors, then as a final step, I'd go through each parent in the remaining list of common ancestors and trace upwards.  If any of its ancestors are in the common ancestors list, then you can remove them.

0

Author Commented:
here is one last request....since this structure is very interlinked....how can I find a particular node in shortest possible time?

I am still confused about the pSameParent and pSameChild pointers...can you explain why do we need these two pointers?
0

Commented:
If you only had a single parent for each child, but unlimited children per parent, then you would need a list of pointers-to-children for each parent.  eg.

Node* pChild; /* pointer to this child */
};

Here, your parent would have a pointer to a linked list of Link's, each of which pointed to a child of the parent.  The pSameParent pointer implements this linked list.  NOTE: With this system you would usually put a back pointer from child to parent in the child node itself (because there is only one parent)

In your case, you have both multiple children per parent AND multiple parents per child.

So the link between a parent and a child needs to point to BOTH the parent AND the child (it corresponds to a line in a directed graph).  As each child can have many parents, you need to be able to access all the Link's for a given child that point to each parent (just like the list of child pointers above), so we use the pSameChild pointer to keep this list.

Hence we get the structure...

Node* pParent;
Node* pChild;
};

If you start with a parent and follow the list of children, then you will traverse a linked list of Links (following the pSameParent pointer).  Each one of these will have have pParent pointing back to the parent node we started from, and each pChild pointing to successive children.

If you start with a parent and follow the list of parents, then you will traverse a linked list of Links (following the pSameChild pointer).  Each one of these will have have pChild pointing back to the child node we started from, and each pParent pointing to successive children.

Regarding finding a node ... what exactly do you mean by finding? Do you want to traverse the structure finding a node that matches a given criteria?  Well, you could keep a list of top level parents (ones that have no parents themselves) and traverse the children, keeping track of which children you have alrady visited, but that would be a lot of work.  Instead, I'd add a linked-list pointer to each node to link them together linearly (probably in order that you add them) and then traverse that list when trying to find a node.  ie.

struct Node {
Link* pChildren; /* all children of this node */
Link* pParents; /* all parents of this node */
Node* pNextNode; /* linked list of all nodes */
/* other data */
};

0

Author Commented:

By finding node I mean..say eg each node has a unique keyword stored in it...so if the user types that keyword then I want to find that keyword in my graph and then find all the parents/children of that particular node. Now the problem is my graph will be very large containing  millions of keywords, so if I have a linked list then  I have to traverse it and find that node but this is very time consuming because of the size of linked list (eg traversing millions of nodes and check if it matched a word).

I think we can have some kind of a structure (?) where in O(1) time it will give us the node matching a particular keyword and in this structure we can also store a pointer to that node in the graph, so after we find that node we can just follow the pointer and then traverse the graph.

any suggestions...
0

Author Commented:

By finding node I mean..say eg each node has a unique keyword stored in it...so if the user types that keyword then I want to find that keyword in my graph and then find all the parents/children of that particular node. Now the problem is my graph will be very large containing  millions of keywords, so if I have a linked list then  I have to traverse it and find that node but this is very time consuming because of the size of linked list (eg traversing millions of nodes and check if it matched a word).

I think we can have some kind of a structure (?) where in O(1) time it will give us the node matching a particular keyword and in this structure we can also store a pointer to that node in the graph, so after we find that node we can just follow the pointer and then traverse the graph.

any suggestions...
0

Commented:
In that case, set up a hash table with keywords and pointers to nodes.  Then, once you've found the node, you can traverse the links to get parents and children
0

Author Commented:

By finding node I mean..say eg each node has a unique keyword stored in it...so if the user types that keyword then I want to find that keyword in my graph and then find all the parents/children of that particular node. Now the problem is my graph will be very large containing  millions of keywords, so if I have a linked list then  I have to traverse it and find that node but this is very time consuming because of the size of linked list (eg traversing millions of nodes and check if it matched a word).

I think we can have some kind of a structure (?) where in O(1) time it will give us the node matching a particular keyword and in this structure we can also store a pointer to that node in the graph, so after we find that node we can just follow the pointer and then traverse the graph.

any suggestions...
0

Author Commented:

By finding node I mean..say eg each node has a unique keyword stored in it...so if the user types that keyword then I want to find that keyword in my graph and then find all the parents/children of that particular node. Now the problem is my graph will be very large containing  millions of keywords, so if I have a linked list then  I have to traverse it and find that node but this is very time consuming because of the size of linked list (eg traversing millions of nodes and check if it matched a word).

I think we can have some kind of a structure (?) where in O(1) time it will give us the node matching a particular keyword and in this structure we can also store a pointer to that node in the graph, so after we find that node we can just follow the pointer and then traverse the graph.

any suggestions...
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.