[jgrapht-users] some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

[Joris K. <de...@gm...>]

Dear,

After profiling an algorithm implementation, I was surprised to find out
that the containsEdge(u,v) method actually took up the largest amount of
computation time; in fact, 70% of the runtime was spent on repeatedly
invoking this method, whereas only 30% was spent on the remaining
algorithm. Digging a little deeper into the code revealed that the
containsEdge(u,v) invokes getEdge(u,v) in AbstractBaseGraph.java. In case
of a Directed graph, the getEdge method would iteratively run over all
outgoing edges of vertex u until an edge e was encountered with
edgeTarget(e)==v. This obviously has a pretty bad runtime complexity
O(N^+(u)), where N^+(u) denotes the number of outgoing edges of vertex u in
the graph. I was wondering what would be the best way to improve this. Here
are some options:

Option 1. We could extend the DirectedNeighborIndex<V,E> class. This class
could include a way to quickly look up an edge. Using for example:
*Map<V,Map<V,E> verticesToEdgeMap=....; getEdge(u,v) would then return:
verticesToEdgeMap.get(u).get(v);  Note: for simplicity, I left out some
simple Null checks.*

Option 2. The above option can also be included into the DirectedSpecifics
subclass in AbstractBaseGraph.java Currently, a vertex maintains 2 sets:
outgoingEdges and incomingEdges. These 2 sets are both stored inside a
DirectedEdgeContainer associated with a vertex. We could add another Map
which maps a pair (source/target vertex) to a specific edge. This would
yield a minor increase in terms of memory, but a potential significant
speed up for a number of algorithms.

One last option I could come up with takes advantage of the
Objects.hash(...) function. We could simply create a hash Objects.hash(u,v)
which could map to an edge.

Let me know what you think.

Joris