|
From: John S. <js...@gm...> - 2016-04-06 21:25:54
|
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 > > |
