Каскадний граф - поширена структура даних в програмуванні і часто застосовується в алгоритмах. Вміст цієї структури важко піддається дослідженню під час налагодження, в силу того, що практично завжди описується одним вузлом посилаються на своїх нащадків. Тобто щоб отримати значення деякого вузла, доводиться виконувати нетривіальний обхід дерева. І тут на допомогу може прийти візуальне уявлення такого графа. Побудова графа у вигляді компактного і легко сприймається дерева, завдання нетривіальне і має безумовно безліч рішень. У статті хотілося б поділитися власним "колесом" для вирішення цього завдання.
У статті мається на увазі, що в будь-який момент часу можна отримати інформацію про нащадків конкретного вузла дерева. Посилання на вузол-предок не обов'язкові, тому що присутні не у всіх представлених дерев.
- Point - описує точку з координатами x і y;
- Dimension - визначає обсяг. Містить поля hight і width;
- Rectangle - описує прямокутник його розмірами і координатами верхнього лівого кута;
- TreeModel - описує дерево. Дозволяє отримувати нащадків і їх кількість для конкретного вузла.
Головною вимогою до алгоритму, була мінімальна кількість обходів дерева для обчислення координат кожного вузла.
Ідея запропонованого рішення полягає в тому, щоб розглядати в якості нащадкам не вузол окремо, а всі породжене їм дерево цілком:
Введемо поняття "грона". Гроно - це деяка структура даних, що посилається на вузол дерева і має посилання на такі ж "грона", відповідні нащадкам цього вузла.
До завдань грона входить обчислення параметрів області розташування вузла, на який вона посилається і обчислення власних габаритів.
По суті, гроно - це карта розміщення вузла і його нащадків.
Створення грон і обчислення координат верхнього лівого їх кута виконується при рекурсивном обході дерева в глибину:
Для наочного зображення ідеї, розглянемо приклад обчислення координат нащадків кореневого вузла 0. Алгоритм має на увазі, що до цього моменту координати вузлів 4-10 вже обчислені, і габарити дерев, породжуваних вузлами 1, 2 і 3 відомі (горизонтальне відстань між осередками в прикладі дорівнює 0 ):
