We value your feedback.
Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!
Course Of The Month
10 days, 13 hours left to enrollBecome a Premium Member and unlock a new, free course in leading technologies each month.
Solved
data structure suggestion
Posted on 1998-10-27
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
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
[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
- Learn & ask questions
-
6
-
4
- +1
12 Comments
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
see
http://www.cs.sunysb.edu/~algorith/implement/c.shtml
for listings of some books on the topic
If your data is truely dynamic, I'd suggest something like this...
typedef struct Link Link;
typedef struct Node Node;
struct Link {
Node* pParent;
Link* pSameParent; /* links for children of the same parent */
Node* pChild;
Link* pSameChild; /* links for parents of the same child */
};
struct Node {
Link* pChildren; /* all children of this node */
Link* pParents; /* all parents of this node */
/* other data */
};
Link* LinkParentToChild (Node* pParent, Node* pChild) {
Link* pLink = malloc(sizeof Link);
pLink->pParent = pParent;
pLink->pChild = pChild;
pLink->pSameParent = pParent->pChildren;
pParent->pChildren = pLink;
pLink->pSameChild = pChild->pParents;
pChild->pParents = pLink;
}
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?
typedef struct Link Link;
typedef struct Node Node;
struct Link {
Node* pParent;
Link* pSameParent; /* links for children of the same parent */
Node* pChild;
Link* pSameChild; /* links for parents of the same child */
};
struct Node {
Link* pChildren; /* all children of this node */
Link* pParents; /* all parents of this node */
/* other data */
};
Link* LinkParentToChild (Node* pParent, Node* pChild) {
Link* pLink = malloc(sizeof Link);
pLink->pParent = pParent;
pLink->pChild = pChild;
pLink->pSameParent = pParent->pChildren;
pParent->pChildren = pLink;
pLink->pSameChild = pChild->pParents;
pChild->pParents = pLink;
}
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?
Thanks for all the responses....
RONSLOW.... your asked....
>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....
RONSLOW.... your asked....
>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....
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.
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.
Thanks for your response RONSLOW...
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?
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?
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.
struct Link {
Link* pSameParent; /* links for children of the same parent */
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...
struct Link {
Node* pParent;
Link* pSameParent; /* links for children of the same parent */
Node* pChild;
Link* pSameChild; /* links for parents of the same child */
};
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 */
};
when you create a node, you add it to the head of the pNextNode linked list.
struct Link {
Link* pSameParent; /* links for children of the same parent */
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...
struct Link {
Node* pParent;
Link* pSameParent; /* links for children of the same parent */
Node* pChild;
Link* pSameChild; /* links for parents of the same child */
};
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 */
};
when you create a node, you add it to the head of the pNextNode linked list.
Again....thanks for your response..
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...
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...
Again....thanks for your response..
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...
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...
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
Again....thanks for your response..
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...
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...
Again....thanks for your response..
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...
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...
Featured Post
We value your feedback.
Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!
Question has a verified solution.
If you are experiencing a similar issue, please ask a related question
Summary:
This tutorial covers some basics of pointer, pointer arithmetic and function pointer.
What is a pointer:
A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
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
Earn Certification
HTML5 Specialist - Certification
Free withPremium
Course of the Month10 days, 13 hours left to enroll
628 members asked questions and received personalized solutions in the past 7 days.
Join the community of 500,000 technology professionals and ask your questions.