Статьи

Эффективный и настраиваемый алгоритм TreeLayout в Java

Январь 18, 2018

Java TreeLayout, описанный ниже, создает макеты деревьев для произвольных деревьев. Он не ограничен определенным выводом или форматом, но может использоваться для любого типа двухмерной диаграммы. Примерами являются компоненты на основе Swing, файлы SVG и многое другое. Это возможно, потому что TreeLayout отделяет макет дерева от фактического рендеринга.

Чтобы использовать TreeLayout, вам в основном необходимо предоставить экземпляр класса TreeLayout с узлами дерева (включая «дочерние» ссылки) вместе с «размером» каждого узла. Кроме того, вы можете настроить макет, указав такие параметры, как «разрыв между уровнями» и т. Д.

На основании этой информации TreeLayout создает компактный, красивый внешний вид. Компоновка имеет следующие свойства [2]:

  1. Макет отображает иерархическую структуру дерева, то есть y-координата узла задается его уровнем.
  2. Края не пересекаются, а узлы на одном уровне имеют минимальное горизонтальное расстояние.
  3. Рисование поддерева не зависит от его положения в дереве, т. Е. Изоморфные поддеревья отрисовываются одинаково с точностью до перевода.
  4. Порядок дочерних узлов отображается на чертеже.
  5. Алгоритм работает симметрично, т.е. рисунок отражения дерева является отраженным рисунком исходного дерева.

Вот пример макета дерева:

содержание

 

Загрузка и установка

  • Источники : http://code.google.com/p/treelayout/source/browse/
  • JAR-файлы :

    • org.abego.treelayout.core.jar : ядро ​​алгоритма TreeLayout.
    • org.abego.treelayout.netbeans.jar : используйте алгоритм TreeLayout для API визуальной библиотеки NetBeans (GraphLayout, …). (При использовании этого JAR убедитесь, что библиотеки NetBeans ‘org.netbeans.api.visual’, ‘org.openide.util’ и ‘org.openide.util.lookup’ находятся в пути к классам.)

 

NetBeans и abego TreeLayout

API визуальной библиотеки NetBeans уже включает в себя алгоритм для построения деревьев (и графиков в целом). Однако стандартная реализация визуальной библиотеки NetBeans не всегда создает такие компактные макеты, как реализация Treeeayout abego:

Макет с использованием abego TreeLayout Макет с использованием стандартного дерева GraphBayay для NetBeans

Оба снимка экрана взяты из демонстрационного приложения в проекте «org.abego.treelayout.netbeans.demo», также предоставленного в источниках. Демонстрационный проект включает в себя библиотеку «org.abego.treelayout.netbeans» для легкого доступа к алгоритму abego TreeLayout из стандартного визуального кода NetBeans.

Как показывает следующее сравнение, использование abego TreeLayout в визуальном коде NetBeans так же просто, как использование стандартного GraphLayout:

Используйте abego TreeLayout для создания SceneLayout :

AbegoTreeLayoutForNetbeans<N, E> graphLayout = 
        new AbegoTreeLayoutForNetbeans<N, E>(root, 100, 100, 50, 50, true);
SceneLayout sceneLayout = LayoutFactory.createSceneGraphLayout(scene,graphLayout);
...

Используйте NetBeans по умолчанию Tree GraphLayout для создания SceneLayout :

GraphLayout<N, E> graphLayout = 
        GraphLayoutFactory.createTreeGraphLayout(100, 100, 50, 50, true);
GraphLayoutSupport.setTreeGraphLayoutRootNode(graphLayout, root);
SceneLayout sceneLayout = LayoutFactory.createSceneGraphLayout(scene, graphLayout);
...

 

Документация

Для получения подробной документации см. JavaDoc в исходном коде и в этом PDF-документе .

Кроме того, вы также можете найти пример кода полезным. Входит в «демонстрационные» пакеты.

 

Алгоритм выполнения

На основе алгоритма Уокера [1] с усовершенствованиями, предложенными Буххаймом, Юнгером и Лейпертом [2], программное обеспечение строит древовидные схемы за линейное время. Т.е. даже деревья с множеством узлов строятся быстро. Кроме алгоритма Рейнгольда – Тилфорда [3], каждый не ограничивается бинарными деревьями.

В эталонном алгоритме алгоритм может размещать деревья со скоростью ок. 5 микросекунд на узел. (Работает на компьютере с процессором Intel Core 2 Duo 2,4 ГГц).

 

развитие

Вы можете проверить исходный код TreeLayout из репозитория TreeLayout SVN .

Проекты содержат конфигурации для IDE Eclipse и NetBeans, а также сценарии ANT для их создания.

 

Лицензия

abego TreeLayout распространяется по лицензии BSD abego Software . ( Текст лицензии )

 

Ссылки

[1] Уокер JQ II. Алгоритм позиционирования узла для общих деревьев. Программное обеспечение — практика и опыт 1990; 20 (7): 685–705.

[2] Буххайм С., Юнгер М., Лейперт С. Рисование корневых деревьев за линейное время. Программное обеспечение — практика и опыт 2006; 36 (6): 651–665

[3] Reingold EM, Tilford JS. Более аккуратные рисунки деревьев. IEEE транзакции по разработке программного обеспечения 1981; 7 (2): 223–228.

38
Share: