Разделить дерево в форсете с помощью jgrapht

У меня есть дерево, представленное библиотекой jgrapht, есть различные типы узлов, которые мне нужно вырезать из любого поддерева, начиная с определенного типа узла.

пример графика

Как вы можете видеть в этом примере, это дерево представляет собой исходный код класса Java. Мне нужно создать несколько объектов jgrapht, разделив основное дерево, начиная с каждого типа узла «Entry». Всего у меня должно получиться 7 деревьев из этого большого. Я использую структуру DirectedPseudograph.


java tree jgrapht
person Philip    schedule 10.09.2019    source источник
comment
Я не совсем уверен, что вы имеете в виду, говоря, что мне нужно вырезать любое поддерево, начиная с определенного типа узла.   -  person Joris Kinable    schedule 11.09.2019

Ответы (1)


arrow_upward
1
arrow_downward

Хотя я не на 100% понимаю, чего вы хотите, похоже, существуют различные подходы к решению.

  1. Начиная с каждого исходящего соседа корневого узла, вы можете запустить поиск в глубину и записать возвращенные узлы. Узлы, достижимые алгоритмом DFS, принадлежат одному и тому же поддереву. Для этого вы можете использовать DepthFirstIterator
  2. Вы можете создать подграф без корневого узла, например, используя AsSubgraph. Затем вы можете вызвать ConnectivityInspector в результирующем индуцированном подграфе. Поскольку каждое поддерево является несвязным компонентом графа, инспектор связности сможет найти каждый из этих компонентов.

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

person Joris Kinable    schedule 11.09.2019
comment
Благодарю вас! Я уже пробовал решение DFS, попробую и второе. Какое решение лучше по сложности, по вашему мнению? P.S. Да, мне нужен псевдограф, потому что он представляет собой исходный код Java. - person Philip; 12.09.2019
comment
Хотя это и незначительно, я предполагаю, что подход DFS является самым быстрым. Однако трудно ответить, так как я точно не знаю, чего вы хотите достичь. Второй подход концептуально достаточно чист и может быть реализован в нескольких строках кода. В конечном счете, второй подход использует те же итераторы, что и подход DFS. Есть ли причина, по которой вас не удовлетворило решение DFS? - person Joris Kinable; 12.09.2019