Re: [jgrapht-users] Chinese Postman Problem
Brought to you by:
barak_naveh,
perfecthash
Menu
▾
▴
Re: [jgrapht-users] Chinese Postman Problem
|
From: Joris K. <j.k...@gm...> - 2018-09-19 23:14:13
|
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 > |
