Getting all edges going out from a node in jgrapht

Question

I am trying to randomly traverse through the graph in jgrapht (until I find some target node). To do it, I need to start at the sourceNode, randomly pick any coming out edge and follow it.

I know there there is a method getAllEdges(sourceVertex, targetVertex) that returns all the edges between two given nodes. But how can I get all edges while having only sourceNode, without the target one?

Swell

Can't see any direct API for doing that. What you can do is either 1. get all the vertices (perhaps using vertexSet() method) and then pass each vertex from this set as targetVertex for the method getAllEdges() and combine the results of all these calls. or 2. get all edges using edgeSet() method. Then for each of these edges call getEdgeSource(E e) to get sourceVertext. Then compare it eith given vertex to see if this edge starts from the given vertex. Collect these edges and you have your desired result. – Tetter

It will probably work, but how efficient is this? I've got quite a big graph to analyze. – Swell

If you are concerned about performance, as there is not out-of-the-box API, I'd suggest you to take a look at the source and then extend the class to create your own implementation of say getAllEdgesStartingFromVertex(V vertex). That also enables you optimize the method the way you want. – Tetter

Answer 1

You can use Graphs.predecessorListOf and Graphs.successorListOf apis directly.

Arise

Answer 2

You can access the outgoing edges of a node(vertex) with outgoingEdgesOf method of a graph object.

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

Also, you can use incomingEdgesOf for the incoming edges.

If you want to access all edges of a node then use

graph.edgesOf(source)

Stafford

Answer 3

Any object that implements the interface Graph<V,E> should have the method edgesOf(V vertex), at least according to the API. Your TransportGraph should be able to do this.

Transalpine

Answer 4

In case anyone wondered, I did not find any direct way to achieve this, so I went with Balkrishna suggestion from comments. My implementation (Java 8 style) is:

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

Note: TransportGraph is a wrapper for jgrapht graph I have written myself. My method unwrap() returns SimpleDirectedWeightedGraph,

Swell

Answer 5

I was trying to comment milez answer, but I mistakenly wrote it as an answer. So, let's write the answer. Milez proposed using JGrapht library, which I have used myself several times and works quite fine. This library has a RandomWalkIterator class which I think meets the requirements.

Almeria

Sorry, this was intended to be a comment to the answer by milez and it went into the wrong place. My mistake. milez proposed JGrapht library, which has a RandomWalkIterator class. In my opinion, it implements exactly the requested functionality. – Almeria