K самых дальних точек от вершины в графе edu.uci.ics.jung

Question

Я хочу найти K самых дальних точек от данной вершины в юнговой реализации ориентированного графа.

Я предполагаю, что BFSDistanceLabeler делает свою работу. Однако он не предоставляет API для возврата K самых дальних точек, поэтому мне придется делать это вручную, обходя все вершины графа и вызывая метод getDistance. Или есть лучший способ?

Но есть большая проблема для меня. Несмотря на то, что график направлен, я хочу рассматривать его как неориентированный для дистанционной маркировки. Можно ли как-то быстро переключиться с ориентированного графа на его неориентированную версию?

Почему я должен рассматривать граф как ненаправленный?

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

При переходе от шага A к шагу B я могу удалить весь предыдущий график и создать новый. Тем не менее, это будет очень много времени. Поскольку я знаю, что моя новая интересная вершина близка к предыдущей, большую часть графа можно использовать повторно.

И именно поэтому мне нужно удалить K самых дальних вершин для новой главной вершины и заменить их новыми вершинами из окружения этой вершины.

Давайте посмотрим на нижнюю картинку с графиком и предположим, что вершина 1 является нашей интересующей вершиной. Так как граф направлен, вершина номер 6 является самой дальней. Однако если бы граф рассматривался как ненаправленный, то вершина номер 4 была бы самой дальней, и это то, что мне нужно.

Answer 1

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

Вы можете получить самые дальние вершины более эффективно, позвонив getVerticesInOrderVisited()и затем обход списка в обратном порядке, начиная с "хвоста": этот список должен быть заполнен в порядке возрастания расстояния от корня (задано), поэтому просто выбирайте вершины из списка, пока расстояние для каждого не начнет уменьшаться.

(Примечание: это не подберет вершины, которые могут быть полностью отсоединены от корневой вершины, которую вы можете считать "самой дальней"); getUnvisitedVertices() сделаю это.)

Чтобы ответить на ваш второй вопрос *: по сути, вы хотите обработать направленные края как ненаправленные. JUNG позволяет вам сделать это; Вместо того, чтобы использовать getSuccessors()/getPredecessors(), ты можешь позвонить getNeighbors(), например.

Как вы поняли, BFSDistanceLabeler не делает этого; он хочет уважать направление края, если он существует, поэтому он использует getSuccessors(), Итак, вот несколько вариантов:

1. использование jung.algorithms.transformation.DirectionTransformer.toUndirected(), Это очень просто, но включает в себя создание множества новых (неориентированных) ребер

2. Создать подкласс BFSDistanceLabeler что переопределяет labelDistances()и заменяет getSuccessors() с getNeighbors(), Это довольно легко, если не очень элегантно.

3. Создать GraphDecorator подкласс, который переопределяет getSuccessors() звонить getNeighbors() на своем графе делегатов. Затем создайте экземпляр вашего подкласса, где ваш исходный граф является делегатом. Это самое элегантное и общее решение. (И в какой-то момент нам может быть полезно предоставить утилиты, которые делают это для вас; пожалуйста, не стесняйтесь подавать проблему на странице JUNG GitHub: https://github.com/jrtom/jung/issues)

Надеюсь это поможет.

* Для дальнейшего использования, пожалуйста, разделите несвязанные вопросы на отдельные вопросы Stackru; это делает их легче ответить и найти.