Графическое дерево JavaScript с Layout - Основы

ОГЛАВЛЕНИЕ

 

 

Основы

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

  1. Узлы на одном уровне выровнены по прямой, а оси всех уровней параллельны.
  2. Родитель должен быть расположен центрально относительно своих дочерних элементов.
  3. Дерево и то же дерево, указанное в обратном порядке, может порождать разметку, которая является зеркальной относительно друг друга. Поддерево должно быть обработано одинаково независимо от того, где оно появляется в основном дереве.

Цель базового алгоритма по отношению к своим предшественникам заключалась в предоставлении решения, которое полностью удовлетворяло третье правило, соответственно располагая поддеревья относительно своих больших поддеревьев.

Рисунок 4. Пример, демонстрирующий разницу между принципами распределения алгоритмов.

Основными принципами алгоритма являются:

  • Обращение с каждым поддеревом как с независимой единицей, а передвижение узла предполагает передвижение всех его дочерних элементов.
  • Это выполнимо, если использовать предварительные координаты и модификатор для каждого узла. Передвижение узла подразумевает увеличение/уменьшение его предварительных координат и его модификатора, но только модификатор будет иметь значение для финальной позиции дочерних элементов узла. Тем самым, передвижение поддерева означает изменение модификатора корневого поддерева. Финальная позиция узла вычисляется путем суммирования предварительных координат узла со всеми модификаторами дочерних элементов.

Алгоритм работает в два этапа. Первый этап (firstWalk) является обходом в обратном порядке. Различные поддеревья обрабатываются рекурсивно со дна вверх и слева направо, позиционируя независимые элементы, образующие каждое поддерево, до того, как ни один из них не будет касаться другого. По мере обхода, меньшие поддеревья комбинируются, формируя большие поддеревья до того, как они достигнут корня. В этом процессе, apportion расположит на равном расстоянии более мелкие поддеревья, которые могли плавать между двумя большими связанными поддеревьями (для удовлетворенья 3-го правила о симметрии). Второй проход (secondWalk) является обходом в обратном порядке, который подсчитывает позицию конечного узла путем добавления всех модификаторов предшественников к предварительным координатам каждого узла.

К первому проходу можно осуществить оптимизацию, которая состоит в инкрементальной версии алгоритма Walker. Данная версия избегает пересчета предварительных координат узла и модификатора, когда изменения, сделанные по отношению к структуре дерева не подразумевают модификацию их значений. Данная оптимизация пока еще не реализована в данном компоненте.

Алгоритм также подстраивает подсчеты в случае, если разметка будет выполнена в другом направлении (то есть снизу вверх). Различные использования могут потребовать различные виды. Обычно традиционное расположение сверху вниз означает власть - к примеру, иерархию в организациях; при этом разметка снизу означает эволюцию или рост, как в биологии; а слева направо разметка может означать временную эволюцию.

Стоит отметить, что такой алгоритм универсальной разметки, как этот, не будет адекватным для относительно мелких деревьев. Деревья с большим числом узлов могут потребовать другую разметку и методы визуализации, такие как возможность увеличения, сдвига и фокусировки, сжатия некоторых, но не всех, дочерних элементов узла, добавления интерактивного поиска. Существует множество других решений для достижения тех же целей, включая (но, не ограничиваясь) гиперболические деревья, карты деревьев и т.д. Если вам необходимо больше информации по этой теме, то ее вы можете найти в сети интернета.