Chinese Postman Problem

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Chinese Postman Problem

Frank Gevaerts
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                                 [hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Chinese Postman Problem

J Kinable
I've opened a pull request for the Chinese Postman Problem:
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 <[hidden email]> 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 <[hidden email]> 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                                 [hidden email]
fks bvba - Formal and Knowledge Systems        http://www.fks.be/
Schampbergstraat 32                            Tel:  <a href="tel:%2B%2B32-%280%2911-21%2049%2011" value="+3211214911" target="_blank">++32-(0)11-21 49 11
B-3511 KURINGEN-HASSELT                        Fax:  <a href="tel:%2B%2B32-%280%2911-22%2004%2019" value="+3211220419" target="_blank">++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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Chinese Postman Problem

Frank Gevaerts
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 <[hidden email]> 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 <[hidden email]>
> > 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                                 [hidden email]
> >> 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
> >> [hidden email]
> >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>
> >
> >

--
Frank Gevaerts                                 [hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Chinese Postman Problem

Szabolcs Besenyei
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 <[hidden email]>:
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 <[hidden email]> 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 <[hidden email]>
> > 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                                 [hidden email]
> >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> >> Schampbergstraat 32                            Tel:  <a href="tel:%2B%2B32-%280%2911-21%2049%2011" value="+3211214911">++32-(0)11-21 49 11
> >> B-3511 KURINGEN-HASSELT                        Fax:  <a href="tel:%2B%2B32-%280%2911-22%2004%2019" value="+3211220419">++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
> >> [hidden email]
> >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>
> >
> >

--
Frank Gevaerts                                 [hidden email]
fks bvba - Formal and Knowledge Systems        http://www.fks.be/
Schampbergstraat 32                            Tel:  <a href="tel:%2B%2B32-%280%2911-21%2049%2011" value="+3211214911">++32-(0)11-21 49 11
B-3511 KURINGEN-HASSELT                        Fax:  <a href="tel:%2B%2B32-%280%2911-22%2004%2019" value="+3211220419">++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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Chinese Postman Problem

J Kinable
In reply to this post by Frank Gevaerts
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]>
> > 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                                 [hidden email]
> >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> >> Schampbergstraat 32                            Tel:  <a href="tel:%2B%2B32-%280%2911-21%2049%2011" value="+3211214911">++32-(0)11-21 49 11
> >> B-3511 KURINGEN-HASSELT                        Fax:  <a href="tel:%2B%2B32-%280%2911-22%2004%2019" value="+3211220419">++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
> >> [hidden email]
> >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>
> >
> >

--
Frank Gevaerts                                 [hidden email]
fks bvba - Formal and Knowledge Systems        http://www.fks.be/
Schampbergstraat 32                            Tel:  <a href="tel:%2B%2B32-%280%2911-21%2049%2011" value="+3211214911">++32-(0)11-21 49 11
B-3511 KURINGEN-HASSELT                        Fax:  <a href="tel:%2B%2B32-%280%2911-22%2004%2019" value="+3211220419">++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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Chinese Postman Problem

J Kinable

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 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]>
> > 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                                 [hidden email]
> >> fks bvba - Formal and Knowledge Systems        http://www.fks.be/
> >> Schampbergstraat 32                            Tel:  <a href="tel:%2B%2B32-%280%2911-21%2049%2011" value="+3211214911" target="_blank">++32-(0)11-21 49 11
> >> B-3511 KURINGEN-HASSELT                        Fax:  <a href="tel:%2B%2B32-%280%2911-22%2004%2019" value="+3211220419" target="_blank">++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
> >> [hidden email]
> >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >>
> >
> >

--
Frank Gevaerts                                 [hidden email]
fks bvba - Formal and Knowledge Systems        http://www.fks.be/
Schampbergstraat 32                            Tel:  <a href="tel:%2B%2B32-%280%2911-21%2049%2011" value="+3211214911" target="_blank">++32-(0)11-21 49 11
B-3511 KURINGEN-HASSELT                        Fax:  <a href="tel:%2B%2B32-%280%2911-22%2004%2019" value="+3211220419" target="_blank">++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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Chinese Postman Problem

Frank Gevaerts
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 <[hidden email]> 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 <[hidden email]>
> > 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 <[hidden email]> 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 <
> >> [hidden email]>
> >> > > 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                                 [hidden email]
> >> > >> 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
> >> > >> [hidden email]
> >> > >> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >> > >>
> >> > >
> >> > >
> >>
> >> --
> >> Frank Gevaerts                                 [hidden email]
> >> 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                                 [hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...