some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
Report Content as Inappropriate

some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

Joris Kinable

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.



jgrapht-users mailing list
[hidden email]