-1

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?

user330612
  • 2,189
  • 7
  • 33
  • 64

1 Answers1

1

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.

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>

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.

Dan D.
  • 73,243
  • 15
  • 104
  • 123