如何用一组固定的颜色为树节点着色? [英] How to color tree nodes with fixed set of colors?

问题描述

我有一个要为其应用颜色的员工层次结构树.我最多只能使用 10 种颜色，因为更多的颜色会让用户感到困惑.我可以用什么逻辑或算法来用一组颜色为树着色?有没有关于如何做到这一点的一些技术?我最初的想法是通过 BFS 在树中找到 10 个子树，然后对它们进行不同的着色.如果第一级本身有 >10 个孩子，则不要应用任何颜色，并且如果有 <;10 个节点然后继续向下直到我们找到 10 个要着色的子树.这是看待这个问题的正确方法吗?艾米更多的想法?

I have a employee hierarchy tree that I want to apply colors for. I can only use at max 10 colors since more colors make it too confusing to users. What is the logic or algorithm I can use to color the tree with a set of colors? are there some techniques on how to do this? My initial thinking was to find 10 sub trees in the tree by doing a BFS and then color them differently. If there are >10 children at the first level itself, then don't apply any color and if there are < 10 nodes then keep going down till we find 10 subtrees to color. Is this the right way to look at this problem? Amy more ideas?

推荐答案

您是否希望每个相邻节点的颜色都不同?父母不同于他们所有的孩子和兄弟姐妹彼此不同?颜色是随机分配的吗?

Do you want every adjacent node to be a different color? Parents different from all their children and siblings different from each other? With the colors otherwise randomly assigned?

旧代码不符合我对其提出的要求，因此我编写了一个新版本的代码，因为它是迭代的，所以效果要好得多.而且我更满意的是它符合我上面所述的描述.

The old code didn't meet the requirements I put on it and so I wrote a new version of the code that is much better as it is iterative. And I'm much more satisfied that it does what meets the description that I stated above.

如果是这样，那么从所有颜色的集合开始 C，为父级选择一个让我们为每个从左到右的子级调用那个 P它们从集合 C - {S,P} 中取出，其中 S 是此节点的左兄弟节点的颜色.对具有集合 C - D 的每个子节点重复此操作，其中 D 是该子节点的颜色，除非您已经选择了节点的颜色.

If so then start out with the set of all colors C, pick one for the parent lets call that one P for each of the children going left to right color them out of the set C - {S,P} where S is the color of the left sibling of this node. Repeat this for each of the children with the set C - D where D is the color of this child except that you have already picked the color of the node.

大部分仍然是正确的，但我切换到迭代级别顺序遍历而不是深度优先递归:

Most of that is still true but instead of depth first recursion I switch to iterative level order traversal:

import random

class Node(object):

    def __init__(self, children):
        self.children = children
        self.color = None

    def __str__(self):
        return  '<node {}>'.format(self.color) + ' '.join(str(c) for c in self.children) + '</node>'

def pick(s):
    return random.choice(list(s))

def assign_colors(node, set_of_colors):

    node.color = pick(set_of_colors)

    level = [node]
    while level:

        left_sibling = set()
        _level = []
        for node in level:
            for child in node.children:
                _level.append(child)
                child.color = pick(set_of_colors - (set([node.color]) | left_sibling))
                left_sibling = set([child.color])

        level = _level

test = Node([Node([Node([Node([]), Node([]), Node([]), Node([])]),
             Node([Node([]), Node([])]), Node([]), Node([])]),
             Node([Node([]), Node([]), Node([]), Node([])]), Node([])])

assign_colors(test, set([1,2,3,4]))

print test

assign_colors(test, set([1,2,3,4,5]))

print test

以下是重新格式化的输出.请注意，没有子级与其父级具有相同的颜色，也没有与其左侧同级或左侧相同级别的子级相同.

The following is the reformatted output. Note that no child has the same color as its parent nor the same as its left sibling or child on the same level to its left.

<node 3>
    <node 4>
        <node 2>
            <node 4></node>
            <node 1></node>
            <node 4></node>
            <node 1></node>
        </node>
        <node 1>
            <node 4></node>
            <node 3></node>
        </node>
        <node 3></node>
        <node 1></node>
    </node>
    <node 1>
        <node 2></node>
        <node 3></node>
        <node 2></node>
        <node 4></node>
    </node>
    <node 2></node>
</node>
<node 4>
    <node 2>
        <node 1>
            <node 5></node>
            <node 4></node>
            <node 2></node>
            <node 4></node>
        </node>
        <node 5>
            <node 3></node>
            <node 2></node>
        </node>
        <node 4></node>
        <node 3></node>
    </node>
    <node 5>
        <node 1></node>
        <node 4></node>
        <node 2></node>
        <node 3></node>
    </node>
    <node 1></node>
</node>

任何树都可以用最多 3 种颜色着色(更多只会使它更丰富多彩).考虑:

Any tree can be colored with at most 3 colors (more just makes it more colorful). Consider:

          1
      /   |   \
     2      3 2
  /  |  \
  1 3 1 3
/ |   \
3 2 3 2

那将是相当于斑马条纹表的树.在此，我将其命名为斑马条纹树.

That would be the tree equivalent of zebra striped tables. Hereby I name this zebra striped trees.

这篇关于如何用一组固定的颜色为树节点着色?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！