Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# data structure suggestion

Posted on 1998-10-27
Medium Priority
175 Views
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
Question by:mabo
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 3

Expert Comment

ID: 1253869
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

LVL 84

Expert Comment

ID: 1253870
a directed graph

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

LVL 10

Expert Comment

ID: 1253871
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 Comment

ID: 1253872
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

LVL 10

Expert Comment

ID: 1253873
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 Comment

ID: 1253874
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

LVL 10

Accepted Solution

RONSLOW earned 1560 total points
ID: 1253875
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 Comment

ID: 1253876

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 Comment

ID: 1253877

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

LVL 10

Expert Comment

ID: 1253878
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 Comment

ID: 1253879

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 Comment

ID: 1253880

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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: Iâ€™ve never triâ€¦
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn hoâ€¦
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
###### Suggested Courses
Course of the Month10 days, left to enroll