Как раскрасить узлы дерева фиксированным набором цветов?

Question

У меня есть дерево иерархии сотрудников, для которого я хочу применить цвета. Я могу использовать только максимум 10 цветов, так как больше цветов делает его слишком запутанным для пользователей. Какую логику или алгоритм я могу использовать, чтобы раскрасить дерево набором цветов? Есть ли методы, как это сделать? Сначала я думал найти 10 поддеревьев в дереве, используя BFS, а затем покрасить их по-разному. Если на первом уровне есть>10 дочерних элементов, то не применяйте цвет, а если есть< 10 узлов, продолжайте снижаться, пока мы не найдем 10 поддеревьев для цвета. Это правильный взгляд на эту проблему? Эми больше идей?

Answer 1

Вы хотите, чтобы каждый соседний узел был другого цвета? Родители отличаются от всех своих детей, а братья и сестры отличаются друг от друга? С цветами в противном случае случайно назначены?

Старый код не отвечал требованиям, которые я к нему предъявлял, поэтому я написал новую версию кода, которая намного лучше, поскольку она итеративна. И я гораздо больше удовлетворен тем, что он делает то, что соответствует описанию, которое я изложил выше.

Если так, то начните с набора всех цветов C, выберите один для родителя, давайте назовем его P для каждого из детей, идущих слева направо, раскрасьте их из набора C - {S,P} где S это цвет левого брата этого узла. Повторите это для каждого из детей с набором C - D где D - цвет этого потомка, за исключением того, что вы уже выбрали цвет узла.

Большая часть этого все еще верна, но вместо глубокой первой рекурсии я переключаюсь на итеративный обход порядка уровней:

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

Ниже приведен переформатированный вывод. Обратите внимание, что ни один из дочерних элементов не имеет того же цвета, что и его родитель, ни того же цвета, что его левый брат или дочерний элемент на том же уровне слева от него.

<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 цвета (более просто делает его более ярким). Рассматривать:

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

Это был бы древовидный эквивалент таблиц с зебрами. Настоящим я называю эту полосатую зебру.