Solved

data structure suggestion

Posted on 1998-10-27
12
156 Views
Last Modified: 2010-08-05
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
Comment
Question by:mabo
12 Comments
 
LVL 3

Expert Comment

by:traygreen
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

by:ozo
ID: 1253870
a directed graph

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

Expert Comment

by:RONSLOW
ID: 1253871
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?

0
 

Author Comment

by:mabo
ID: 1253872
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....
0
 
LVL 10

Expert Comment

by:RONSLOW
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

by:mabo
ID: 1253874
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?
0
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 
LVL 10

Accepted Solution

by:
RONSLOW earned 390 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.

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.


0
 

Author Comment

by:mabo
ID: 1253876
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...
0
 

Author Comment

by:mabo
ID: 1253877
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...
0
 
LVL 10

Expert Comment

by:RONSLOW
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

by:mabo
ID: 1253879
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...
0
 

Author Comment

by:mabo
ID: 1253880
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...
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

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…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now