EDIT: The most general case I need is not a tree but any Directed Acyclic Graph.
I have a directed acyclic graph.
I need to sort it in a list so that in the list every node comes after any node it can walk to in the graph.
So far so good, just use a topological sorting algorithm.
However, I have an additional constraint: Each node in the graph is colored, and I need to find a sorting so that the list is as cohesive as possible. In other words, if you walk the list, you should see a change in colors as few times as possible.
I need an efficient algorithm. No iterating through all possible sortings.
The set of colors is typically much smaller than the set of nodes in the graph.
If no efficient exact algorithm is possible, I would be happy with a heuristic one that is likely to produce good results.
There is some information that one could potentially use for the heuristic: The colors are also partially ordered, and this ordering of the colors is correlated to the ordering of the nodes. I.e. a node is likely (but not guaranteed) to have a color that is "smaller than" the color of its parent node.
You can think of the problem this way: I have a set of jobs, and each job can depend on the output of several other jobs (if x depends on y there is an arrow from x to y). There is an overhead associated with setting up the data needed for each job, but this overhead is significantly reduced if the previous job had the same "color". The whole set of jobs is typically executed many thousand times, so if one can find an not too expensive way to improve the order of the jobs, that will pay off.
So far I have come up with this algorithm which works well most times, but not always:
Define the order "<=" so that x <= y if y can walk to x in the graph.
find any topological sort of the nodes and put it in the list L (L is sorted from smallest to largest w.r.t the partial ordering "<=" )
W = 
for x in L:
find the earliest y in W so that color(x)==color(y) && there is no z in W with z > y and x > z
if y exists:
insert x in W after y.
if y does not exist and there is no z in W with x > z:
place x at the beginning of W
place x at the end of W
for each continuous group G of colors in W:
for x in G in reverse order:
find the latest y in W so that color(x)==color(y) && there is no z in W with z > x and z < y
if y exists:
move x directly before y in W
The second pass may seem a little puzzling, but it is just my experience that it tends to improve the results. I.e. some times it will be able to move one whole group of colors past another group and join a third group of the same color.
I think the reason that the first pass is not sufficient is that there can be complicated interdependencies between the nodes that are sorted in L after the current x you are looking at, and so you can't know the optimal placement of x in the first pass, you just have to go with something.
Any help would be great!