jgrapht-users — JGraphT user list.

Re: [jgrapht-users] JGraphT matching optimizations?

[d-michail <dim...@gm...>]

Hi, 

some matching algorithms in bipartite graphs perform computation for every
vertex in the left partition. Thus, what you are observing is reasonable.
Swapping the two partitions is a common optimization trick. Feel free to
submit a pull-request if you observe a significant performance gain.

Best, 
Dimitrios



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/JGraphT-matching-optimizations-tp4025147p4025148.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] JGraphT matching optimizations?

[Ben H. <ben...@gm...>]

Hello there,

I just found some interesting performance characteristics of the matching
algorithms.  The tests are not complete, put it appears that the
implementations (possibly the algorithms themselves?) are sensitive to
which partition is passed first.  I think pretty good performance gains can
be had by passing the smallest partition first, and this check could be
incorporated into the algorithms (constructors), so you'd get the advantage
regardless of which order you pass the partitions.

I can supply my test code, and/or the timing data if you like.  I thought I
would first ask, to see if this is known already, and expected.

Thanks,
-Ben

Re: [jgrapht-users] Running demos

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

Hi,

 

I am really sorry to spam you but I just want to say it worked after I cleared my dependency cache. Thanks for your time!

 

Kind regards,
Cherie

 

From: Cherie Pun <che...@gm...>
Date: Friday, 31 March 2017 at 10:11
To: <jgr...@li...>
Subject: Running demos

 

Hi,

 

Sorry for this stupid question. I have cloned the repository from Github (checked out to the 1.0.1 version) and I would like to run the demo.

I tried running it in intellij and it’s giving me error: “package org.jgrapht.ext.GmlParser does not exist”

When I run “java –jar jgraph-demo-1.0.1jar” in the demo folder, it gave me the following error.

“Error: A JNI error has occurred, please check your installation and try again

Exception in thread "main" java.lang.NoClassDefFoundError: org/jgrapht/Graph

                at java.lang.Class.getDeclaredMethods0(Native Method)

                at java.lang.Class.privateGetDeclaredMethods(Class.java:2701)

                at java.lang.Class.privateGetMethodRecursive(Class.java:3048)

                at java.lang.Class.getMethod0(Class.java:3018)

                at java.lang.Class.getMethod(Class.java:1784)

                at sun.launcher.LauncherHelper.validateMainClass(LauncherHelper.java:544)

                at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:526)

Caused by: java.lang.ClassNotFoundException: org.jgrapht.Graph

                at java.net.URLClassLoader.findClass(URLClassLoader.java:381)

                at java.lang.ClassLoader.loadClass(ClassLoader.java:424)

                at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:331)

                at java.lang.ClassLoader.loadClass(ClassLoader.java:357)

                ... 7 more

“

I am guessing it’s something small that I am missing but it would be great if someone can give me some guidance on this, thanks!

 

Kind regards,

Cherie

[jgrapht-users] Running demos

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

Hi,

 

Sorry for this stupid question. I have cloned the repository from Github (checked out to the 1.0.1 version) and I would like to run the demo.

I tried running it in intellij and it’s giving me error: “package org.jgrapht.ext.GmlParser does not exist”

When I run “java –jar jgraph-demo-1.0.1jar” in the demo folder, it gave me the following error.

“Error: A JNI error has occurred, please check your installation and try again

Exception in thread "main" java.lang.NoClassDefFoundError: org/jgrapht/Graph

                at java.lang.Class.getDeclaredMethods0(Native Method)

                at java.lang.Class.privateGetDeclaredMethods(Class.java:2701)

                at java.lang.Class.privateGetMethodRecursive(Class.java:3048)

                at java.lang.Class.getMethod0(Class.java:3018)

                at java.lang.Class.getMethod(Class.java:1784)

                at sun.launcher.LauncherHelper.validateMainClass(LauncherHelper.java:544)

                at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:526)

Caused by: java.lang.ClassNotFoundException: org.jgrapht.Graph

                at java.net.URLClassLoader.findClass(URLClassLoader.java:381)

                at java.lang.ClassLoader.loadClass(ClassLoader.java:424)

                at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:331)

                at java.lang.ClassLoader.loadClass(ClassLoader.java:357)

                ... 7 more

“

I am guessing it’s something small that I am missing but it would be great if someone can give me some guidance on this, thanks!

 

Kind regards,

Cherie

Re: [jgrapht-users] Chinese Postman Problem

[Frank G. <fra...@fk...>]

Hi Joris,

It turns out that the number of odd vertices is fairly small for my dataset,
so I can actually just brute-force it most of the time and find some
heuristics for the one of two cases where the number is too large. Having
a non-optimal solution for just a few cases is acceptable. I did manage
to add that to your code, so we're happy for now.

Frank

On Tue, Mar 28, 2017 at 12:46:59PM -0400, J Kinable wrote:
> Hi Frank,
> 
> It turns out there's a flaw in the CPP implementation for *undirected*
> graphs.
> To solve the Chinese Postman Problem (CPP) for *undirected* graphs, it is
> necessary to compute a min cost perfect matching in a complete graph.
> Currently, JGraphT doesn't have such an algorithm. Initially I tried to get
> away with this by duplicating all the nodes in the complete graph and
> solving a min cost perfect matching on the resulting bipartite graph; this
> works for most, but, as you found out, not for all cases :(.
> 
> The CPP implementation for *directed* graphs works fine and is unaffected
> by this issue.
> 
> To solve the aforementioned Matching problem, ideally we implement this
> paper:
> Kolmogorov, V. Blossom V: a new implementation of a minimum cost perfect
> matching algorithm. Math. Prog. Comp. (2009) 1: 43.
> doi:10.1007/s12532-009-0002-8
> To the best of my knowledge, this is the fastest implementation at the
> moment.
> 
> I'm not aware of any simple-and-quick-to-implement algorithms for the min
> cost perfect matching problem in complete graphs, so it might take some
> time before we have a suitable implementation to solve this issue. Until
> then, the CPP implementation cannot be merged into JgraphT's master branch.
> On the bright side: the commented-out code at the bottom of
> ChinesePostman.java already fixes the flaw (it just requires a matching
> algorithm).
> 
> Obviously, this is not going to help you out in the short run, so here are
> 2 possible alternative solutions you could use:
> 
> 1. The CPP code for directed graphs works fine so you could use that.
> 
> 2. At the bottom of ChinesePostman.java
> <https://github.com/jgrapht/jgrapht/pull/385/files#diff-17a47bf2dc488441cb3b7a7f7e2ff318>
> there
> is commented-out code: this would be the correct implementation for the
> *undirected* version of the algorithm. You could use that code. Problem:
> this code needs a solver for the Min cost perfect matching problem in
> complete graphs. You would have to provide a solver for this yourself, as
> such a solver is currently not present in JGraphT. Here you have 3 options:
> 
> a. use a matching solver from some alternative open/closed source project.
> 
> b. implement a solver using an Integer Programming solver (assuming you
> have access to such a solver, this would be easy, as implementing the
> matching problem as a Mixed Integer Programming Problem is straightforward).
> c. implement a heuristic to solve the matching problem (this is rather
> suboptimal, since you may obviously loose the optimal solution)
> 
> 
> Btw, thanks for exposing this flaw!
> 
> 
> br,
> 
> 
> Joris Kinable
> 
> On Mon, Mar 27, 2017 at 6:21 PM, J Kinable <j.k...@gm...> wrote:
> 
> > I'm afraid you've encountered a bug... :( As long as the graph is strongly
> > connected (which is the case for your graph), then it must be possible to
> > find a feasible tour. For this H-shaped graph, I would expect a tour which
> > passes each edge exactly twice.
> > Thanks for reporting; I'll look into it.
> >
> > Joris Kinable
> >
> > On Mon, Mar 27, 2017 at 12:21 PM, Frank Gevaerts <fra...@fk...>
> > wrote:
> >
> >> Thank you, this is very helpful. I have tried this on our dataset, and it
> >> works for most of our dataset.
> >> One case I'm not entirely sure of is a H-shaped graph:
> >>
> >>             Graph<Integer, DefaultWeightedEdge> g=new
> >> SimpleWeightedGraph<>(DefaultWeightedEdge.class);
> >>             Graphs.addAllVertices(g, Arrays.asList(1, 2, 3, 4, 5, 6));
> >>             Graphs.addEdge(g, 1, 2, 1);
> >>             Graphs.addEdge(g, 2, 3, 1);
> >>             Graphs.addEdge(g, 3, 4, 1);
> >>             Graphs.addEdge(g, 2, 5, 1);
> >>             Graphs.addEdge(g, 3, 6, 1);
> >>
> >> Trying to get the CPP path for that gives me
> >> java.lang.IllegalArgumentException: Graph is not Eulerian
> >>
> >> I'm not entirely sure if this case is expected to work though.
> >>
> >> Frank
> >>
> >> `
> >> On Sun, Mar 26, 2017 at 04:36:41PM -0400, J Kinable wrote:
> >> > I've opened a pull request for the Chinese Postman Problem:
> >> > https://github.com/jgrapht/jgrapht/pull/385
> >> > The implementation supports both directed and undirected graphs. I
> >> realized
> >> > why I didn't finish the implementation initially: ideally the algorithm
> >> > requires a fast algorithm for Max Weight matchings in complete graphs,
> >> but
> >> > currently JgraphT doesn't have such implementation. As a trade-off I
> >> used a
> >> > slower bipartite matching algorithm.
> >> >
> >> > The code is fully functional and tested, but its final inclusion in
> >> JGraphT
> >> > will obviously depend on the review process. Feel free to fork my github
> >> > branch or wait until the implementation makes its way to Jgrapht's
> >> master
> >> > branch.
> >> >
> >> >
> >> > br,
> >> >
> >> > Joris Kinable
> >> >
> >> > On Wed, Mar 22, 2017 at 3:40 PM, J Kinable <j.k...@gm...> wrote:
> >> >
> >> > > Hi Frank,
> >> > >
> >> > > Currently JGraphT doesn't have algorithms for the Chinese Postman
> >> Problem
> >> > > (CPP).
> >> > >
> >> > > 1. Solving the CPP for mixed graphs is NP-hard. As far as I know, the
> >> best
> >> > > performing methods to solve the CPP for mixed graphs use Integer
> >> Linear
> >> > > Program Solvers. This is however hard to do in JGraphT since the best
> >> > > performing solvers (Cplex/Gurobi) are commercial and don't have a
> >> common
> >> > > interface. Similar issues appear for open source solvers. I'm not
> >> aware of
> >> > > any open source graph libraries that provide an implementation for the
> >> > > Mixed CPP.
> >> > >
> >> > > 2. On the other hand, the CPP for undirected graphs is much easier. At
> >> > > some point in the past I was working on an implementation for
> >> JGraphT. I
> >> > > can see whether I can finish it somewhere this week (that is, if I
> >> can find
> >> > > on which computer I stored it :) ).
> >> > >
> >> > > br,
> >> > >
> >> > > Joris Kinable
> >> > >
> >> > > On Wed, Mar 22, 2017 at 1:10 PM, Frank Gevaerts <
> >> fra...@fk...>
> >> > > wrote:
> >> > >
> >> > >> Hi,
> >> > >>
> >> > >> I'm looking for a library that can solve the Chinese Postman Problem
> >> (i.e.
> >> > >> finding a (ideally shortest) route that uses all edges in a graph),
> >> either
> >> > >> for undirected graphs, or for mixed graphs. Can JGraphT handle this,
> >> or
> >> > >> does
> >> > >> anyone know a different library I can use?
> >> > >>
> >> > >> My searches only seem to turn up academic papers but no usable code.
> >> > >>
> >> > >> Frank
> >> > >>
> >> > >> --
> >> > >> Frank Gevaerts                                 fra...@fk...
> >> > >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> >> > >> Schampbergstraat 32                            Tel:  ++32-(0)11-21
> >> 49 11
> >> > >> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22
> >> 04 19
> >> > >>
> >> > >> ------------------------------------------------------------
> >> > >> ------------------
> >> > >> Check out the vibrant tech community on one of the world's most
> >> > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> >> > >> _______________________________________________
> >> > >> jgrapht-users mailing list
> >> > >> jgr...@li...
> >> > >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >> > >>
> >> > >
> >> > >
> >>
> >> --
> >> Frank Gevaerts                                 fra...@fk...
> >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> >> Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
> >> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19
> >>
> >
> >

-- 
Frank Gevaerts                                 fra...@fk...
fks bvba - Formal and Knowledge Systems        http://www.fks.be/
Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19

Re: [jgrapht-users] Chinese Postman Problem

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

Hi Frank,

It turns out there's a flaw in the CPP implementation for *undirected*
graphs.
To solve the Chinese Postman Problem (CPP) for *undirected* graphs, it is
necessary to compute a min cost perfect matching in a complete graph.
Currently, JGraphT doesn't have such an algorithm. Initially I tried to get
away with this by duplicating all the nodes in the complete graph and
solving a min cost perfect matching on the resulting bipartite graph; this
works for most, but, as you found out, not for all cases :(.

The CPP implementation for *directed* graphs works fine and is unaffected
by this issue.

To solve the aforementioned Matching problem, ideally we implement this
paper:
Kolmogorov, V. Blossom V: a new implementation of a minimum cost perfect
matching algorithm. Math. Prog. Comp. (2009) 1: 43.
doi:10.1007/s12532-009-0002-8
To the best of my knowledge, this is the fastest implementation at the
moment.

I'm not aware of any simple-and-quick-to-implement algorithms for the min
cost perfect matching problem in complete graphs, so it might take some
time before we have a suitable implementation to solve this issue. Until
then, the CPP implementation cannot be merged into JgraphT's master branch.
On the bright side: the commented-out code at the bottom of
ChinesePostman.java already fixes the flaw (it just requires a matching
algorithm).

Obviously, this is not going to help you out in the short run, so here are
2 possible alternative solutions you could use:

1. The CPP code for directed graphs works fine so you could use that.

2. At the bottom of ChinesePostman.java
<https://github.com/jgrapht/jgrapht/pull/385/files#diff-17a47bf2dc488441cb3b7a7f7e2ff318>
there
is commented-out code: this would be the correct implementation for the
*undirected* version of the algorithm. You could use that code. Problem:
this code needs a solver for the Min cost perfect matching problem in
complete graphs. You would have to provide a solver for this yourself, as
such a solver is currently not present in JGraphT. Here you have 3 options:

a. use a matching solver from some alternative open/closed source project.

b. implement a solver using an Integer Programming solver (assuming you
have access to such a solver, this would be easy, as implementing the
matching problem as a Mixed Integer Programming Problem is straightforward).
c. implement a heuristic to solve the matching problem (this is rather
suboptimal, since you may obviously loose the optimal solution)


Btw, thanks for exposing this flaw!


br,


Joris Kinable

On Mon, Mar 27, 2017 at 6:21 PM, J Kinable <j.k...@gm...> wrote:

> I'm afraid you've encountered a bug... :( As long as the graph is strongly
> connected (which is the case for your graph), then it must be possible to
> find a feasible tour. For this H-shaped graph, I would expect a tour which
> passes each edge exactly twice.
> Thanks for reporting; I'll look into it.
>
> Joris Kinable
>
> On Mon, Mar 27, 2017 at 12:21 PM, Frank Gevaerts <fra...@fk...>
> wrote:
>
>> Thank you, this is very helpful. I have tried this on our dataset, and it
>> works for most of our dataset.
>> One case I'm not entirely sure of is a H-shaped graph:
>>
>>             Graph<Integer, DefaultWeightedEdge> g=new
>> SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>>             Graphs.addAllVertices(g, Arrays.asList(1, 2, 3, 4, 5, 6));
>>             Graphs.addEdge(g, 1, 2, 1);
>>             Graphs.addEdge(g, 2, 3, 1);
>>             Graphs.addEdge(g, 3, 4, 1);
>>             Graphs.addEdge(g, 2, 5, 1);
>>             Graphs.addEdge(g, 3, 6, 1);
>>
>> Trying to get the CPP path for that gives me
>> java.lang.IllegalArgumentException: Graph is not Eulerian
>>
>> I'm not entirely sure if this case is expected to work though.
>>
>> Frank
>>
>> `
>> On Sun, Mar 26, 2017 at 04:36:41PM -0400, J Kinable wrote:
>> > I've opened a pull request for the Chinese Postman Problem:
>> > https://github.com/jgrapht/jgrapht/pull/385
>> > The implementation supports both directed and undirected graphs. I
>> realized
>> > why I didn't finish the implementation initially: ideally the algorithm
>> > requires a fast algorithm for Max Weight matchings in complete graphs,
>> but
>> > currently JgraphT doesn't have such implementation. As a trade-off I
>> used a
>> > slower bipartite matching algorithm.
>> >
>> > The code is fully functional and tested, but its final inclusion in
>> JGraphT
>> > will obviously depend on the review process. Feel free to fork my github
>> > branch or wait until the implementation makes its way to Jgrapht's
>> master
>> > branch.
>> >
>> >
>> > br,
>> >
>> > Joris Kinable
>> >
>> > On Wed, Mar 22, 2017 at 3:40 PM, J Kinable <j.k...@gm...> wrote:
>> >
>> > > Hi Frank,
>> > >
>> > > Currently JGraphT doesn't have algorithms for the Chinese Postman
>> Problem
>> > > (CPP).
>> > >
>> > > 1. Solving the CPP for mixed graphs is NP-hard. As far as I know, the
>> best
>> > > performing methods to solve the CPP for mixed graphs use Integer
>> Linear
>> > > Program Solvers. This is however hard to do in JGraphT since the best
>> > > performing solvers (Cplex/Gurobi) are commercial and don't have a
>> common
>> > > interface. Similar issues appear for open source solvers. I'm not
>> aware of
>> > > any open source graph libraries that provide an implementation for the
>> > > Mixed CPP.
>> > >
>> > > 2. On the other hand, the CPP for undirected graphs is much easier. At
>> > > some point in the past I was working on an implementation for
>> JGraphT. I
>> > > can see whether I can finish it somewhere this week (that is, if I
>> can find
>> > > on which computer I stored it :) ).
>> > >
>> > > br,
>> > >
>> > > Joris Kinable
>> > >
>> > > On Wed, Mar 22, 2017 at 1:10 PM, Frank Gevaerts <
>> fra...@fk...>
>> > > wrote:
>> > >
>> > >> Hi,
>> > >>
>> > >> I'm looking for a library that can solve the Chinese Postman Problem
>> (i.e.
>> > >> finding a (ideally shortest) route that uses all edges in a graph),
>> either
>> > >> for undirected graphs, or for mixed graphs. Can JGraphT handle this,
>> or
>> > >> does
>> > >> anyone know a different library I can use?
>> > >>
>> > >> My searches only seem to turn up academic papers but no usable code.
>> > >>
>> > >> Frank
>> > >>
>> > >> --
>> > >> Frank Gevaerts                                 fra...@fk...
>> > >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
>> > >> Schampbergstraat 32                            Tel:  ++32-(0)11-21
>> 49 11
>> > >> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22
>> 04 19
>> > >>
>> > >> ------------------------------------------------------------
>> > >> ------------------
>> > >> Check out the vibrant tech community on one of the world's most
>> > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
>> > >> _______________________________________________
>> > >> jgrapht-users mailing list
>> > >> jgr...@li...
>> > >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>> > >>
>> > >
>> > >
>>
>> --
>> Frank Gevaerts                                 fra...@fk...
>> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
>> Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
>> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19
>>
>
>

Re: [jgrapht-users] Chinese Postman Problem

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

I'm afraid you've encountered a bug... :( As long as the graph is strongly
connected (which is the case for your graph), then it must be possible to
find a feasible tour. For this H-shaped graph, I would expect a tour which
passes each edge exactly twice.
Thanks for reporting; I'll look into it.

Joris Kinable

On Mon, Mar 27, 2017 at 12:21 PM, Frank Gevaerts <fra...@fk...>
wrote:

> Thank you, this is very helpful. I have tried this on our dataset, and it
> works for most of our dataset.
> One case I'm not entirely sure of is a H-shaped graph:
>
>             Graph<Integer, DefaultWeightedEdge> g=new
> SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>             Graphs.addAllVertices(g, Arrays.asList(1, 2, 3, 4, 5, 6));
>             Graphs.addEdge(g, 1, 2, 1);
>             Graphs.addEdge(g, 2, 3, 1);
>             Graphs.addEdge(g, 3, 4, 1);
>             Graphs.addEdge(g, 2, 5, 1);
>             Graphs.addEdge(g, 3, 6, 1);
>
> Trying to get the CPP path for that gives me java.lang.IllegalArgumentException:
> Graph is not Eulerian
>
> I'm not entirely sure if this case is expected to work though.
>
> Frank
>
> `
> On Sun, Mar 26, 2017 at 04:36:41PM -0400, J Kinable wrote:
> > I've opened a pull request for the Chinese Postman Problem:
> > https://github.com/jgrapht/jgrapht/pull/385
> > The implementation supports both directed and undirected graphs. I
> realized
> > why I didn't finish the implementation initially: ideally the algorithm
> > requires a fast algorithm for Max Weight matchings in complete graphs,
> but
> > currently JgraphT doesn't have such implementation. As a trade-off I
> used a
> > slower bipartite matching algorithm.
> >
> > The code is fully functional and tested, but its final inclusion in
> JGraphT
> > will obviously depend on the review process. Feel free to fork my github
> > branch or wait until the implementation makes its way to Jgrapht's master
> > branch.
> >
> >
> > br,
> >
> > Joris Kinable
> >
> > On Wed, Mar 22, 2017 at 3:40 PM, J Kinable <j.k...@gm...> wrote:
> >
> > > Hi Frank,
> > >
> > > Currently JGraphT doesn't have algorithms for the Chinese Postman
> Problem
> > > (CPP).
> > >
> > > 1. Solving the CPP for mixed graphs is NP-hard. As far as I know, the
> best
> > > performing methods to solve the CPP for mixed graphs use Integer Linear
> > > Program Solvers. This is however hard to do in JGraphT since the best
> > > performing solvers (Cplex/Gurobi) are commercial and don't have a
> common
> > > interface. Similar issues appear for open source solvers. I'm not
> aware of
> > > any open source graph libraries that provide an implementation for the
> > > Mixed CPP.
> > >
> > > 2. On the other hand, the CPP for undirected graphs is much easier. At
> > > some point in the past I was working on an implementation for JGraphT.
> I
> > > can see whether I can finish it somewhere this week (that is, if I can
> find
> > > on which computer I stored it :) ).
> > >
> > > br,
> > >
> > > Joris Kinable
> > >
> > > On Wed, Mar 22, 2017 at 1:10 PM, Frank Gevaerts <fra...@fk...
> >
> > > wrote:
> > >
> > >> Hi,
> > >>
> > >> I'm looking for a library that can solve the Chinese Postman Problem
> (i.e.
> > >> finding a (ideally shortest) route that uses all edges in a graph),
> either
> > >> for undirected graphs, or for mixed graphs. Can JGraphT handle this,
> or
> > >> does
> > >> anyone know a different library I can use?
> > >>
> > >> My searches only seem to turn up academic papers but no usable code.
> > >>
> > >> Frank
> > >>
> > >> --
> > >> Frank Gevaerts                                 fra...@fk...
> > >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> > >> Schampbergstraat 32                            Tel:  ++32-(0)11-21
> 49 11
> > >> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22
> 04 19
> > >>
> > >> ------------------------------------------------------------
> > >> ------------------
> > >> Check out the vibrant tech community on one of the world's most
> > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> > >> _______________________________________________
> > >> jgrapht-users mailing list
> > >> jgr...@li...
> > >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> > >>
> > >
> > >
>
> --
> Frank Gevaerts                                 fra...@fk...
> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19
>

Re: [jgrapht-users] Chinese Postman Problem

[Szabolcs B. <bes...@gm...>]

Hi,

In your case the HierholzerEulerianCycle#isEulerian(g) method returns
`false` since your graph contains odd degree vertices, thus
HierholzerEulerianCycle#getEulerianCycle(g) throws an
IllegalArgumentException.

Üdvözlettel,

Besenyei Szabolcs

2017-03-27 18:21 GMT+02:00 Frank Gevaerts <fra...@fk...>:

> Thank you, this is very helpful. I have tried this on our dataset, and it
> works for most of our dataset.
> One case I'm not entirely sure of is a H-shaped graph:
>
>             Graph<Integer, DefaultWeightedEdge> g=new
> SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>             Graphs.addAllVertices(g, Arrays.asList(1, 2, 3, 4, 5, 6));
>             Graphs.addEdge(g, 1, 2, 1);
>             Graphs.addEdge(g, 2, 3, 1);
>             Graphs.addEdge(g, 3, 4, 1);
>             Graphs.addEdge(g, 2, 5, 1);
>             Graphs.addEdge(g, 3, 6, 1);
>
> Trying to get the CPP path for that gives me java.lang.IllegalArgumentException:
> Graph is not Eulerian
>
> I'm not entirely sure if this case is expected to work though.
>
> Frank
>
> `
> On Sun, Mar 26, 2017 at 04:36:41PM -0400, J Kinable wrote:
> > I've opened a pull request for the Chinese Postman Problem:
> > https://github.com/jgrapht/jgrapht/pull/385
> > The implementation supports both directed and undirected graphs. I
> realized
> > why I didn't finish the implementation initially: ideally the algorithm
> > requires a fast algorithm for Max Weight matchings in complete graphs,
> but
> > currently JgraphT doesn't have such implementation. As a trade-off I
> used a
> > slower bipartite matching algorithm.
> >
> > The code is fully functional and tested, but its final inclusion in
> JGraphT
> > will obviously depend on the review process. Feel free to fork my github
> > branch or wait until the implementation makes its way to Jgrapht's master
> > branch.
> >
> >
> > br,
> >
> > Joris Kinable
> >
> > On Wed, Mar 22, 2017 at 3:40 PM, J Kinable <j.k...@gm...> wrote:
> >
> > > Hi Frank,
> > >
> > > Currently JGraphT doesn't have algorithms for the Chinese Postman
> Problem
> > > (CPP).
> > >
> > > 1. Solving the CPP for mixed graphs is NP-hard. As far as I know, the
> best
> > > performing methods to solve the CPP for mixed graphs use Integer Linear
> > > Program Solvers. This is however hard to do in JGraphT since the best
> > > performing solvers (Cplex/Gurobi) are commercial and don't have a
> common
> > > interface. Similar issues appear for open source solvers. I'm not
> aware of
> > > any open source graph libraries that provide an implementation for the
> > > Mixed CPP.
> > >
> > > 2. On the other hand, the CPP for undirected graphs is much easier. At
> > > some point in the past I was working on an implementation for JGraphT.
> I
> > > can see whether I can finish it somewhere this week (that is, if I can
> find
> > > on which computer I stored it :) ).
> > >
> > > br,
> > >
> > > Joris Kinable
> > >
> > > On Wed, Mar 22, 2017 at 1:10 PM, Frank Gevaerts <fra...@fk...
> >
> > > wrote:
> > >
> > >> Hi,
> > >>
> > >> I'm looking for a library that can solve the Chinese Postman Problem
> (i.e.
> > >> finding a (ideally shortest) route that uses all edges in a graph),
> either
> > >> for undirected graphs, or for mixed graphs. Can JGraphT handle this,
> or
> > >> does
> > >> anyone know a different library I can use?
> > >>
> > >> My searches only seem to turn up academic papers but no usable code.
> > >>
> > >> Frank
> > >>
> > >> --
> > >> Frank Gevaerts                                 fra...@fk...
> > >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> > >> Schampbergstraat 32                            Tel:  ++32-(0)11-21
> 49 11
> > >> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22
> 04 19
> > >>
> > >> ------------------------------------------------------------
> > >> ------------------
> > >> Check out the vibrant tech community on one of the world's most
> > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> > >> _______________________________________________
> > >> jgrapht-users mailing list
> > >> jgr...@li...
> > >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> > >>
> > >
> > >
>
> --
> Frank Gevaerts                                 fra...@fk...
> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19
>
> ------------------------------------------------------------
> ------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] Chinese Postman Problem

[Frank G. <fra...@fk...>]

Thank you, this is very helpful. I have tried this on our dataset, and it works for most of our dataset.
One case I'm not entirely sure of is a H-shaped graph:

            Graph<Integer, DefaultWeightedEdge> g=new SimpleWeightedGraph<>(DefaultWeightedEdge.class);
            Graphs.addAllVertices(g, Arrays.asList(1, 2, 3, 4, 5, 6));
            Graphs.addEdge(g, 1, 2, 1);
            Graphs.addEdge(g, 2, 3, 1);
            Graphs.addEdge(g, 3, 4, 1);
            Graphs.addEdge(g, 2, 5, 1);
            Graphs.addEdge(g, 3, 6, 1);

Trying to get the CPP path for that gives me java.lang.IllegalArgumentException: Graph is not Eulerian

I'm not entirely sure if this case is expected to work though.

Frank

`
On Sun, Mar 26, 2017 at 04:36:41PM -0400, J Kinable wrote:
> I've opened a pull request for the Chinese Postman Problem:
> https://github.com/jgrapht/jgrapht/pull/385
> The implementation supports both directed and undirected graphs. I realized
> why I didn't finish the implementation initially: ideally the algorithm
> requires a fast algorithm for Max Weight matchings in complete graphs, but
> currently JgraphT doesn't have such implementation. As a trade-off I used a
> slower bipartite matching algorithm.
> 
> The code is fully functional and tested, but its final inclusion in JGraphT
> will obviously depend on the review process. Feel free to fork my github
> branch or wait until the implementation makes its way to Jgrapht's master
> branch.
> 
> 
> br,
> 
> Joris Kinable
> 
> On Wed, Mar 22, 2017 at 3:40 PM, J Kinable <j.k...@gm...> wrote:
> 
> > Hi Frank,
> >
> > Currently JGraphT doesn't have algorithms for the Chinese Postman Problem
> > (CPP).
> >
> > 1. Solving the CPP for mixed graphs is NP-hard. As far as I know, the best
> > performing methods to solve the CPP for mixed graphs use Integer Linear
> > Program Solvers. This is however hard to do in JGraphT since the best
> > performing solvers (Cplex/Gurobi) are commercial and don't have a common
> > interface. Similar issues appear for open source solvers. I'm not aware of
> > any open source graph libraries that provide an implementation for the
> > Mixed CPP.
> >
> > 2. On the other hand, the CPP for undirected graphs is much easier. At
> > some point in the past I was working on an implementation for JGraphT. I
> > can see whether I can finish it somewhere this week (that is, if I can find
> > on which computer I stored it :) ).
> >
> > br,
> >
> > Joris Kinable
> >
> > On Wed, Mar 22, 2017 at 1:10 PM, Frank Gevaerts <fra...@fk...>
> > wrote:
> >
> >> Hi,
> >>
> >> I'm looking for a library that can solve the Chinese Postman Problem (i.e.
> >> finding a (ideally shortest) route that uses all edges in a graph), either
> >> for undirected graphs, or for mixed graphs. Can JGraphT handle this, or
> >> does
> >> anyone know a different library I can use?
> >>
> >> My searches only seem to turn up academic papers but no usable code.
> >>
> >> Frank
> >>
> >> --
> >> Frank Gevaerts                                 fra...@fk...
> >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> >> Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
> >> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19
> >>
> >> ------------------------------------------------------------
> >> ------------------
> >> Check out the vibrant tech community on one of the world's most
> >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> >> _______________________________________________
> >> jgrapht-users mailing list
> >> jgr...@li...
> >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>
> >
> >

-- 
Frank Gevaerts                                 fra...@fk...
fks bvba - Formal and Knowledge Systems        http://www.fks.be/
Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19

Re: [jgrapht-users] Chinese Postman Problem

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

I've opened a pull request for the Chinese Postman Problem:
https://github.com/jgrapht/jgrapht/pull/385
The implementation supports both directed and undirected graphs. I realized
why I didn't finish the implementation initially: ideally the algorithm
requires a fast algorithm for Max Weight matchings in complete graphs, but
currently JgraphT doesn't have such implementation. As a trade-off I used a
slower bipartite matching algorithm.

The code is fully functional and tested, but its final inclusion in JGraphT
will obviously depend on the review process. Feel free to fork my github
branch or wait until the implementation makes its way to Jgrapht's master
branch.


br,

Joris Kinable

On Wed, Mar 22, 2017 at 3:40 PM, J Kinable <j.k...@gm...> wrote:

> Hi Frank,
>
> Currently JGraphT doesn't have algorithms for the Chinese Postman Problem
> (CPP).
>
> 1. Solving the CPP for mixed graphs is NP-hard. As far as I know, the best
> performing methods to solve the CPP for mixed graphs use Integer Linear
> Program Solvers. This is however hard to do in JGraphT since the best
> performing solvers (Cplex/Gurobi) are commercial and don't have a common
> interface. Similar issues appear for open source solvers. I'm not aware of
> any open source graph libraries that provide an implementation for the
> Mixed CPP.
>
> 2. On the other hand, the CPP for undirected graphs is much easier. At
> some point in the past I was working on an implementation for JGraphT. I
> can see whether I can finish it somewhere this week (that is, if I can find
> on which computer I stored it :) ).
>
> br,
>
> Joris Kinable
>
> On Wed, Mar 22, 2017 at 1:10 PM, Frank Gevaerts <fra...@fk...>
> wrote:
>
>> Hi,
>>
>> I'm looking for a library that can solve the Chinese Postman Problem (i.e.
>> finding a (ideally shortest) route that uses all edges in a graph), either
>> for undirected graphs, or for mixed graphs. Can JGraphT handle this, or
>> does
>> anyone know a different library I can use?
>>
>> My searches only seem to turn up academic papers but no usable code.
>>
>> Frank
>>
>> --
>> Frank Gevaerts                                 fra...@fk...
>> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
>> Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
>> B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19
>>
>> ------------------------------------------------------------
>> ------------------
>> Check out the vibrant tech community on one of the world's most
>> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>
>

[jgrapht-users] Chinese Postman Problem

[Frank G. <fra...@fk...>]

Hi,

I'm looking for a library that can solve the Chinese Postman Problem (i.e.
finding a (ideally shortest) route that uses all edges in a graph), either
for undirected graphs, or for mixed graphs. Can JGraphT handle this, or does
anyone know a different library I can use?

My searches only seem to turn up academic papers but no usable code.

Frank

-- 
Frank Gevaerts                                 fra...@fk...
fks bvba - Formal and Knowledge Systems        http://www.fks.be/
Schampbergstraat 32                            Tel:  ++32-(0)11-21 49 11
B-3511 KURINGEN-HASSELT                        Fax:  ++32-(0)11-22 04 19

Re: [jgrapht-users] Lambda expressions in jgrapht

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

Sure, feel free to do so. It may be a nice way to get comfortable with
Github and the code submission system. Have a look at this first:
https://github.com/jgrapht/jgrapht/wiki/Contributor-Guidelines

Joris

On Mon, Mar 13, 2017 at 2:07 PM, apoorv <apo...@gm...>
wrote:

> Hi, I wanted to mention that I am relatively new to open-source. I see the
> opportunity to use lambda expressions in a few classes for example, in
> GraphMLDemo.java. Should I make a pull request to do that?
>
>
>
>
> --
> View this message in context: http://jgrapht-users.107614.
> n3.nabble.com/Lambda-expressions-in-jgrapht-tp4025133p4025136.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
> ------------------------------------------------------------
> ------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] Lambda expressions in jgrapht

[apoorv <apo...@gm...>]

Hi, I wanted to mention that I am relatively new to open-source. I see the
opportunity to use lambda expressions in a few classes for example, in
GraphMLDemo.java. Should I make a pull request to do that?




--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Lambda-expressions-in-jgrapht-tp4025133p4025136.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Lambda expressions in jgrapht

[apoorv <apo...@gm...>]

Thanks, will do so 



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Lambda-expressions-in-jgrapht-tp4025133p4025135.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Lambda expressions in jgrapht

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

In various places we are already using Lambda expressions. We've reworked
numerous classes since we upgraded from java 7 to java 8, but inevitably
there may some older pieces of code left. If you see any opportunities to
improve the quality of the code or to improve the performance of an
algorithm, feel free to submit a code contribution.

br,

Joris Kinable

On Sun, Mar 12, 2017 at 3:31 PM, apoorv <apo...@gm...>
wrote:

> Does jgrapht dev team have any plans for using lambda expressions in place
> of
> anonymous classes?
>
>
>
> --
> View this message in context: http://jgrapht-users.107614.
> n3.nabble.com/Lambda-expressions-in-jgrapht-tp4025133.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
> ------------------------------------------------------------
> ------------------
> Announcing the Oxford Dictionaries API! The API offers world-renowned
> dictionary content that is easy and intuitive to access. Sign up for an
> account today to start using our lexical data to power your apps and
> projects. Get started today and enter our developer competition.
> http://sdm.link/oxford
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Lambda expressions in jgrapht

[apoorv <apo...@gm...>]

Does jgrapht dev team have any plans for using lambda expressions in place of
anonymous classes?



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Lambda-expressions-in-jgrapht-tp4025133.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] Doubt regarding serialVersionUID in IntrusiveEdge.java and DefaultEdge.java

[apoorv <apo...@gm...>]

Hi, I read the code in IntrusiveEdge.java and DefaultEdge.java under the
package org.jgrapht.graph. I found that both classes have a variable
serialVersionUID declared as private static final long and contains the same
value even though the class DefaultEdge is a sublass of IntrusiveEdge class.
Couldn't we declare serialVersionUID to be protected in IntrusiveEdge class
and remove it from the DefaultEdge class?



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Doubt-regarding-serialVersionUID-in-IntrusiveEdge-java-and-DefaultEdge-java-tp4025132.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Help when import Jgrapht libs into Android Studio

[d-michail <dim...@gm...>]

Hi, 

I opened pull-request #376 on Github which fixes this. Consider testing it.

Thanks,
Dimitrios





--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Issue-when-import-Jgrapht-libs-into-Android-Studio-tp4025116p4025131.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] proposed interface change

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

Hey all,

One of the data modeling issues we faced way back when the JGraphT project
started was how to represent all the diverse critters which populate the
fascinating world of graph theory:  directed graphs, undirected graphs,
weighted graphs, acyclic graphs, simple graphs, pseudographs, multigraphs,
and on and on.  The decisions we made at that time were the following:

1) rule out some of the more exotic possibilities (e.g. hypergraphs)

2) use sub-interfaces to model some fundamental variations in graph
structure (namely DirectedGraph, UndirectedGraph, and WeightedGraph)

3) treat the rest of the possibilities as constraints on the fundamental
types, and provide a library of implementation classes to make it easy to
apply and combine them

This has worked out fairly well, but over the years, we've seen flaws crop
up, particularly around WeightedGraph (e.g.
https://github.com/jgrapht/jgrapht/issues/116), as well as a lot of
duplication of class implementations due to the split between DirectedGraph
and UndirectedGraph

After various discussions in github, the project committers have
collectively come up with a newer approach, and one of us (Dimitrios
Michail) has put a big effort into belling the cat:

https://github.com/jgrapht/jgrapht/pull/366

This pull request deprecates decision #2 above.  Namely, we are proposing
to phase out the UndirectedGraph, DirectedGraph, and WeightedGraph
interfaces, unifying all of their methods into the existing Graph
interface.  In place of compile-time type information, we're introducing
the GraphType interface as run-time type information.  Hence, where before
an algorithm might have required a DirectedGraph as input via method
signature, it will now take a Graph, and then throw an exception if a graph
of incorrect type is supplied as input.  This was already the approach for
the less fundamental graph aspects (e.g. when an algorithm prohibited
multigraphs as input), so now it is being applied uniformly.

We realize this may cause a bit of upgrade pain for existing apps which are
written in terms of the sub-interfaces being deprecated.  But we believe
it's a worthwhile tradeoff both in terms of library interface improvement
and long-term library maintainability.  As always, we're planning to go
through the usual deprecation process to make the transition as smooth as
possible for apps and dependent libraries.  But before moving ahead with
merging this pull request, we'd like to hear any feedback you might have on
the new approach.

Thanks!

[jgrapht-users] graph clustering etc

[Hendrik Lücke-T. <he...@ou...>]

Hi,

im currently evaluating if jgrapht is sufficient for my Needs. Am i right, that it does not contain any graph clustering algorithms (yet)? Are there even Interfaces for such a use case?

Best,
helt

Re: [jgrapht-users] Creating weighted directed graph using xml file as input

[Szabolcs B. <bes...@gm...>]

Hi,

https://github.com/jgrapht/jgrapht/blob/master/jgrapht-demo/src/main/java/org/jgrapht/demo/GraphMLDemo.java

Is this what you had in mind?

Regards,

Üdvözlettel,

Besenyei Szabolcs

2017-01-30 6:16 GMT+01:00 st chakra <stc...@gm...>:

> Hello,
>
> I want to create a weighted directed graph, using jgrapht from a xml file
> as input. I read in the documentation that jgrapht offers this feature but
> i am in need of an example to learn how to implement it. Can you please
> help with an example?
>
> Your help will be greatly appreciated.
>
> Thanks,
> Shreya
>
>
>
> ------------------------------------------------------------
> ------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, SlashDot.org! http://sdm.link/slashdot
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Creating weighted directed graph using xml file as input

[st c. <stc...@gm...>]

Hello,

I want to create a weighted directed graph, using jgrapht from a xml file
as input. I read in the documentation that jgrapht offers this feature but
i am in need of an example to learn how to implement it. Can you please
help with an example?

Your help will be greatly appreciated.

Thanks,
Shreya

[jgrapht-users] updated todo list and future enhancements

[Dimitrios M. <dim...@gm...>]

Hi all,

to accompany our latest release 1.0.1 we have compiled a list of
features/enhancements for the library, that we may work in the near future.

https://github.com/jgrapht/jgrapht/wiki/TODOs

We hope that by compiling such a list (a) more people will contribute to
the development of the library, and (b) it will be easier for someone new
to the codebase to get involved.

The list is by no means exhaustive, feel free to enhance functionality in
some other area and submit a pull-request.

Regards,
Dimitrios Michail

[jgrapht-users] JGraphT version 1.0.1 released

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

Hi all,

To start the new year right, we have released JGraphT version 1.0.1! Thanks
to all your contributions, this new release has many new features,
enhancements, quality-of-life improvements and bugfixes. For a full list of
changes, refer to https://github.com/jgrapht/jgrapht/blob/master/HISTORY.md.
Again, JGraphT wouldn't exist without your help, so continue submitting
those nice code contributions!

cheers,

Joris Kinable

[jgrapht-users] jgrapht release 1.0.1 pre-announcement

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

We are in the process of finalizing the next release of jgrapht, version
1.0.1. We've received a lot of very nice contributions, so this is going to
be another exciting release. The release is scheduled for sometime next
week. If you have any last-minute changes you would like to make available
for the upcoming release, then this is the time to submit them (pull
request or create a new issue).

br,

Joris Kinable