|
From: Joris K. <de...@gm...> - 2016-04-06 23:18:49
|
John, If I understand you correct, you would propose to do the following: To the Specifics class, you would add: Map<VertexPair<V,V>,Set<E>> vertexPairToEdgeMap=....; Then in DirectedSpecifics.addEdgeToTouchingVertices(E e) you would *add*: VertexPair<V,V> pair=new VertexPair<>(source, target); if(!vertexPairToEdgeMap.containsKey(pair)) vertexPairToEdgeMap.put(pair, new LinkedHashSet<>()); vertexPairToEdgeMap.get(pair).put(e); And then the current DirectedSpecifics.getEdge(V source, V target) would be *replaced* by: VertexPair<V,V> pair=new VertexPair<>(source, target); if(!vertexPairToEdgeMap.containsKey(pair) || vertexPairToEdgeMap.get(pair).isEmpty()) return null; else return vertexPairToEdgeMap.get(pair).iterator().next(); This would be possible, but then the SimpleIdentityDirectedGraphTest would fail. (In this test, the Vertex objects are changed *after* they are created and added to graph, so an IdentityHashMap is required, see the test for details). I'm not sure how to resolve this. An application can indeed override createDirectedSpecifics, but both Specifics and DirectedSpecifics are resp. private and protected, so you cannot provide a custom DirectedSpecifics implementation which avoid this issue. Also, would the frequent construction of short-lived VertexPair objects not be an issue, i.e. a new VertexPair would be created each time getEdge(V source, V target) is invoked. Joris On Wed, Apr 6, 2016 at 5:25 PM, John Sichi <js...@gm...> wrote: > Per the last option mentioned by Joris, I don't think any equals/hashCode > override is required for any object. > > My preference is a hybrid of his second and third options. > > We would add an additional graph-level map inside of Specifics (not > vertex-level inside of EdgeContainer), where the key is VertexPair, and the > value is Edge (or Set<Edge> for multigraphs). When adding an edge, we add > a corresponding entry. When removing an edge, we remove the entry (or > remove the edge from the set for multigraphs, deleting the entry once the > set is empty). This allows us to optimize both containsEdge and getEdge > (which is slightly different depending on directed vs undirected). > > The default implementation would be this new indexing. If an application > wants to revert to the old approach to save memory, this would be possible > by overriding the createDirectedSpecifics and createUndirectedSpecifics > methods. > > > On Wed, Apr 6, 2016 at 2:01 PM, Rushang Karia <rus...@ho...> > wrote: > >> >> Wouldn't this be solved by checking for references as well in addition to >> the equals()? >> >> ----- Reply message ----- >> From: "Aidan Delaney" <ai...@on...> >> To: "jgr...@li..." < >> jgr...@li...> >> Subject: [jgrapht-users] some potential speed improvements for >> containsEdge(u, v) and getEdge(u, v) >> Date: Wed, Apr 6, 2016 01:33 >> >> >> 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 >> jgr...@li... >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users >> >> > > > ------------------------------------------------------------------------------ > > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > > |
