Есть дерево произвольной высоты и ветвистости. Некоторые произвольные вершины сгруппированы, т.е. условно помечены некоторым тэгом. Нужно нарисовать дерево на плоскости так чтобы вершины с одинаковым тэгом оказались возможно близко друг к другу.
Например (слева просто дерево, справа с выполнением требования о близости сгруппированных вершин):
1|x 3 5|x 7 7 5|x 1|x 3 (иксы рядом)
\ / \ / \ / \ /
2|y 6 8|y 6 2|y 8|y (игреки рядом)
\ | / \ | /
\ | / \ | /
\ | / \ | /
\ | / \ | /
\ | / \ | /
\|/ \|/
4 4
Один тэг может быть на разных ярусах, точного решения может не быть, основная цель - красивая картинка где вершины с одним тэгом сгруппированы, поэтому вообще вершины можно двигать произвольно если это не создаст пересечений между рёбрами дерева, но может быть стоит и наоборот, ограничить возможные положения каждой вершины (как на картинке выше - по высоте) и плясать только от порядка потомков в каждом узле.
Есть ли название у этой задачи, какие есть пути решения?
Пока идеи такие:
- Можно решать чисто от порядка вершин, т.е. ввести меру расстояния между двумя вершинами с одним тэгом (= число вершин между ними без этого тэга), и минимизировать сумму таких расстояний для всех пар. Чем такое можно делать (алгоритмы, библиотеки)? Быстрее чем за факториал, понятное дело.
- Можно решать от размещения вершин на плоскости
- Планаризация графа, причём довольно хитрая - вводим новые рёбра так чтобы вершины с одним тэгом образовали полный граф, и планаризируем (алгоритмы, библиотеки?) учитывая только пересечения новых рёбер с рёбрами дерева с весом 1 и рёбер дерева между собой с бесконечным весом.
- Модель пружинок и зарядов, но кажется что чтобы она сошлась нужно начать с чего-то подготовленного одним из способов выше.
