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...> - 2017-03-29 21:58:39
|
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 |
