Quantcast

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

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

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

Rushang Karia
I find overriding the hashcode() and equals() method to be the most useful. I would be interested in profiling with a poor hash function to see if the difference is still remarkable or not.

However for complex generics like user defined types the quality of the hash would depend on how the user implemented the hash framework and would also force the user to override the methods for correctness. If they did not override the methods they could get incorrect results. We would need to enforce them to override the methods.

I think the hash approach is sufficient for most algorithms and can be accommodated in a minor release but I am not sure if  it is the best approach.

Please pardon the formatting as I typed this over a cellphone 

I'll try to send over a code snippet from long back (before I knew of jgraph)

Rushang




----- Reply message -----
From: "Joris Kinable" <[hidden email]>
To: "[hidden email]" <[hidden email]>
Subject: [jgrapht-users] some potential speed improvements for containsEdge(u, v) and getEdge(u, v)
Date: Tue, Apr 5, 2016 21:33

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

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Aidan Delaney
Dear all,
As far as I recall (and I'm happy to be wrong) overriding hash code for
Edge leads to Bad Things (tm).  JGraphT is a general graph
implementation.  As such, it doesn't assume that you're graph is not a
multigraph.
        In the JGraphT implementation, if we add edge e between vertex
v1 and v2 we -- unsurprisingly -- have an edge between v1 and v2.  If I
create another edge, e', which is between v1 and v2 and identical to e
in all other respects, then my graph has two edges, e and e', between
v1 and v2.  By overriding hashCode, e and e' would be equal edges and
you'd only have one edge between v1 and v2.
        I hope the above helps.  I'll read it again after my first
coffee to see if it's actually intelligible.

--
Dr Aidan Delaney
Principal Lecturer
Computing, Engineering & Maths
University of Brighton

@aidandelaney

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

signature.asc (188 bytes) Download Attachment
Loading...