jgrapht-users — JGraphT user list.

[jgrapht-users] Null endVertex for DijkstraShortestPath?

[James D. <dem...@ho...>]

Hello there,
I had a question about the implementation of DijkstraShortestPath. It appears from the code that an endVertex is required. However, I was hoping that I could use Dijkstra's without giving it an end vertex. The idea being that i want to give it a startVertex and then have it return to me the shortest path that traverses all nodes. The idea being that I'd want to find the shortest path from each starting vertex.
Let me know if this is possible with JGraphT. Thanks!
-JamesD 		 	   		  

[jgrapht-users] next release version

[John S. <js...@gm...>]

Hey all,

It's been pointed out to me that the move to JDK 8 is a big one, which may
make take a while for projects weighted down by legacy release constraints
to absorb.

As a result, the next JGraphT release will be 1.0.0 (instead of 0.9.3).

We could have made it 0.10, but JGraphT, although just barely
post-millennial, is not exactly a spring chicken, so we might as well
celebrate its maturity with a bright shiny 1.x designation.

If necessary for dependent projects stuck on older JDK versions,
maintenance releases on the 0.9 series can be branched off for backports,
but there are no plans for that at this time.

I'll make the corresponding changes in the HISTORY/pom files unless I hear
objections.

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

[H.N. de R. <hnr...@gr...>]

I agree with Joris. Implement the current setup and solve a performance 
collapse if and when it causes issues.


-- 
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org



On 10 April 2016 9:07:25 pm Joris Kinable <de...@gm...> wrote:

> I've done some testing to measure the impact of frequent object creation.
> *Algorithm setup:*
> 1. Implementation where VertexPair objects are frequently created and
> immediately discarded afterwards (see
> https://github.com/jgrapht/jgrapht/pull/188).
> 2. Implementation where I use a ModifiableVertexPair as proposed by Ernst.
> In this implementation I created a single ModifiableVertexPair indexPair.
> Each time an edge is queried in the Map<ModifiableVertexPair<V>,
> ArrayUnenforcedSet<E>> touchingVerticesToEdgeMap,
>  indexPair.updatePair(source, target) gets invoked first. This entirely
> avoids the creation of new VertexPairs. To ensure that read operations are
> thread-save, I made the getEdge(u,v) and getAllEdges(u,v) synchronized.
> Here's the implementation:
> https://github.com/jkinable/jgrapht/blob/SpecificsOptimization_experimental/jgrapht-core/src/main/java/org/jgrapht/graph/specifics/FastLookupDirectedSpecifics_experimental.java
> . If you want to try it yourself or see my implementation, download this
> branch:
> https://github.com/jkinable/jgrapht/tree/SpecificsOptimization_experimental
>
> *Experiment setup:*
> java version "1.8.0_77"
> Java(TM) SE Runtime Environment (build 1.8.0_77-b03)
>
> Each experiment is repeated 5 times, with 5 warmup iterations each.
>
> *Experiments:*
> 1. ConstructGraph: Build 100 graphs, each consisting of 1000 vertices and
> 100000 edges
> 2. UseGraph: Build 100 graphs, run 3 different algorithms on each graph,
> randomly destroy part of the graph (triggering containsEdge(u,v) and
> removeEdge(u,v)).
>
> Results:
>
> Benchmark
>                   Mode  Cnt      Score      Error  Units
> ConstructGraph(objectCreation)                  avgt    5  11313.907 ±
>  216.430  ms/op
> UseGraph(objectCreation)                  avgt    5  33234.987 ± 1009.527
>  ms/op
> ConstructGraph(IndexPair)  avgt    5  11230.629 ±  146.290  ms/op
> UseGraph(IndexPair)  avgt    5  32295.133 ± 1208.719  ms/op
>
> Here objectCreation uses a DirectedSpecifics implementation where
> short-lived VertexPairs are created. IndexPair uses a DirectedSpecifics
> implementation where objects are reused.
> I repeated these experiment several times, never was there a clear winner.
>
> Conclusion:
> I was unable to create a scenario where reusing the objects was
> significantly more efficient than recreating them. Quite an interesting
> result if you ask me. Consequently, I would propose to continue with my
> pull request: https://github.com/jgrapht/jgrapht/pull/188
>
>
> br,
>
> Joris Kinable
>
>
> On Sun, Apr 10, 2016 at 7:24 AM, H.N. de Ridder <hnr...@gr...>
> wrote:
>
>> On Sat, Apr 09, 2016 at 08:25:15PM -0700, John Sichi wrote:
>>
>> Yes, that's true. Thread-unsafety is a k.o.-criterium. I tested with 64bit
>> icedtea 2.6.5. I'm short on time right now, but I'll see in a week or so
>> whether I can repeat the tests with java8 and also if I can pinpoint when
>> memory gets tight and what happens then.
>>
>> > Hmmm...the problem with the reusable pair object is that it makes even
>> > reads thread-unsafe (unless it's implemented via a thread-local
>> variable).
>> > I'm not 100% sure, but I think the last time we analyzed it, the graph
>> data
>> > structures themselves were all OK for concurrent reads (though not of
>> > course for concurrent reads+writes).
>> >
>> > It might be good to repeat the benchmarking with the latest JVM.
>> >
>> > On Sat, Apr 9, 2016 at 11:14 AM, 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
>> > >
>>
>> --
>> 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
>>
>

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

[Joris K. <de...@gm...>]

I've done some testing to measure the impact of frequent object creation.
*Algorithm setup:*
1. Implementation where VertexPair objects are frequently created and
immediately discarded afterwards (see
https://github.com/jgrapht/jgrapht/pull/188).
2. Implementation where I use a ModifiableVertexPair as proposed by Ernst.
In this implementation I created a single ModifiableVertexPair indexPair.
Each time an edge is queried in the Map<ModifiableVertexPair<V>,
ArrayUnenforcedSet<E>> touchingVerticesToEdgeMap,
 indexPair.updatePair(source, target) gets invoked first. This entirely
avoids the creation of new VertexPairs. To ensure that read operations are
thread-save, I made the getEdge(u,v) and getAllEdges(u,v) synchronized.
Here's the implementation:
https://github.com/jkinable/jgrapht/blob/SpecificsOptimization_experimental/jgrapht-core/src/main/java/org/jgrapht/graph/specifics/FastLookupDirectedSpecifics_experimental.java
. If you want to try it yourself or see my implementation, download this
branch:
https://github.com/jkinable/jgrapht/tree/SpecificsOptimization_experimental

*Experiment setup:*
java version "1.8.0_77"
Java(TM) SE Runtime Environment (build 1.8.0_77-b03)

Each experiment is repeated 5 times, with 5 warmup iterations each.

*Experiments:*
1. ConstructGraph: Build 100 graphs, each consisting of 1000 vertices and
100000 edges
2. UseGraph: Build 100 graphs, run 3 different algorithms on each graph,
randomly destroy part of the graph (triggering containsEdge(u,v) and
removeEdge(u,v)).

Results:

Benchmark
                  Mode  Cnt      Score      Error  Units
ConstructGraph(objectCreation)                  avgt    5  11313.907 ±
 216.430  ms/op
UseGraph(objectCreation)                  avgt    5  33234.987 ± 1009.527
 ms/op
ConstructGraph(IndexPair)  avgt    5  11230.629 ±  146.290  ms/op
UseGraph(IndexPair)  avgt    5  32295.133 ± 1208.719  ms/op

Here objectCreation uses a DirectedSpecifics implementation where
short-lived VertexPairs are created. IndexPair uses a DirectedSpecifics
implementation where objects are reused.
I repeated these experiment several times, never was there a clear winner.

Conclusion:
I was unable to create a scenario where reusing the objects was
significantly more efficient than recreating them. Quite an interesting
result if you ask me. Consequently, I would propose to continue with my
pull request: https://github.com/jgrapht/jgrapht/pull/188


br,

Joris Kinable


On Sun, Apr 10, 2016 at 7:24 AM, H.N. de Ridder <hnr...@gr...>
wrote:

> On Sat, Apr 09, 2016 at 08:25:15PM -0700, John Sichi wrote:
>
> Yes, that's true. Thread-unsafety is a k.o.-criterium. I tested with 64bit
> icedtea 2.6.5. I'm short on time right now, but I'll see in a week or so
> whether I can repeat the tests with java8 and also if I can pinpoint when
> memory gets tight and what happens then.
>
> > Hmmm...the problem with the reusable pair object is that it makes even
> > reads thread-unsafe (unless it's implemented via a thread-local
> variable).
> > I'm not 100% sure, but I think the last time we analyzed it, the graph
> data
> > structures themselves were all OK for concurrent reads (though not of
> > course for concurrent reads+writes).
> >
> > It might be good to repeat the benchmarking with the latest JVM.
> >
> > On Sat, Apr 9, 2016 at 11:14 AM, 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
> > >
>
> --
> 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
>

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

[H.N. de R. <hnr...@gr...>]

On Sat, Apr 09, 2016 at 08:25:15PM -0700, John Sichi wrote:

Yes, that's true. Thread-unsafety is a k.o.-criterium. I tested with 64bit
icedtea 2.6.5. I'm short on time right now, but I'll see in a week or so
whether I can repeat the tests with java8 and also if I can pinpoint when
memory gets tight and what happens then.

> Hmmm...the problem with the reusable pair object is that it makes even
> reads thread-unsafe (unless it's implemented via a thread-local variable).
> I'm not 100% sure, but I think the last time we analyzed it, the graph data
> structures themselves were all OK for concurrent reads (though not of
> course for concurrent reads+writes).
> 
> It might be good to repeat the benchmarking with the latest JVM.
> 
> On Sat, Apr 9, 2016 at 11:14 AM, 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
> >

-- 
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

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

[John S. <js...@gm...>]

Hmmm...the problem with the reusable pair object is that it makes even
reads thread-unsafe (unless it's implemented via a thread-local variable).
I'm not 100% sure, but I think the last time we analyzed it, the graph data
structures themselves were all OK for concurrent reads (though not of
course for concurrent reads+writes).

It might be good to repeat the benchmarking with the latest JVM.

On Sat, Apr 9, 2016 at 11:14 AM, 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
>

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

[Joris K. <de...@gm...>]

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
>

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

[H.N. de R. <hnr...@gr...>]

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

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

[John S. <js...@gm...>]

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
>>
>>
>

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

[Joris K. <de...@gm...>]

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
>
>

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

[John S. <js...@gm...>]

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
>
>

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

[Rushang K. <rus...@ho...>]

------------------------------------------------------------------------------

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

[Aidan D. <ai...@on...>]

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

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

[Rushang K. <rus...@ho...>]

------------------------------------------------------------------------------

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

[Joris K. <de...@gm...>]

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] JGraphT Version 0.9.2 Released

[John S. <js...@gm...>]

This is an incremental release including all contributions since the 0.9.1
release. This is the last release for which JGraphT will support a JDK 1.7
build; for the next release (0.9.3), we will require JDK 1.8.

You can see the full change list here:

https://github.com/jgrapht/jgrapht/blob/master/HISTORY.md

Re: [jgrapht-users] Weighted graph

[Ícaro C. D. <ic...@gm...>]

In order to show what you want for the edges, create your own subclass of
DefaultWeightedEdge, then override *toString* method.

For large graphs, I suggest you export them in dot format, which is lighter
for plotting.

2016-02-14 22:27 GMT-02:00 Cherie Pun <che...@gm...>:

> Hi all,
>
> I am trying to visualise a weighted graph using jgraphx, however the label
> on the edge is the pair of connected nodes instead of the weight. How do I
> change the string that is displayed on the edge?
>
> Also, my graph has more than 400k edges, I tried to visualise the graph
> but it took a long time and I stopped the program. Is it normal for it to
> take more than an hour and does the library support graphs that is of this
> scale?
>
> Thank you very much for helping.
>
> Kind regards,
> Cherie
>
>
> ------------------------------------------------------------------------------
> Site24x7 APM Insight: Get Deep Visibility into Application Performance
> APM + Mobile APM + RUM: Monitor 3 App instances at just $35/Month
> Monitor end-to-end web transactions and take corrective actions now
> Troubleshoot faster and improve end-user experience. Signup Now!
> http://pubads.g.doubleclick.net/gampad/clk?id=272487151&iu=/4140
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] preparing for 0.9.2 release

[John S. <js...@gm...>]

I've published the latest dev snapshot.  You can test it by using this as
your repository URL:

http://oss.sonatype.org/content/repositories/snapshots

<dependency>
  <groupId>org.jgrapht</groupId>
  <artifactId>jgrapht-core</artifactId>
  <version>0.9.2-SNAPSHOT</version>
</dependency>

Next week I'll work on pushing out the official release.

[jgrapht-users] Weighted graph

[Cherie P. <che...@gm...>]

Hi all,

I am trying to visualise a weighted graph using jgraphx, however the label
on the edge is the pair of connected nodes instead of the weight. How do I
change the string that is displayed on the edge?

Also, my graph has more than 400k edges, I tried to visualise the graph but
it took a long time and I stopped the program. Is it normal for it to take
more than an hour and does the library support graphs that is of this scale?

Thank you very much for helping.

Kind regards,
Cherie

[jgrapht-users] Modelling the London Underground in JgraphT

[Rob K. <rob...@gm...>]

Guys,

I want to model the London Underground Network in JGraphT such that I can
do things like find me 3 stations running westbound on the District line
from a given station.

I've put the stations in a directed graph and I've extended WeightedEdge to
contain a direction eg. Eastbound, Westbound, Northbound etc.and so the
edge's have that direction in.

I was looking at BreadthFirstIterator but do I need to extend that class so
that I can traverse given the station but only in the direction that I want
it to go in?

I'm new to JGraphT so hopefully I've gone in the right direction but any
help would be appreciated!

Thanks

Rob

[jgrapht-users] Gomory Hu implementation

[Mads J. <mj...@in...>]

Hi,

I'm trying to get an implementation of the Gomory-Hu minimum cut tree
running, as rejuvenated by Gusfield. I'm having trouble to get the code
to run. I tried to use the example from the Python Igraph (I've modified
the Python code to iteratively print values of the s-cut and t-cut, and
neighbors. The odd thing about my code is that in the very first S-T cut
computation, it should be 6, but it's yielding 4, but for the second
run, it's correct. I don't understand that first part with the cut.
Thank you.

It's my goal to open a pull request for the code, in a cleaned-up form;
I started writing the code with a TestCase, but as the test-case kept
failing, and no output is printed when running "mvn test".
-- 
Med venlig hilsen / Kind regards,
Mads Jensen

     Saajan Fernandes: I think we forget things if there is nobody to
                       tell them.
     -- The Lunchbox (2013)

Re: [jgrapht-users] minimum cut in a directed graph

[keshete <kes...@gm...>]

Found this thread 2 years after it was originally created... This is
something I also need. I tried the link you posted regarding the C code, but
it isn't available anymore...
Do you by any chance still have some kind of sample code for this? I'm
looking for a quick solution and this seems promising.

Thanks!
Keshet



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/minimum-cut-in-a-directed-graph-tp4024852p4025075.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] About the similarity of the 2 graphs

[Ícaro C. D. <ic...@gm...>]

There are different ways of measuring similarity between graphs. There is
not consensus, after all.
Besides, this is NP-complete, unless your graphs follow some restrictions
which could lead the cost to P, for example.
I suggest you check a few recent articles about graph similarity so you
will know if approximations suffice your needs.


2016-01-24 23:16 GMT-02:00 Viacheslav Kovalevskyi <via...@b0...>:

> Hi there,
>
> I was trying to measure the similarity of the 2 graphs. Graphs are
> non-direct, with weighted edges. Ideally I need the measure the similarity
> of the graphs with the different algorithms, however if I can find
> implementation of at least one of them, it would solve at least part of the
> problem.
>
> At the moment it does not seems from the mail list and the docs that the
> JGraphT supports this functionality (am i wrong?)? At the moment I'm
> implementing one of the algorithms from scratch on my own. But it would be
> awesome if my assumptions are incorrect and the JGraphT is actually
> supports what I need =)
>
> Thank you in advance on any help about the topic.
>
>
> ------------------------------------------------------------------------------
> Site24x7 APM Insight: Get Deep Visibility into Application Performance
> APM + Mobile APM + RUM: Monitor 3 App instances at just $35/Month
> Monitor end-to-end web transactions and take corrective actions now
> Troubleshoot faster and improve end-user experience. Signup Now!
> http://pubads.g.doubleclick.net/gampad/clk?id=267308311&iu=/4140
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] About the similarity of the 2 graphs

[Viacheslav K. <via...@b0...>]

Hi there,

I was trying to measure the similarity of the 2 graphs. Graphs are
non-direct, with weighted edges. Ideally I need the measure the similarity
of the graphs with the different algorithms, however if I can find
implementation of at least one of them, it would solve at least part of the
problem.

At the moment it does not seems from the mail list and the docs that the
JGraphT supports this functionality (am i wrong?)? At the moment I'm
implementing one of the algorithms from scratch on my own. But it would be
awesome if my assumptions are incorrect and the JGraphT is actually
supports what I need =)

Thank you in advance on any help about the topic.

[jgrapht-users] Find all path between two vertex

[Thomas H. <ham...@pr...>]

 

Hi,

I´ve seen, that this kind of question has already been posted,
but I haven´t found a real solution in the archives yet.

So my problem
is: I wonder, if there is a good way to find all possible paths between
two vertexes.

I´m currently working with a DefaultDirectedWeightedGraph
and I can be sure, that I do not have more than 5 different vertexes. So
there won´t be a too big complexity within this graph.
The different
edges between these vertexes are defined dynamically.
So now I would
like to find out all possible path between one source-vertex and a
target-vertex, where both vertex can also be the same (like in the
eulerian cycle).

I tried to work with the „EulerianCircuit", but that
doesn´t work, because I do not have a unidirectional graph. Using the
„shortestPath"-algorithms (such as KShortestPaths) isn´t working for me
as well, because I need ALL paths.

I found this article
(http://www.scielo.gpeari.mctes.pt/scielo.php?pid=S1645-99112009000200004&script=sci_arttext),
dealing with this kind of a problem - but actually the pseudo-code
isn´t really easy to understand for me.
Maybe someone else already
adopted this algorithm to JGraphT or might help me to translate this
into a pseudo-jgrapht-code.

I would be very thankful, if someone can
point me in the right direction, about what to do best in my
case.

Thanks for your help