jgrapht-users — JGraphT user list.

[jgrapht-users] Semi eulerian path

[Dries De S. <dri...@gm...>]

Hi,

I've been looking for a better way to use jgrapht to find a semi eulerian
path.

In our current implementation I use the hierholzer cycle algorithm by
connecting the vertices I want to find the path between with a "fake" edge
so that it causes the cycle and then rearrange the path it generated to fix
the order, but I'm doubting if there's no algorithm in the jgrapht
implementation that can do this straight away?

Kind regards,

Dries

[jgrapht-users] Iterating all solutions

[Claude B. <cl...@re...>]

First of all, congrats for the speed and reliability of the algorithms 
in this library.

My question concerns a Kolmogorov weighted perfect matching. In the 
specific problem I'm trying to solve, there can sometimes be a few 
optimal solutions, with the same score, and which only differ one from 
the other by the permutation of some edges (A->D, B->C instead of A->C, 
B->D for instance).

Would it be possible to somehow iterate all those solutions, or at least 
those reachable with a single permutation, either with the existing 
algorithm or by patching it?

Re: [jgrapht-users] remove node from fully connected SimpleGraph while keeping it fully connected

[Siddharth J. <sid...@gm...>]

Hi Gabor,

Fully connected = every node is reachable from over other node in the graph.

HTH.

S.

On Wed, Oct 4, 2023 at 11:31 AM Gábor Szegedi <gab...@gm...>
wrote:

> Hello Siddharth,
>
> Can you please describe it a little bit more?
>
> If you have a Kn complete Graph, and you remove a Vertex (and all the
> edges related to that vertex) you gonna still have a complete graph with
> Kn-1 nodes.
>
> Kind regards,
> Gábor
>
> Siddharth Jain <sid...@gm...> ezt írta (időpont: 2023. okt. 4.,
> Sze, 20:25):
>
>> Hello,
>>
>> I have a SimpleGraph that is fully connected. I need a method that can
>> remove a *given* node (vertex) from the graph with the condition that
>> the graph remains fully connected. In order to do this, the method may
>> create new edge(s) as necessary for the fully connected property to hold
>> true. Does the JGraphT library provide such a method?
>>
>> S.
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>

Re: [jgrapht-users] remove node from fully connected SimpleGraph while keeping it fully connected

[Gábor S. <gab...@gm...>]

Hello Siddharth,

Can you please describe it a little bit more?

If you have a Kn complete Graph, and you remove a Vertex (and all the edges
related to that vertex) you gonna still have a complete graph with Kn-1
nodes.

Kind regards,
Gábor

Siddharth Jain <sid...@gm...> ezt írta (időpont: 2023. okt. 4., Sze,
20:25):

> Hello,
>
> I have a SimpleGraph that is fully connected. I need a method that can
> remove a *given* node (vertex) from the graph with the condition that the
> graph remains fully connected. In order to do this, the method may create
> new edge(s) as necessary for the fully connected property to hold true.
> Does the JGraphT library provide such a method?
>
> S.
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] remove node from fully connected SimpleGraph while keeping it fully connected

[Joris K. <j.k...@gm...>]

Please post your question on https://stackoverflow.com/ with tag jgrapht
That way, more people can find and benefit from the answer.

On Wed, Oct 4, 2023 at 11:25 AM Siddharth Jain <sid...@gm...> wrote:

> Hello,
>
> I have a SimpleGraph that is fully connected. I need a method that can
> remove a *given* node (vertex) from the graph with the condition that the
> graph remains fully connected. In order to do this, the method may create
> new edge(s) as necessary for the fully connected property to hold true.
> Does the JGraphT library provide such a method?
>
> S.
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] remove node from fully connected SimpleGraph while keeping it fully connected

[Siddharth J. <sid...@gm...>]

Hello,

I have a SimpleGraph that is fully connected. I need a method that can
remove a *given* node (vertex) from the graph with the condition that the
graph remains fully connected. In order to do this, the method may create
new edge(s) as necessary for the fully connected property to hold true.
Does the JGraphT library provide such a method?

S.

Re: [jgrapht-users] How to EdmondsKarp using capacity instead of edge weight

[Gábor S. <gab...@gm...>]

Hi Joris,

In JGraphT is it possible to get the minimum weight path between two
vertices?

I'm not sure that the Dijkstra is considering edge weights.

If not, how do I get the lowest weighted path?
Do you have any idea?

Thanks,
Gábor

Joris Kinable <j.k...@gm...> ezt írta (időpont: 2021. szept. 30.,
Cs, 5:15):

> See the response here:
> https://stackoverflow.com/questions/69380229/jgrapht-how-to-use-my-custom-made-edge-implementation-with-edmondskarp-max-flo/69385637#69385637
>
> On Tue, Sep 28, 2021 at 7:36 AM Gábor Szegedi <gab...@gm...>
> wrote:
>
>> Dear Fellow JGraphT Users,
>>
>> I'm writing to you because I found something that I do not understand,
>> and I need your help.
>>
>> So my findings are that the EdmondsKarpMFImpl
>> <https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/flow/EdmondsKarpMFImpl.html>
>> is using the Edge weight as the capacity. But in that case how do you
>> assign an upper bound to the capacity?
>> Or how can I 'ask' the algorithm to use another field (which is
>> implemented in my implementation of the DefaultWeightedEdge) as a capacity
>> instead of the edge weight.
>>
>> I'm really hoping that someone could help me, it would require for my
>> thesis.
>>
>> Cheers and Looking forward to hearing from you,
>> Gabe
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>

[jgrapht-users] JGraphT 1.5.2 released

[Joris K. <j.k...@gm...>]

Hi all,
After 2 quiet years, JGraphT 1.5.2 has been released! A full list of
changes can be found here:
https://github.com/jgrapht/jgrapht/blob/master/HISTORY.md
Different to previous releases, we decided to update all dependencies
pre-release instead of post-release. This choice is motivated by the fact
that our previous release dates back 2 years, and many of our software
dependencies released new updates containing bug fixes and security
enhancements.


Thank you all for your contributions,

Joris Kinable

Re: [jgrapht-users] reverse-cost for UndirectedGraphs

[Mario B. <mar...@gm...>]

Thank you very much John and Joris. Both your replies were very
informative.

Actually yes, what I had in mind was a "mixed graph", but as both of you
have  pointed out, it seems this will be problematic. I will probably just
create a new path by reversing the nodes and assign a reverse_cost as
suggested to simulate one way roads. I work with millions of edges though,
and I am truly hoping that this won't result in a performance hit. Will
test it out.

Again, thank you very much.

Mario.


On Sat, Oct 30, 2021 at 5:09 AM Joris Kinable <j.k...@gm...> wrote:

>
> Hi Mario,
>
> These questions are best asked on stackoverflow as this will allow more
> people to benefit from the answer.
>
> Typically, what you want to do to represent a road network, is to use a
> directed graph. Each arc represents a set of driving lanes that are all in
> the same direction. To represent a one-way street, you would use 1 arc. To
> represent a street which can be driven in two directions, you would use 2
> arcs.
> Here's a simplified definition of a RoadSegment I've used in the past:
>
> public class RoadSegment{
>
>     /* Unique identifier of the road segment */
>     public final String ID;
>     /* Street name */
>     public final String streetName;
>     /* Set of waypoints defining the shape of the segment (for plotting
> and GPS routing) */
>     public final List<WayPoint> wayPoints;
>     /* Type of the road segment, e.g. highway, residential road */
>     public final RoadType roadType;
>     /* Speed limit in ft/sec */
>     public final int speedLimit;
>     /* Length of road segment in feet, rounded to the nearest integer */
>     public final int length;
>     /* Total number of lanes directed from the tail of this road segment,
> to the head of this road segment. */
>     public final int lanes;
>
>     ...
> }
> If you want to calculate the shortest path (in terms of distance), or the
> fastest path (in terms of time), the easiest thing to do is take advantage
> of the AsWeightedGraph class, as it allows you to run Dijkstra (or similar
> algorithms) with different weights.
>
> Now if you really insist, you can actually use jgrapht with mixed graphs,
> which contain both directed arcs and undirected edges. I've done this in
> the past, using the above RoadSegment class:
>
> /**
> * The following graphs are for routing purposes. They contain the city
> topology.
> * -undirectedRoutingGraph: graph containing all residential streets
> * -directedRoutingGraph: graph containing all the directed arcs
> (one-directional lanes, including one-directional streets)
> * -unionRoutingGraph: a union of the previous 2 graphs
> * **/
> public final Multigraph<RoutingNode, RoadSegment> undirectedRoutingGraph;
> public final DirectedMultigraph<RoutingNode, RoadSegment>
> directedRoutingGraph;
> public final MixedGraphUnion<RoutingNode, RoadSegment> unionRoutingGraph;
>
> Various graph algorithms work quite well on the above graph. Some need
> some tweaking. Either way, it's best if you can avoid using mixed graphs.
>
> Joris Kinable
>
>
> On Fri, Oct 29, 2021 at 4:55 AM John Sichi <js...@gm...> wrote:
>
>> Hi Mario,
>>
>> I think you are describing a "mixed graph", which we allow you to
>> construct via the union of an undirected and directed graph; but most of
>> our algorithms don't know what to do with such a beast, so it's not a
>> terribly useful concept yet.
>>
>> The problematic workaround is a directed graph with opposing edge pairs
>> simulating undirected edges.
>>
>> I don't believe there's currently anything in the way of algorithms being
>> improved to support mixed graphs; this would be a great GSoC project if we
>> are able to participate in that again in the future.
>>
>> There's one open bug for the current inability to directly instantiate a
>> mixed graph:
>>
>> https://github.com/jgrapht/jgrapht/issues/1039
>>
>> This also requires quite a bit of work under the hood.
>>
>>
>> On Tue, Oct 26, 2021 at 1:35 PM Mario Basa <mar...@gm...> wrote:
>>
>>> Is it possible to assign a reverse-cost along with the usual edge cost
>>> in  UndirectedGraphs? This is to simulate one-way passages in a road
>>> network.
>>>
>>> Thanks a lot.
>>>
>>> Mario.
>>>
>>> _______________________________________________
>>> 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] reverse-cost for UndirectedGraphs

[Joris K. <j.k...@gm...>]

Hi Mario,

These questions are best asked on stackoverflow as this will allow more
people to benefit from the answer.

Typically, what you want to do to represent a road network, is to use a
directed graph. Each arc represents a set of driving lanes that are all in
the same direction. To represent a one-way street, you would use 1 arc. To
represent a street which can be driven in two directions, you would use 2
arcs.
Here's a simplified definition of a RoadSegment I've used in the past:

public class RoadSegment{

    /* Unique identifier of the road segment */
    public final String ID;
    /* Street name */
    public final String streetName;
    /* Set of waypoints defining the shape of the segment (for plotting and
GPS routing) */
    public final List<WayPoint> wayPoints;
    /* Type of the road segment, e.g. highway, residential road */
    public final RoadType roadType;
    /* Speed limit in ft/sec */
    public final int speedLimit;
    /* Length of road segment in feet, rounded to the nearest integer */
    public final int length;
    /* Total number of lanes directed from the tail of this road segment,
to the head of this road segment. */
    public final int lanes;

    ...
}
If you want to calculate the shortest path (in terms of distance), or the
fastest path (in terms of time), the easiest thing to do is take advantage
of the AsWeightedGraph class, as it allows you to run Dijkstra (or similar
algorithms) with different weights.

Now if you really insist, you can actually use jgrapht with mixed graphs,
which contain both directed arcs and undirected edges. I've done this in
the past, using the above RoadSegment class:

/**
* The following graphs are for routing purposes. They contain the city
topology.
* -undirectedRoutingGraph: graph containing all residential streets
* -directedRoutingGraph: graph containing all the directed arcs
(one-directional lanes, including one-directional streets)
* -unionRoutingGraph: a union of the previous 2 graphs
* **/
public final Multigraph<RoutingNode, RoadSegment> undirectedRoutingGraph;
public final DirectedMultigraph<RoutingNode, RoadSegment>
directedRoutingGraph;
public final MixedGraphUnion<RoutingNode, RoadSegment> unionRoutingGraph;

Various graph algorithms work quite well on the above graph. Some need some
tweaking. Either way, it's best if you can avoid using mixed graphs.

Joris Kinable


On Fri, Oct 29, 2021 at 4:55 AM John Sichi <js...@gm...> wrote:

> Hi Mario,
>
> I think you are describing a "mixed graph", which we allow you to
> construct via the union of an undirected and directed graph; but most of
> our algorithms don't know what to do with such a beast, so it's not a
> terribly useful concept yet.
>
> The problematic workaround is a directed graph with opposing edge pairs
> simulating undirected edges.
>
> I don't believe there's currently anything in the way of algorithms being
> improved to support mixed graphs; this would be a great GSoC project if we
> are able to participate in that again in the future.
>
> There's one open bug for the current inability to directly instantiate a
> mixed graph:
>
> https://github.com/jgrapht/jgrapht/issues/1039
>
> This also requires quite a bit of work under the hood.
>
>
> On Tue, Oct 26, 2021 at 1:35 PM Mario Basa <mar...@gm...> wrote:
>
>> Is it possible to assign a reverse-cost along with the usual edge cost in
>>  UndirectedGraphs? This is to simulate one-way passages in a road network.
>>
>> Thanks a lot.
>>
>> Mario.
>>
>> _______________________________________________
>> 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] reverse-cost for UndirectedGraphs

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

Hi Mario,

I think you are describing a "mixed graph", which we allow you to construct
via the union of an undirected and directed graph; but most of our
algorithms don't know what to do with such a beast, so it's not a terribly
useful concept yet.

The problematic workaround is a directed graph with opposing edge pairs
simulating undirected edges.

I don't believe there's currently anything in the way of algorithms being
improved to support mixed graphs; this would be a great GSoC project if we
are able to participate in that again in the future.

There's one open bug for the current inability to directly instantiate a
mixed graph:

https://github.com/jgrapht/jgrapht/issues/1039

This also requires quite a bit of work under the hood.


On Tue, Oct 26, 2021 at 1:35 PM Mario Basa <mar...@gm...> wrote:

> Is it possible to assign a reverse-cost along with the usual edge cost in
>  UndirectedGraphs? This is to simulate one-way passages in a road network.
>
> Thanks a lot.
>
> Mario.
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] reverse-cost for UndirectedGraphs

[Mario B. <mar...@gm...>]

Is it possible to assign a reverse-cost along with the usual edge cost in
 UndirectedGraphs? This is to simulate one-way passages in a road network.

Thanks a lot.

Mario.

Re: [jgrapht-users] How to EdmondsKarp using capacity instead of edge weight

[Joris K. <j.k...@gm...>]

See the response here:
https://stackoverflow.com/questions/69380229/jgrapht-how-to-use-my-custom-made-edge-implementation-with-edmondskarp-max-flo/69385637#69385637

On Tue, Sep 28, 2021 at 7:36 AM Gábor Szegedi <gab...@gm...>
wrote:

> Dear Fellow JGraphT Users,
>
> I'm writing to you because I found something that I do not understand, and
> I need your help.
>
> So my findings are that the EdmondsKarpMFImpl
> <https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/flow/EdmondsKarpMFImpl.html>
> is using the Edge weight as the capacity. But in that case how do you
> assign an upper bound to the capacity?
> Or how can I 'ask' the algorithm to use another field (which is
> implemented in my implementation of the DefaultWeightedEdge) as a capacity
> instead of the edge weight.
>
> I'm really hoping that someone could help me, it would require for my
> thesis.
>
> Cheers and Looking forward to hearing from you,
> Gabe
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] How to EdmondsKarp using capacity instead of edge weight

[Joris K. <j.k...@gm...>]

Hi Gabe,
The best place to get answers to these kinds of questions is on
https://stackoverflow.com/ (use the tag *jgrapht*): yo u have a bigger
audience and more people will be able to answer, or benefit themselves from
the answers.

Short answers:

Option a: the get and set edgeWeight methods of a weighted graph simply
store an edge 'weight' as a double. You can freely interpret this weight.
If you want to interpret this weight as 'capacity' that's fine. If you want
to interpret it as 'cost' that's also fine. So in order to set the
capacities of the individual edges, all you have to do is invoke
setEdgeWeight on those edges with the desired capacity.

Option b: you could wrap your graph in a AsWeightedGraph class to define
custom weights, or to delegate the getEdgeWeight method to a 'function'.
Using AsWeightedGraph is particularly useful if your graph is essentially
unweighted and you want to make it weighted temporarily, or if you have a
graph where every edge has two sets of weights (e.g. cost and capacity).

Option c: create a graph with a custom edge implementation which extends
the DefaultWeightedEdge class (e.g. MyCustomeEdge extends
DefaultWeightedEdge). Then override the getEdgeWeight() method to return
your custom 'capacity' field instead.

These are just sketches of 3 simple solutions. If you could provide a short
code snippet of what you try to accomplish that would be easier.
Nevertheless, please put your question on stackoverflow.

br,

Joris Kinable

On Tue, Sep 28, 2021 at 7:36 AM Gábor Szegedi <gab...@gm...>
wrote:

> Dear Fellow JGraphT Users,
>
> I'm writing to you because I found something that I do not understand, and
> I need your help.
>
> So my findings are that the EdmondsKarpMFImpl
> <https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/flow/EdmondsKarpMFImpl.html>
> is using the Edge weight as the capacity. But in that case how do you
> assign an upper bound to the capacity?
> Or how can I 'ask' the algorithm to use another field (which is
> implemented in my implementation of the DefaultWeightedEdge) as a capacity
> instead of the edge weight.
>
> I'm really hoping that someone could help me, it would require for my
> thesis.
>
> Cheers and Looking forward to hearing from you,
> Gabe
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] How to EdmondsKarp using capacity instead of edge weight

[Gábor S. <gab...@gm...>]

Dear Fellow JGraphT Users,

I'm writing to you because I found something that I do not understand, and
I need your help.

So my findings are that the EdmondsKarpMFImpl
<https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/flow/EdmondsKarpMFImpl.html>
is using the Edge weight as the capacity. But in that case how do you
assign an upper bound to the capacity?
Or how can I 'ask' the algorithm to use another field (which is implemented
in my implementation of the DefaultWeightedEdge) as a capacity instead of
the edge weight.

I'm really hoping that someone could help me, it would require for my
thesis.

Cheers and Looking forward to hearing from you,
Gabe

Re: [jgrapht-users] A reaction to JGraphT

[Joris K. <j.k...@gm...>]

This is really cool, thanks for sharing! Those graphics are really pretty!
I typically only see graph coloring problems from the mathematical side;
the graphical side is often overlooked. Thanks again for reaching out and
let is us know if you run into any issues or discover any use cases which
are currently not supported by our graph library.

On Wed, Aug 18, 2021 at 11:27 PM John Sichi <js...@gm...> wrote:

> Thank you very much Gary, from all of who work on JGraphT, it's always
> great to hear positive feedback :)
>
> The graph coloring images are lovely!
>
> On Thu, Aug 19, 2021 at 8:37 AM Gary Lucas <gwl...@gm...> wrote:
>
>> Dear JGraphT developer team,
>>
>> A guy who uses my Delaunay Triangulation API just pointed me in the
>> direction of the JGraphT project.  I’ve looked at your website and  I am
>> deeply impressed with your work.  My compliments to all of you on a
>> well-made software library.
>>
>>
>>
>> Gary
>>
>>
>>
>> P.S. You can see some cool images that were made using JGraphT at micycle1's
>> JGraphT post
>> <https://github.com/gwlucastrig/Tinfour/issues/58#issuecomment-901337687>
>> _______________________________________________
>> 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] A reaction to JGraphT

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

Thank you very much Gary, from all of who work on JGraphT, it's always
great to hear positive feedback :)

The graph coloring images are lovely!

On Thu, Aug 19, 2021 at 8:37 AM Gary Lucas <gwl...@gm...> wrote:

> Dear JGraphT developer team,
>
> A guy who uses my Delaunay Triangulation API just pointed me in the
> direction of the JGraphT project.  I’ve looked at your website and  I am
> deeply impressed with your work.  My compliments to all of you on a
> well-made software library.
>
>
>
> Gary
>
>
>
> P.S. You can see some cool images that were made using JGraphT at micycle1's
> JGraphT post
> <https://github.com/gwlucastrig/Tinfour/issues/58#issuecomment-901337687>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] A reaction to JGraphT

[Gary L. <gwl...@gm...>]

Dear JGraphT developer team,

A guy who uses my Delaunay Triangulation API just pointed me in the
direction of the JGraphT project.  I’ve looked at your website and  I am
deeply impressed with your work.  My compliments to all of you on a
well-made software library.



Gary



P.S. You can see some cool images that were made using JGraphT at micycle1's
JGraphT post
<https://github.com/gwlucastrig/Tinfour/issues/58#issuecomment-901337687>

[jgrapht-users] JGraphT version 1.5.1 released

[Joris K. <j.k...@gm...>]

Dear,
JGraphT version 1.5.1 has been released and is accessible through our usual
channels: github, maven and Sourceforge. Although the new version number
indicates a minor release, the number of contributions made by the
community are once again substantial! One of the cool newly added features
is the WebGraph adapter. This adapter allows you to invoke JGraphT's
arsenal of algorithms on some truly massive web graphs! More information on
the WebGraph initiative can be found here <https://webgraph.di.unimi.it/>.
As always, the full release notes can be found here
<https://github.com/jgrapht/jgrapht/blob/master/HISTORY.md>.

br,

Joris Kinable

[jgrapht-users] upcoming jgrapht 1.5.1 release

[Joris K. <j.k...@gm...>]

Hi all,
It's that time of the year again: spring! Which means it's time to release
the next version of jgrapht (1.5.1). If you have any last minute changes,
open reviews, stuff you really want to squeeze into the next release: this
is the moment! Submit/finish those PRs, or push your peers to finish theirs
:). All contributions must be merged by Thursday March 18.

Joris Kinable

Re: [jgrapht-users] TransitNodeRoutingShortestPath

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

Thanks, I've asked the author of the algorithm to take a look!

On Sun, Feb 14, 2021 at 11:19 PM Mario Basa <mar...@gm...> wrote:

> Will a CSV file of the graph that contains the ID,SOURCE,TARGET,COST be
> usable?
>
> Thanks.
>
> Mario.
>
>
> On Sun, Feb 14, 2021 at 5:26 PM John Sichi <js...@gm...> wrote:
>
>> Could you create an issue in github?  But before someone can look into
>> it, it'll be necessary to have access to the data (or better, a small
>> subset which reproduces the issue).  If you can't provide the data, then
>> the second best would be to provide output from a CPU profiler showing
>> where the time is being spent.
>>
>> On Fri, Feb 12, 2021 at 12:56 AM Mario Basa <mar...@gm...> wrote:
>>
>>> Greetings,
>>>
>>> I have been trying to use the TransitNodeRoutingShortestPath on a graph
>>> that contains the OSM road network of Switzerland (474,687 edges) since
>>> the documentation says that this algorithm is most suited for large
>>> networks.
>>>
>>> For some reason though, everytime pre-computation is performed, the CPU
>>> usage jumps to 350% continuously and I had to stop the process after 3
>>> hours of processing since obviously there was something wrong. It took only
>>> around 3 minutes to do a pre-computation using the ContractionHierarchyBidirectionalDijkstra
>>> algorithm using the very same graph.
>>>
>>> My code is:
>>>
>>> *private* *static* TransitNodeRoutingShortestPath<Integer,
>>>
>>>         LabeledWeightedEdge> *tnrsp* = *null*;
>>>
>>>
>>> ThreadPoolExecutor executor =
>>>
>>>                         (ThreadPoolExecutor) Executors.
>>> *newFixedThreadPool*(3);
>>>
>>>
>>>
>>>                 *tnrsp* = *new* TransitNodeRoutingShortestPath<Integer,
>>>
>>>                     LabeledWeightedEdge>(*defaultGraph*,executor);
>>>
>>>
>>>
>>>                 *tnrsp*.performPrecomputation();
>>>
>>>
>>>
>>> I tried increasing the ThreadPool but I got the same result (high CPU
>>> usage and un-ending processing).
>>>
>>>
>>> Is there anything I am doing wrong? I'd really appreciate it if someone
>>> can point out how to properly use this algorithm.
>>>
>>>
>>> Thanks.
>>>
>>>
>>>
>>> Mario
>>>
>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>

Re: [jgrapht-users] TransitNodeRoutingShortestPath

[Mario B. <mar...@gm...>]

Will a CSV file of the graph that contains the ID,SOURCE,TARGET,COST be
usable?

Thanks.

Mario.


On Sun, Feb 14, 2021 at 5:26 PM John Sichi <js...@gm...> wrote:

> Could you create an issue in github?  But before someone can look into it,
> it'll be necessary to have access to the data (or better, a small subset
> which reproduces the issue).  If you can't provide the data, then the
> second best would be to provide output from a CPU profiler showing where
> the time is being spent.
>
> On Fri, Feb 12, 2021 at 12:56 AM Mario Basa <mar...@gm...> wrote:
>
>> Greetings,
>>
>> I have been trying to use the TransitNodeRoutingShortestPath on a graph
>> that contains the OSM road network of Switzerland (474,687 edges) since
>> the documentation says that this algorithm is most suited for large
>> networks.
>>
>> For some reason though, everytime pre-computation is performed, the CPU
>> usage jumps to 350% continuously and I had to stop the process after 3
>> hours of processing since obviously there was something wrong. It took only
>> around 3 minutes to do a pre-computation using the ContractionHierarchyBidirectionalDijkstra
>> algorithm using the very same graph.
>>
>> My code is:
>>
>> *private* *static* TransitNodeRoutingShortestPath<Integer,
>>
>>         LabeledWeightedEdge> *tnrsp* = *null*;
>>
>>
>> ThreadPoolExecutor executor =
>>
>>                         (ThreadPoolExecutor) Executors.
>> *newFixedThreadPool*(3);
>>
>>
>>
>>                 *tnrsp* = *new* TransitNodeRoutingShortestPath<Integer,
>>
>>                     LabeledWeightedEdge>(*defaultGraph*,executor);
>>
>>
>>
>>                 *tnrsp*.performPrecomputation();
>>
>>
>>
>> I tried increasing the ThreadPool but I got the same result (high CPU
>> usage and un-ending processing).
>>
>>
>> Is there anything I am doing wrong? I'd really appreciate it if someone
>> can point out how to properly use this algorithm.
>>
>>
>> Thanks.
>>
>>
>>
>> Mario
>>
>>
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>

Re: [jgrapht-users] TransitNodeRoutingShortestPath

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

Could you create an issue in github?  But before someone can look into it,
it'll be necessary to have access to the data (or better, a small subset
which reproduces the issue).  If you can't provide the data, then the
second best would be to provide output from a CPU profiler showing where
the time is being spent.

On Fri, Feb 12, 2021 at 12:56 AM Mario Basa <mar...@gm...> wrote:

> Greetings,
>
> I have been trying to use the TransitNodeRoutingShortestPath on a graph
> that contains the OSM road network of Switzerland (474,687 edges) since
> the documentation says that this algorithm is most suited for large
> networks.
>
> For some reason though, everytime pre-computation is performed, the CPU
> usage jumps to 350% continuously and I had to stop the process after 3
> hours of processing since obviously there was something wrong. It took only
> around 3 minutes to do a pre-computation using the ContractionHierarchyBidirectionalDijkstra
> algorithm using the very same graph.
>
> My code is:
>
> *private* *static* TransitNodeRoutingShortestPath<Integer,
>
>         LabeledWeightedEdge> *tnrsp* = *null*;
>
>
> ThreadPoolExecutor executor =
>
>                         (ThreadPoolExecutor) Executors.
> *newFixedThreadPool*(3);
>
>
>
>                 *tnrsp* = *new* TransitNodeRoutingShortestPath<Integer,
>
>                     LabeledWeightedEdge>(*defaultGraph*,executor);
>
>
>
>                 *tnrsp*.performPrecomputation();
>
>
>
> I tried increasing the ThreadPool but I got the same result (high CPU
> usage and un-ending processing).
>
>
> Is there anything I am doing wrong? I'd really appreciate it if someone
> can point out how to properly use this algorithm.
>
>
> Thanks.
>
>
>
> Mario
>
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] TransitNodeRoutingShortestPath

[Mario B. <mar...@gm...>]

Greetings,

I have been trying to use the TransitNodeRoutingShortestPath on a graph
that contains the OSM road network of Switzerland (474,687 edges) since the
documentation says that this algorithm is most suited for large networks.

For some reason though, everytime pre-computation is performed, the CPU
usage jumps to 350% continuously and I had to stop the process after 3
hours of processing since obviously there was something wrong. It took only
around 3 minutes to do a pre-computation using the
ContractionHierarchyBidirectionalDijkstra
algorithm using the very same graph.

My code is:

*private* *static* TransitNodeRoutingShortestPath<Integer,

        LabeledWeightedEdge> *tnrsp* = *null*;


ThreadPoolExecutor executor =

                        (ThreadPoolExecutor) Executors.*newFixedThreadPool*
(3);



                *tnrsp* = *new* TransitNodeRoutingShortestPath<Integer,

                    LabeledWeightedEdge>(*defaultGraph*,executor);



                *tnrsp*.performPrecomputation();



I tried increasing the ThreadPool but I got the same result (high CPU usage
and un-ending processing).


Is there anything I am doing wrong? I'd really appreciate it if someone can
point out how to properly use this algorithm.


Thanks.



Mario

[jgrapht-users] code of conduct

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

In line with contemporary best practices for inclusive and respectful open
source collaboration, we've added a code of conduct for the JGraphT
community:

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

The language is derived from the Contributor Covenant, which is a common
template for growing a welcoming community.  If you'd like to suggest any
specific improvements to the language, please feel free to open an issue in
github on this topic.

As you interact with others in our community, we appreciate your efforts in
remaining mindful of these guidelines.