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 |
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 |
Free forum by Nabble | Edit this page |