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