3
$\begingroup$

Example TreeProvided is a tree with three types of node. The structure of the tree cannot be modified and traversal of the tree is limited to querying a node for its children or its parent.

The objective of the algorithm is to traverse the tree from the root node and collect all of the valid combinations of the data in the tree.

A node of type 1 is an occluding node. Any node that is a child of this type of node cannot “see” the data in the other branches of the parent type 1 node. In the diagram there are two instances of type 1 nodes, Y and Z. Note that the Y instance occurs twice. Type 1 node instances can occur multiple times in the tree and can be at any level below the root. Separate occurrences - of a single instance of a type 1 node - always have the same number of branches as children, but will contain different data. The branches of a type one node have known labels.

Nodes of type 1 can occlude other nodes of type 1. For example, if we take the left branch of Node Z on the diagram (to Node M), then the instance of Node Y on the right branch of Z is occluded from Node M (its data cannot be combined with data from Node M). Therefore, data nodes B and C will never combine with D, E, or F.

Only data from the same branch of two instances of a type 1 node can be combined. So, given two occurrences of an instance of a type 1 node, the data from each branch of one will only combine with the data from the identical branch of the other instance. Therefore, the data in the two occurrences of node Y on the tree will combine to the pairs DG, EH, and FI (never DH or EI, etc.).

A node of type 2 is a simultaneous node. Any node that is a child of this type of node can combine with the other children of any non-occluded node in the tree. Of course, if a child of the type 2 node is a type 1 node, then all the rules of type 1 nodes apply for children of that type 1 node. Type 2 nodes can have children of any type.

A node of type 3 is a data node. These nodes contain information that can be combined with information from other data nodes. The collection of these nodes into valid combinations is the goal of our tree traversal. There are no restrictions on the parent-child relationships of node types. A node of type 1 can be a child of a node of type 2 and vice versa. Type 1 and 2 nodes can be children of type 3 nodes. The data in a type 3 node with children of type 1 or 2 will be visible to all its children and to all other simultaneous non-occluded nodes in the tree.

The root node of the tree is of type 2, simultaneous.

Calling the function to retrieve the children of a node may return null, indicating a leaf has been reached.

The output of the algorithm should be the set of all “valid” data combinations. That is, the set of all combinations of the data that accounts for occlusions of the type 1 nodes in the tree and all simultaneous data from non-occluded areas across the tree.

A summary of the rules:

Type 1

  • Type 1 nodes occlude data in their branches (i.e. data in one child branch cannot be combined with data in another).
  • Type 1 node instances may occur multiple times and at any level below the root of the tree.
  • The branches of a type 1 node are labeled and match across occurrences of the same instance.
  • The data in branches of a type 1 node can only be combined with other non-occluded simultaneous data or the data from the same branch of another occurrence of the type 1 node.

Type 2

  • Type 2 nodes are simultaneous, meaning that data from any of its branches should be combined with other non-occluded data in the tree.
  • Type 2 nodes can have multiple children of different types.

Type 3

  • Type 3 nodes are data nodes, they are combined together to form valid outputs of the traversal algorithm.

General Tree Rules

  • Any node type can be the parent/child of any other node type. The tree’s structure is unknown before traversal, there is no guarantee of balance or foreknowledge of the depth of the tree.
  • Traversal begins from the root node of the tree.
  • The root of the tree is a type 2 node.
  • There are no restrictions on the number of branches a node can have.

Traversal can be done by calling two functions:

  • One that either returns null (at a leaf) or a collection of the children of the current node.
  • Another that returns the parent of the current node.

Given these rules, the valid data combinations for the example tree provided are: ABCG, ABCH, ABCI, ADG, AEH, and AFI.

This description is the best way I can distill the problem to its essential components. The example I gave doesn't reflect all the possible relationships between nodes in the tree (I don't have any type 3 nodes with children, for example). Any help with ways to break the problem down, simplify, and approaches to solving this problem would be most appreciated.

What I would like from the CS StackExchange community:

I need help finding an algorithm to traverse the tree efficiently and collect all the data, preferably with as few big O operations as possible (i.e. lowest number of traversals and post processing). The data I'm pulling from can range from tens of possible data combinations to hundreds of millions.

What I have done so far:

I have developed an algorithm that does a depth first traversal of the tree and creates a list of paths through the tree with records of the type 1 node branches traversed by the path. I loop over the results, checking to see if the branches taken by the permutations of the paths conflict. I aggregate all these results into a set of valid path combinations. There are several loops due to different data types and tons of comparison operations to compare branches. This approach is effective for small n, but fails when my tree becomes sufficiently complex and/or large.

Why I am asking this question:

I wouldn't really begin to know how to describe this problem in order to search for similar answers. I'd also have to search across multiple communities.

$\endgroup$
  • $\begingroup$ I have read the whole post - I do not feel like the whole description is really needed, and it seems that you have problem in aggregating results? $\endgroup$ – Evil Apr 14 '16 at 0:57
  • $\begingroup$ I was just attempting to give a full description of the situation. As I do not have any formal CS education, I don't know how to simplify the explanation. Yes, the difficulty in aggregating the results comes from the fact that I am creating an intermediate format of the data collected from the tree and running the permutations of all the paths through the tree, checking for valid combinations. I don't believe this is the most efficient approach. I think I could do more while traversing the tree. $\endgroup$ – TorrentialFire Apr 14 '16 at 1:21
  • $\begingroup$ Ok. It is indeed full description of the tree. How do you store combinations? Why do you store paths instead of combinations? It looks like you first perform full DFS, and then merge paths for results? Maybe you could retreive partial results and stick to only one traversal? $\endgroup$ – Evil Apr 14 '16 at 1:44
  • $\begingroup$ I store paths because I don't know what data structure in which to store combinations. I took - what I assume is naive - the route of storing the path to each piece of data in a path and then checking for each valid combination. $\endgroup$ – TorrentialFire Apr 14 '16 at 1:52
  • $\begingroup$ My "combinations" end up being lists of the paths to the data that validly combine. $\endgroup$ – TorrentialFire Apr 14 '16 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.