Re: [jgrapht-users] some potential speed improvements for containsEdge(u, v) and getEdge(u, v)

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Based on all the suggestions in this thread, I've started a first round of
code optimization. See my pull request:
https://github.com/jgrapht/jgrapht/pull/188
Since this really touches the internals of JGraphT, please perform a
thorough code review.

@Ernst. Interesting idea to create an VertexPair object once and then
modify it for various lookups. I haven't tried it yet though.

br,

Joris Kinable

On Sat, Apr 9, 2016 at 2:14 PM, H.N. de Ridder <hnr...@gr...>
wrote:

> On Fri, Apr 08, 2016 at 02:36:37AM -0700, John Sichi wrote:
> > 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...
>
> But iterators typically are used more than once, here the new pair is used
> only for a single hash lookup.
>
> Several years ago I ran into the same performance issue with JgraphT and
> as a
> quick hack created a wrapper class like this (and then forget about it
> until
> this discussion):
>
> public class CacheGraph<V,E> extends ListenableDirectedGraph<V,E>
>         implements GraphListener<V,E> {
>     private DirectedGraph<V,E> graph;   /** The graph we're caching */
>     private HashMap<V,V> nodeCache;
>     private HashMap<Pair,E> edgeCache;
>     private Pair reusablePair;          /** For looking up edges */
>
> The rest of the class is about as you'd expect. Note that Pair, different
> from
> org.jgrapht.util.VertexPair, is modifiable. I used this class to time the
> impact of allocating a new Pair() when performing an edge lookup and in my
> application it adds about 9% to the running time. And this is when there
> is no
> shortage of memory. When there is, the shit can really hit the fan. So I
> suggest using a reusable pair object and not reallocating one for every
> test.
>
> Regards,
>    Ernst
>
> >
> > 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
> > >>>
>
> --
> Information System on Graph Classes and their Inclusions (ISGCI)
> http://www.graphclasses.org
>
>
> ------------------------------------------------------------------------------
> Find and fix application performance issues faster with Applications
> Manager
> Applications Manager provides deep performance insights into multiple
> tiers of
> your business applications. It resolves application problems quickly and
> reduces your MTTR. Get your free trial! http://pubads.g.doubleclick.net/
> gampad/clk?id=1444514301&iu=/ca-pub-7940484522588532
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>