|
From: John S. <js...@gm...> - 2016-04-08 09:36:44
|
I was thinking the existing DirectedSpecifics and UndirectedSpecifics would become "legacy" implementations (preserving the old behavior). We would add new subclasses, say OptimizedDirectedSpecifics and OptimizedUndirectedSpecifics (better names welcome). The vertexPairToEdgeMap should exist only at the Optimized level (not at the base level). The default implementation of createDirectedSpecifics would instantiate OptimizedDirectedSpecifics. But applications (of which SimpleIdentityDirectedGraphTest is a representative) would be free to override this to instantiate the old DirectedSpecifics (with their own refinements, as in that test). Does that work? Regarding short-lived VertexPairs: long ago I learned to stop worrying and love the Eden approach of the garbage collector. Think about how many iterators are created and forgotten during a typical algorithm execution... On Wed, Apr 6, 2016 at 4:18 PM, Joris Kinable <de...@gm...> wrote: > 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 >> >> > |
