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

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.