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
>