How to modify preorder tree traversal algorithm to handle nodes with multiple parents?

Question

I've been searching for a while now and can't seem to find an alternative solution. I need the tree traversal algorithm in such a way that a node can have more than 1 parent, if it's possible (found a great article here: Storing Hierarchical Data in a Database). Are there any algorithms so that, starting from a root node, we can determine the sequence and dependencies of nodes (currently reading topological sorting)?

Answer 1

The structure you described isn't a tree, it's a directed graph. As it would be suitable for hierarchical drawing you might be tempted to think of it as a tree (which itself is an acyclic connected graph).

Typical traversal algorithms for graphs are depth-first and breadth-first. The graph implementation is only different as it records the nodes it has already visited in order to avoid visiting certain nodes multiple times. However, if your data structure guarantees that it's acyclic, you can use tree algorithms on your graph by simply treating "parents" as "children".

I made a simple sketch to illustrate what I mean (the perfect chance to try Google Docs' new drawing feature):

As you see, it's possible to treat any graph that has an acyclic directed form as a tree and apply tree algorithms on it. As soon as you can't guarantee this property you'll have to go for dedicated graph algorithms.

Answer 2

A tree is basically a directed unweighted graph, where each vertice has N or less edges, and no cycles can happen.
If your'e certain there are no cycles in your tree, you could just treat a parent as another child of the specified node, and preform a preorder traversal normally.
However, if cycles might happen, you need graph algorithms.
Specifically: Breadth first search.

Answer 3

Just checking for maybe a simple case: can the two parents have different parents? If no you could turn them into single node (conceptually) and have a tree again.

Otherwise you will have to split the child node and duplicate a branch for the other parent. (This can of course lead to inconsistency and/or inneficient algorithms later, depending if you will need to maintain the data structure).

The above options hold if you insist on having the tree structure, which by definition can have only one parent.

So maybe you need to step back and explain what are you trying to accomplish and why it must be a tree structure if nodes can have two parents.

Answer 4

You aren't describing a tree here. You can NOT call your graph a tree.

A tree is an undirected graph without cycles. Parent/child relationship is NOT an interpretation of directions drawn on the edges. They are the result of naming one vertex the root.

We name a vertex "parent" to current, because it's the next one to the path to root. All other vertexes adjacent to current one are "children".

You can't just lay out an arbitrary graph in such a way that "parents" are "above" or "point to vertex", and children are "below" or "vertex points to them". A tree is a tree because a root is picked. What you depict in your question is not a tree. And tree traversal algorithms are NOT applicable to traversing arbitrary graphs.

There are several graph traversal algorithms, such as breadth-first search or depth-first search (check side notes in those pages for more). Use them instead of trying to tie your full-featured graph into your knowledge about trees.