2
$\begingroup$

I have an n-ary tree and I want to get all possible representations of the tree that "cover" (for lack of a better term) the tree. Here's what I mean by cover:

Suppose we have the following tree

        1
     /    \
    2      3
   / \    /|\
  4   6  5 7 8
      |
      9

I want to somehow obtain the following:

  • 1
  • 2, 3
  • 2, 5, 7, 8
  • 4, 6, 3
  • 4, 6, 5, 7, 8
  • 4, 9, 3
  • 4, 9, 5, 7, 8

As you can see 1 completely covers the tree because all leaves are underneath it. Similarly 2, 3 covers the entire tree because all leaves are underneath them. This goes for all of them until finally we get to 4, 9, 5, 7, 8 which covers the entire tree because all leaves are underneath (or are them).

Is there an algorithm to do this or a modification of a classic search algorithm that will produce this?

$\endgroup$
  • $\begingroup$ I have figured out a crummy recursive way to do this, I will post it below tomorrow afternoon when I get a chance. $\endgroup$ – Nick Chapman Mar 9 '17 at 6:56
2
$\begingroup$

Let $T$ be a tree with root $r$, and let the children of $r$ be $r_1,\ldots,r_d$. Then every minimal cover of $T$ either consists of $r$, or is a union of minimal covers of $r_1,\ldots,r_d$; if $r$ is a leaf then the second option doesn't exist. You can easily convert this to a recursive algorithm that lists all minimal covers.

$\endgroup$
0
$\begingroup$

Yuval was moving in the right direction.

Here's the pseduo code:

def get_tree_covers(node):
    node_covers = []
    if node is NULL:
        return node_covers
    node_covers.append(node.value)
    if node.children is NULL:
        return node_covers
    child_covers = [] // Used to store the covers of each child
    for child in node.children:
        child_covers.append(get_tree_covers(child))
    if child_covers.length == 1:
        tree_covers = join_lists(tree_covers, child_covers[0])
        return tree_covers
    joined_covers = child_covers[0]
    for i in range(1 to child_covers.length):
        new_tree_covers = []
        for j in range(0 to joined_covers.length):
            for k in range(0 to child_covers[i]):
                new_cover = joined_covers[j] + child_covers[i][k]
                new_tree_covers.append(new_cover)
        joined_covers = new_tree_covers
    tree_covers = join_lists(tree_covers, joined_covers)
    return tree_covers

The runtime is abysmal and I would love to know if anyone can come up with anything quicker. Worst case this thing runs in O(max_branch_lengh^number_of_branches) which is really bad. For my use case it works out all right because I'm using it on very small trees so we're talking at most a few hundred operations. But on a larger tree this would really kill your runtime.

$\endgroup$
  • $\begingroup$ I'm not sure that the running time is abysmal in the number of covering representations. $\endgroup$ – Yuval Filmus Mar 11 '17 at 12:57
  • $\begingroup$ @YuvalFilmus what do you mean in the number of covering representations? $\endgroup$ – Nick Chapman Mar 12 '17 at 0:37
  • $\begingroup$ I mean the size of the output. $\endgroup$ – Yuval Filmus Mar 12 '17 at 10:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.