Ready to showcase your work, publish content or promote your business online? With Squarespace’s award-winning templates and 24/7 customer service, getting started is simple. Head to Squarespace.com and use offer code ‘EXPERTS’ to get 10% off your first purchase.
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
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
Asked:
-
6
-
4
- +1
1 Solution
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...
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.
Join & Write a Comment Already a member? Login.
Featured Post
There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.
Tackle projects and never again get stuck behind a technical roadblock.
Join Now
see
http://www.cs.sunysb.edu/~algorith/implement/c.shtml
for listings of some books on the topic