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