Получение всех ребер, выходящих из узла в jgrapht

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

Я знаю, что есть метод getAllEdges(sourceVertex, targetVertex), который возвращает все ребра между двумя заданными узлами. Но как я могу получить все ребра, имея только исходный узел без целевого?


java graph jgrapht jgraph
person TheMP    schedule 16.06.2015    source источник
comment
Не вижу прямого API для этого. Что вы можете сделать, так это либо 1. получить все вершины (возможно, используя метод vertexSet()), а затем передать каждую вершину из этого набора как targetVertex для метода getAllEdges() и объединить результаты всех этих вызовов. или 2. получить все ребра, используя метод edgeSet(). Затем для каждого из этих ребер вызовите getEdgeSource(E e), чтобы получить sourceVertext. Затем сравните его с данной вершиной, чтобы увидеть, начинается ли это ребро с данной вершины. Соберите эти ребра, и вы получите желаемый результат.   -  person Balkrishna Rawool    schedule 16.06.2015
comment
Вероятно, это сработает, но насколько это эффективно? У меня есть довольно большой график для анализа.   -  person TheMP    schedule 16.06.2015
comment
Если вас беспокоит производительность, поскольку готового API нет, я бы посоветовал вам взглянуть на исходный код, а затем расширить класс, чтобы создать собственную реализацию, скажем, getAllEdgesStartingFromVertex(V vertex). Это также позволяет вам оптимизировать метод так, как вы хотите.   -  person Balkrishna Rawool    schedule 16.06.2015

Ответы (5)


arrow_upward
4
arrow_downward

Вы можете напрямую использовать Graphs.predecessorListOf и Graphs.successorListOf.

person adarsh003    schedule 30.06.2015

arrow_upward
2
arrow_downward

Вы можете получить доступ к исходящим ребрам узла (вершины) с помощью метода outgoingEdgesOf объекта графа.

Set<MyEdge> edges = myGraph.outgoingEdgesOf(sourceNode);

Кроме того, вы можете использовать incomingEdgesOf для входящих ребер.

Если вы хотите получить доступ ко всем краям узла, используйте

graph.edgesOf(source)
person Memin    schedule 17.05.2020

arrow_upward
1
arrow_downward

Любой объект, реализующий интерфейс Graph<V,E>, должен иметь метод edgesOf(V vertex), по крайней мере, в соответствии с API. Ваш TransportGraph должен уметь это делать.

person milez    schedule 14.07.2015

arrow_upward
0
arrow_downward

Если кому-то интересно, я не нашел прямого способа добиться этого, поэтому я воспользовался предложением Балкришны из комментариев. Моя реализация (стиль Java 8):

   private List<WeightedEdge> getAllEdgesFromNode(TransportGraph graph, MyNode startNode) {
    return graph.unwrap().edgeSet().stream()
            .filter(weightedEdge -> graph.unwrap().getEdgeSource(weightedEdge).equals(startNode))
            .collect(Collectors.toList());
}

Примечание. TransportGraph — это оболочка для графа jgrapht, которую я написал сам. Мой метод unwrap() возвращает SimpleDirectedWeightedGraph,

person TheMP    schedule 19.06.2015

arrow_upward
-2
arrow_downward

Я пытался прокомментировать ответ milez, но по ошибке написал его как ответ. Итак, давайте напишем ответ. Milez предложил использовать библиотеку JGrapht, которую я использовал сам несколько раз, и она отлично работает. В этой библиотеке есть класс RandomWalkIterator, который, я думаю, соответствует требованиям.

person Juan    schedule 31.08.2017
comment
Извините, это должен был быть комментарий к ответу Милеза, и он попал не в то место. Моя ошибка. milez предложил библиотеку JGrapht, в которой есть класс RandomWalkIterator. На мой взгляд, он реализует именно запрошенный функционал. - person Juan; 25.10.2017