Re: [jgrapht-users] Chinese Postman Problem
Brought to you by:
barak_naveh,
perfecthash
Menu
▾
▴
Re: [jgrapht-users] Chinese Postman Problem
|
From: Frank G. <fra...@fk...> - 2018-09-20 10:32:55
|
Hi Joris, That's excellent news! Thank you, and everyone involved. I'm currently working on a major new version of the software I needed it for last year, so this will definitely come in handy. Frank On Thu, Sep 20, 2018 at 01:13:52AM +0200, Joris Kinable wrote: > Hi Frank, > > Just to let you know, we now have a fully-functional algorithm for the > Chinese Postman Problem in jgrapht which supports both directed and > undirected, weighted and unweighted graphs. > > br, > > Joris Kinable > > On Wed, Mar 29, 2017 at 11:58 PM Frank Gevaerts <fra...@fk...> > wrote: > > > 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 > > -- 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 |
