You can subscribe to this list here.
2003 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(2) 
_{Nov}

_{Dec}


2004 
_{Jan}
(1) 
_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}
(1) 
_{Jul}
(1) 
_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(2) 
2005 
_{Jan}

_{Feb}
(1) 
_{Mar}
(5) 
_{Apr}
(1) 
_{May}

_{Jun}
(12) 
_{Jul}
(6) 
_{Aug}
(7) 
_{Sep}
(2) 
_{Oct}

_{Nov}
(1) 
_{Dec}

2006 
_{Jan}
(4) 
_{Feb}
(3) 
_{Mar}
(2) 
_{Apr}
(3) 
_{May}
(6) 
_{Jun}
(2) 
_{Jul}
(3) 
_{Aug}
(12) 
_{Sep}
(6) 
_{Oct}
(3) 
_{Nov}
(12) 
_{Dec}

2007 
_{Jan}
(6) 
_{Feb}

_{Mar}
(6) 
_{Apr}
(8) 
_{May}
(2) 
_{Jun}
(8) 
_{Jul}
(2) 
_{Aug}
(3) 
_{Sep}
(7) 
_{Oct}
(3) 
_{Nov}

_{Dec}
(1) 
2008 
_{Jan}
(11) 
_{Feb}
(4) 
_{Mar}
(8) 
_{Apr}
(3) 
_{May}
(4) 
_{Jun}
(1) 
_{Jul}

_{Aug}
(3) 
_{Sep}
(1) 
_{Oct}
(4) 
_{Nov}
(5) 
_{Dec}
(5) 
2009 
_{Jan}
(3) 
_{Feb}
(12) 
_{Mar}
(14) 
_{Apr}
(9) 
_{May}
(8) 
_{Jun}
(1) 
_{Jul}
(4) 
_{Aug}
(10) 
_{Sep}

_{Oct}
(10) 
_{Nov}

_{Dec}
(4) 
2010 
_{Jan}
(9) 
_{Feb}
(16) 
_{Mar}
(14) 
_{Apr}
(19) 
_{May}
(1) 
_{Jun}
(3) 
_{Jul}
(17) 
_{Aug}
(9) 
_{Sep}
(4) 
_{Oct}
(4) 
_{Nov}
(11) 
_{Dec}
(8) 
2011 
_{Jan}
(10) 
_{Feb}
(11) 
_{Mar}
(10) 
_{Apr}
(14) 
_{May}
(6) 
_{Jun}
(8) 
_{Jul}
(9) 
_{Aug}
(11) 
_{Sep}
(13) 
_{Oct}
(7) 
_{Nov}
(9) 
_{Dec}
(1) 
2012 
_{Jan}
(5) 
_{Feb}
(14) 
_{Mar}
(4) 
_{Apr}
(25) 
_{May}
(18) 
_{Jun}
(18) 
_{Jul}
(3) 
_{Aug}
(6) 
_{Sep}
(3) 
_{Oct}
(16) 
_{Nov}
(5) 
_{Dec}
(12) 
2013 
_{Jan}
(1) 
_{Feb}
(6) 
_{Mar}
(14) 
_{Apr}
(34) 
_{May}
(9) 
_{Jun}
(3) 
_{Jul}
(8) 
_{Aug}

_{Sep}
(10) 
_{Oct}
(11) 
_{Nov}
(11) 
_{Dec}
(15) 
2014 
_{Jan}
(2) 
_{Feb}
(6) 
_{Mar}
(11) 
_{Apr}
(12) 
_{May}
(6) 
_{Jun}
(7) 
_{Jul}

_{Aug}
(4) 
_{Sep}
(1) 
_{Oct}
(1) 
_{Nov}
(5) 
_{Dec}
(6) 
2015 
_{Jan}
(15) 
_{Feb}
(4) 
_{Mar}
(7) 
_{Apr}
(8) 
_{May}
(1) 
_{Jun}
(18) 
_{Jul}
(27) 
_{Aug}
(13) 
_{Sep}
(4) 
_{Oct}
(8) 
_{Nov}
(7) 
_{Dec}
(6) 
2016 
_{Jan}
(4) 
_{Feb}
(5) 
_{Mar}

_{Apr}
(15) 
_{May}
(5) 
_{Jun}
(4) 
_{Jul}
(1) 
_{Aug}
(1) 
_{Sep}
(7) 
_{Oct}
(2) 
_{Nov}
(4) 
_{Dec}
(2) 
2017 
_{Jan}
(7) 
_{Feb}
(1) 
_{Mar}
(17) 
_{Apr}
(2) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(3) 
_{Sep}
(3) 
_{Oct}

_{Nov}
(2) 
_{Dec}

From: John Sichi <jsichi@gm...>  20171115 01:20:47

We've just merged the complete removal of the deprecated undirected/directed/weighted graph interfaces into trunk. So, apps which depend on them (that is, most apps which use JGraphT) will need to be updated in order to be able to use versions of JGraphT past the latest (1.1) release. Joris, thanks as always for the release work!  Forwarded message  From: J Kinable <j.kinable@...> Date: Tue, Nov 14, 2017 at 4:58 AM Subject: [jgraphtannounce] JGraphT version 1.1 released To: jgraphtusers@..., jgraphtannounce@... Hi all, JGraphtT version 1.1 has been released! As always, thank you for your contributions. This release significantly reduces the number of different Graph interfaces: the interfaces UndirectedGraph, DirectedGraph and WeightedGraph have been deprecated. Instead, their functionality is captured in one, simple, clean *Graph* interface. This makes it much easier to implement algorithms, methods and classes which can work with various different graph types. For a full list of changes, refer to https://github.com/jgrapht/jgrapht /blob/master/HISTORY.md cheers, Joris Kinable   Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ jgraphtannounce mailing list jgraphtannounce@... https://lists.sourceforge.net/lists/listinfo/jgraphtannounce 
From: J Kinable <j.kinable@gm...>  20171114 12:58:39

Hi all, JGraphtT version 1.1 has been released! As always, thank you for your contributions. This release significantly reduces the number of different Graph interfaces: the interfaces UndirectedGraph, DirectedGraph and WeightedGraph have been deprecated. Instead, their functionality is captured in one, simple, clean *Graph* interface. This makes it much easier to implement algorithms, methods and classes which can work with various different graph types. For a full list of changes, refer to https://github.com/jgrapht/jgrapht /blob/master/HISTORY.md cheers, Joris Kinable 
From: J Kinable <j.kinable@gm...>  20170914 11:13:41

Currently there's no buildin function which can do that automatically for you. We are currently making this functionality available somewhere in the next few weeks, see Pull Request: https://github.com/jgrapht/jgrapht/pull/423 In the mean time, to get the desired behavior, you could implement your own DepthFirstSearch iterator. Or more conveniently, just copy mine: https://github.com/jkinable/jgrapht/blob/95daef5a6826818d00e113ac610415a763c5aee0/jgraphtcore/src/main/java/org/jgrapht/traverse/DepthFirstIterator.java This iterator has a new function getDepth(V v) which allows you to query the depth of a specific node (after the DFS completes, or after the node has been visited). So in order to query all nodes at a certain depth, you could write an additional function: //cache the nodes at a given depth Map<Integer,Set<V>> depthMap=new HashMap<>(); for(V v : graph.vertexSet()){ int depth=dfs.getDepth(v); if(!depthMap.containsKey(depth)) depthMap.put(depth, new HashSet<V>()); depthMap.get(depth).add(v); } Now you can easily query all nodes at a given depth: depthMap.get(3); On Thu, Sep 14, 2017 at 1:00 PM, Bobi Adji Andov <bobiadziandov@...> wrote: > Hello all, > > I am a new user to JGraphT and as every other newbie I am running into > ideas that I would like to solve with this library, but I am still not sure > how to do that. > > I am building a directed graph and I am wandering is there a way to get > all the nodes at certain depth (starting from a vertex). For example > something like get all nodes at depth 3 from certain vertex. > > Thanks in advance, > Slobodan > >  > > > > *Slobodan AdjiAndovskype:bobiadziandov* > >  >  > Check out the vibrant tech community on one of the world's most > engaging tech sites, Slashdot.org! http://sdm.link/slashdot > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > > 
From: Bobi Adji Andov <bobiadziandov@gm...>  20170914 11:00:39

Hello all, I am a new user to JGraphT and as every other newbie I am running into ideas that I would like to solve with this library, but I am still not sure how to do that. I am building a directed graph and I am wandering is there a way to get all the nodes at certain depth (starting from a vertex). For example something like get all nodes at depth 3 from certain vertex. Thanks in advance, Slobodan  *Slobodan AdjiAndovskype:bobiadziandov* 
From: J Kinable <j.kinable@gm...>  20170907 21:50:11

We are in the process of finalizing the next release of jgrapht, version 1.1. The release is scheduled for sometime this month. This release contains some major changes, including various simplifications to the graph interfaces. Moreover, several algorithms have been reimplemented, thereby adapting them to accept both directed and undirected graphs, while at the same time improving their overall performance. If you have any lastminute changes you would like to make available for the upcoming release, then this is the time to submit them (pull request or create a new issue). Similarly, if you still have open PRs lingering around, please fix any comments by the reviewers. br, Joris Kinable 
From: J Kinable <j.kinable@gm...>  20170817 20:18:24

Please address your replies to the entire list, not to me in person: this increases the likelihood that the original author of the algorithm chimes in. I'm unfortunately not familiar with the VF2 algorithm, or its implementation in jgrapht. I'd recommend to repeat your experiment. Keep your experiment as simple as possible to eliminate potential (common) causes of bugs. E.g.: 1. use Graph<Integer, DefaultEdge> g1=new SimpleGraph<>(DefaultEdge.class); for both graphs (instead of directed graphs which are cast to undirected graphs). 2. use Integer as vertex data type, not String. Finally: 1. Since checking whether 2 graphs are isomorphic is generally hard, please verify whether VF2 is a complete (exact) algorithm. 2. Provide a mapping from the vertices of g1 to the vertices of g2 to prove that the graphs are indeed isomorphic. If the graphs are indeed isomorphic, the algorithm is exact, and the algorithm returns false, please feel free to file a bug report using our issue tracker: https://github.com/jgrapht/jgrapht/issues Alternatively, if you are convinced that this is a bug, feel free to have a look at the source code (https://github.com/jgrapht/jgrapht) . The algorithm seems pretty short, so it may not be very hard to track down what's going wrong. thanks, Joris Kinable On Thu, Aug 17, 2017 at 2:37 PM, murad tukan <muradtuk@...> wrote: > Dear Joris, > > I have attached bellow the code for checking the isomorphism: > > > public class testing3 { > > private static DefaultDirectedGraph<String, DefaultEdge> graph1, > graph2; > private static IsomorphismInspector<String, DefaultEdge> inspector; > > > public static void main(String[] args) > { > > > graph1 = new DefaultDirectedGraph<String, > DefaultEdge>(DefaultEdge.class); > graph2 = new DefaultDirectedGraph<String, > DefaultEdge>(DefaultEdge.class); > > // graph1 > for(int i = 1; i <= 6; ++i) > { > graph1.addVertex(Integer.toString(i)); > graph2.addVertex(Integer.toString(i)); > } > > graph1.addEdge("1", "2"); > graph1.addEdge("2", "1"); > graph1.addEdge("1", "3"); > graph1.addEdge("3", "1"); > graph1.addEdge("1", "6"); > graph1.addEdge("6", "1"); > graph1.addEdge("2", "4"); > graph1.addEdge("4", "2"); > graph1.addEdge("2", "5"); > graph1.addEdge("5", "2"); > graph1.addEdge("3", "4"); > graph1.addEdge("4", "3"); > graph1.addEdge("3", "5"); > graph1.addEdge("5", "3"); > graph1.addEdge("4", "6"); > graph1.addEdge("6", "4"); > graph1.addEdge("5", "6"); > graph1.addEdge("6", "5"); > > > // graph2 > graph2.addEdge("1", "2"); > graph2.addEdge("2", "1"); > graph2.addEdge("1", "3"); > graph2.addEdge("3", "1"); > graph2.addEdge("1", "6"); > graph2.addEdge("6", "1"); > graph2.addEdge("2", "3"); > graph2.addEdge("3", "2"); > graph2.addEdge("2", "4"); > graph2.addEdge("4", "2"); > graph2.addEdge("3", "5"); > graph2.addEdge("5", "3"); > graph2.addEdge("4", "5"); > graph2.addEdge("5", "4"); > graph2.addEdge("4", "6"); > graph2.addEdge("6", "4"); > graph2.addEdge("5", "6"); > graph2.addEdge("6", "5"); > > UndirectedGraph<String, DefaultEdge> g1 = new > AsUndirectedGraph<String, DefaultEdge>(graph1); > UndirectedGraph<String, DefaultEdge> g2 = new > AsUndirectedGraph<String, DefaultEdge>(graph2); > > inspector = new VF2GraphIsomorphismInspector<String, > DefaultEdge>(g1,g2); > System.err.println(inspector.isomorphismExists()); > } > > } > > For such graph, the result should be true rather than false (Also i > checked using MATLAB graph isomorphism solver and it returned true). > > To get more intuition why the two graphs are isomorphic, see the actual > graphs: > > [image: Inline image 2] > > > Please advise. > > Thanks in advance, > M.T. > > P.s. Also tried using SimpleGraph and still got false in term of > isomorphic or not. > > On Thu, Aug 17, 2017 at 7:48 AM, J Kinable <j.kinable@...> wrote: > >> Hi, >> >> Can you be a bit more specific? What is the graph you are testing on? Can >> you show a code snippet. Preferably provide a small working example, and >> describe the expected output. >> >> br, >> >> Joris Kinable >> >> On Wed, Aug 16, 2017 at 9:59 PM, murad tukan <muradtuk@...> wrote: >> >>> Dear sir/madam, >>> >>> I have tried your vf2 algorithm a.k.a. VF2GraphIsomorphismInspector on >>> the following graphs by replacing each edge by two directional edges such >>> that each is in opposite direction in order to obtain a directed graph. >>> The algorithm returned false when it should have returned true. >>> >>> Is there a bug in the implementation of VF2 or I misrepresented the >>> graphs? >>> >>> Please advise as soon as possible. >>> >>> Thanks in advance, >>> M.T. >>> >>>  >>>  >>> Check out the vibrant tech community on one of the world's most >>> engaging tech sites, Slashdot.org! http://sdm.link/slashdot >>> _______________________________________________ >>> jgraphtusers mailing list >>> jgraphtusers@... >>> https://lists.sourceforge.net/lists/listinfo/jgraphtusers >>> >>> >> > 
From: J Kinable <j.kinable@gm...>  20170817 11:49:02

Hi, Can you be a bit more specific? What is the graph you are testing on? Can you show a code snippet. Preferably provide a small working example, and describe the expected output. br, Joris Kinable On Wed, Aug 16, 2017 at 9:59 PM, murad tukan <muradtuk@...> wrote: > Dear sir/madam, > > I have tried your vf2 algorithm a.k.a. VF2GraphIsomorphismInspector on the > following graphs by replacing each edge by two directional edges such that > each is in opposite direction in order to obtain a directed graph. > The algorithm returned false when it should have returned true. > > Is there a bug in the implementation of VF2 or I misrepresented the graphs? > > Please advise as soon as possible. > > Thanks in advance, > M.T. > >  >  > Check out the vibrant tech community on one of the world's most > engaging tech sites, Slashdot.org! http://sdm.link/slashdot > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > > 
From: murad tukan <muradtuk@gm...>  20170817 02:00:20

Dear sir/madam, I have tried your vf2 algorithm a.k.a. VF2GraphIsomorphismInspector on the following graphs by replacing each edge by two directional edges such that each is in opposite direction in order to obtain a directed graph. The algorithm returned false when it should have returned true. Is there a bug in the implementation of VF2 or I misrepresented the graphs? Please advise as soon as possible. Thanks in advance, M.T. 
From: Michał Urban <michalurban@op...>  20170528 19:07:31

ello I've created graph using JGraphT library g = new ListenableUndirectedWeightedGraph <String, MyEdge>(MyEdge.class); graphAdapter = new JGraphXAdapter<String, MyEdge>(g); layout = new mxOrganicLayout(graphAdapter); layout.execute(graphAdapter.getDefaultParent()); mxGraphComponent component = new mxGraphComponent(graphAdapter); component.setPreferredSize(new Dimension(dim.width  50, dim.height  200)); add(component); and I want to add dynamically a new vertex after pushing the button @Override public void actionPerformed(ActionEvent e) { String a="1"; String b="2"; g.addVertex(a); g.addVertex(b); g.addEdge(a,b); } public static class MyEdge extends DefaultWeightedEdge { //weight @Override public String toString() { return String.valueOf(getWeight()); } } how can I refresh the view? 
From: dmichail <dimitrios.michail@gm...>  20170410 10:53:53

Hi, some matching algorithms in bipartite graphs perform computation for every vertex in the left partition. Thus, what you are observing is reasonable. Swapping the two partitions is a common optimization trick. Feel free to submit a pullrequest if you observe a significant performance gain. Best, Dimitrios  View this message in context: http://jgraphtusers.107614.n3.nabble.com/JGraphTmatchingoptimizationstp4025147p4025148.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: Ben Horner <ben.k.horner@gm...>  20170407 22:43:36

Hello there, I just found some interesting performance characteristics of the matching algorithms. The tests are not complete, put it appears that the implementations (possibly the algorithms themselves?) are sensitive to which partition is passed first. I think pretty good performance gains can be had by passing the smallest partition first, and this check could be incorporated into the algorithms (constructors), so you'd get the advantage regardless of which order you pass the partitions. I can supply my test code, and/or the timing data if you like. I thought I would first ask, to see if this is known already, and expected. Thanks, Ben 
From: Cherie Pun <cherie.cy.pun@gm...>  20170331 10:21:01

Hi, I am really sorry to spam you but I just want to say it worked after I cleared my dependency cache. Thanks for your time! Kind regards, Cherie From: Cherie Pun <cherie.cy.pun@...> Date: Friday, 31 March 2017 at 10:11 To: <jgraphtusers@...> Subject: Running demos Hi, Sorry for this stupid question. I have cloned the repository from Github (checked out to the 1.0.1 version) and I would like to run the demo. I tried running it in intellij and it’s giving me error: “package org.jgrapht.ext.GmlParser does not exist” When I run “java –jar jgraphdemo1.0.1jar” in the demo folder, it gave me the following error. “Error: A JNI error has occurred, please check your installation and try again Exception in thread "main" java.lang.NoClassDefFoundError: org/jgrapht/Graph at java.lang.Class.getDeclaredMethods0(Native Method) at java.lang.Class.privateGetDeclaredMethods(Class.java:2701) at java.lang.Class.privateGetMethodRecursive(Class.java:3048) at java.lang.Class.getMethod0(Class.java:3018) at java.lang.Class.getMethod(Class.java:1784) at sun.launcher.LauncherHelper.validateMainClass(LauncherHelper.java:544) at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:526) Caused by: java.lang.ClassNotFoundException: org.jgrapht.Graph at java.net.URLClassLoader.findClass(URLClassLoader.java:381) at java.lang.ClassLoader.loadClass(ClassLoader.java:424) at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:331) at java.lang.ClassLoader.loadClass(ClassLoader.java:357) ... 7 more “ I am guessing it’s something small that I am missing but it would be great if someone can give me some guidance on this, thanks! Kind regards, Cherie 
From: Cherie Pun <cherie.cy.pun@gm...>  20170331 09:11:30

Hi, Sorry for this stupid question. I have cloned the repository from Github (checked out to the 1.0.1 version) and I would like to run the demo. I tried running it in intellij and it’s giving me error: “package org.jgrapht.ext.GmlParser does not exist” When I run “java –jar jgraphdemo1.0.1jar” in the demo folder, it gave me the following error. “Error: A JNI error has occurred, please check your installation and try again Exception in thread "main" java.lang.NoClassDefFoundError: org/jgrapht/Graph at java.lang.Class.getDeclaredMethods0(Native Method) at java.lang.Class.privateGetDeclaredMethods(Class.java:2701) at java.lang.Class.privateGetMethodRecursive(Class.java:3048) at java.lang.Class.getMethod0(Class.java:3018) at java.lang.Class.getMethod(Class.java:1784) at sun.launcher.LauncherHelper.validateMainClass(LauncherHelper.java:544) at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:526) Caused by: java.lang.ClassNotFoundException: org.jgrapht.Graph at java.net.URLClassLoader.findClass(URLClassLoader.java:381) at java.lang.ClassLoader.loadClass(ClassLoader.java:424) at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:331) at java.lang.ClassLoader.loadClass(ClassLoader.java:357) ... 7 more “ I am guessing it’s something small that I am missing but it would be great if someone can give me some guidance on this, thanks! Kind regards, Cherie 
From: Frank Gevaerts <frank.gevaerts@fk...>  20170329 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 bruteforce it most of the time and find some heuristics for the one of two cases where the number is too large. Having a nonoptimal 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/s1253200900028 > To the best of my knowledge, this is the fastest implementation at the > moment. > > I'm not aware of any simpleandquicktoimplement 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 commentedout 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#diff17a47bf2dc488441cb3b7a7f7e2ff318>; > there > is commentedout 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.kinable@...> 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 Hshaped 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 <frank.gevaerts@...> > > 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 Hshaped 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 tradeoff 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.kinable@...> wrote: > >> > > >> > > Hi Frank, > >> > > > >> > > Currently JGraphT doesn't have algorithms for the Chinese Postman > >> Problem > >> > > (CPP). > >> > > > >> > > 1. Solving the CPP for mixed graphs is NPhard. 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 < > >> frank.gevaerts@...> > >> > > 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 frank.gevaerts@... > >> > >> fks bvba  Formal and Knowledge Systems http://www.fks.be/ > >> > >> Schampbergstraat 32 Tel: ++32(0)1121 > >> 49 11 > >> > >> B3511 KURINGENHASSELT Fax: ++32(0)1122 > >> 04 19 > >> > >> > >> > >>  > >> > >>  > >> > >> Check out the vibrant tech community on one of the world's most > >> > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot > >> > >> _______________________________________________ > >> > >> jgraphtusers mailing list > >> > >> jgraphtusers@... > >> > >> https://lists.sourceforge.net/lists/listinfo/jgraphtusers > >> > >> > >> > > > >> > > > >> > >>  > >> Frank Gevaerts frank.gevaerts@... > >> fks bvba  Formal and Knowledge Systems http://www.fks.be/ > >> Schampbergstraat 32 Tel: ++32(0)1121 49 11 > >> B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 > >> > > > >  Frank Gevaerts frank.gevaerts@... fks bvba  Formal and Knowledge Systems http://www.fks.be/ Schampbergstraat 32 Tel: ++32(0)1121 49 11 B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 
From: J Kinable <j.kinable@gm...>  20170328 16:47:27

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/s1253200900028 To the best of my knowledge, this is the fastest implementation at the moment. I'm not aware of any simpleandquicktoimplement 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 commentedout 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#diff17a47bf2dc488441cb3b7a7f7e2ff318>; there is commentedout 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.kinable@...> 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 Hshaped 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 <frank.gevaerts@...> > 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 Hshaped 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 tradeoff 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.kinable@...> wrote: >> > >> > > Hi Frank, >> > > >> > > Currently JGraphT doesn't have algorithms for the Chinese Postman >> Problem >> > > (CPP). >> > > >> > > 1. Solving the CPP for mixed graphs is NPhard. 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 < >> frank.gevaerts@...> >> > > 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 frank.gevaerts@... >> > >> fks bvba  Formal and Knowledge Systems http://www.fks.be/ >> > >> Schampbergstraat 32 Tel: ++32(0)1121 >> 49 11 >> > >> B3511 KURINGENHASSELT Fax: ++32(0)1122 >> 04 19 >> > >> >> > >>  >> > >>  >> > >> Check out the vibrant tech community on one of the world's most >> > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot >> > >> _______________________________________________ >> > >> jgraphtusers mailing list >> > >> jgraphtusers@... >> > >> https://lists.sourceforge.net/lists/listinfo/jgraphtusers >> > >> >> > > >> > > >> >>  >> Frank Gevaerts frank.gevaerts@... >> fks bvba  Formal and Knowledge Systems http://www.fks.be/ >> Schampbergstraat 32 Tel: ++32(0)1121 49 11 >> B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 >> > > 
From: J Kinable <j.kinable@gm...>  20170327 22:22:12

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 Hshaped 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 <frank.gevaerts@...> 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 Hshaped 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 tradeoff 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.kinable@...> wrote: > > > > > Hi Frank, > > > > > > Currently JGraphT doesn't have algorithms for the Chinese Postman > Problem > > > (CPP). > > > > > > 1. Solving the CPP for mixed graphs is NPhard. 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 <frank.gevaerts@... > > > > > 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 frank.gevaerts@... > > >> fks bvba  Formal and Knowledge Systems http://www.fks.be/ > > >> Schampbergstraat 32 Tel: ++32(0)1121 > 49 11 > > >> B3511 KURINGENHASSELT Fax: ++32(0)1122 > 04 19 > > >> > > >>  > > >>  > > >> Check out the vibrant tech community on one of the world's most > > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot > > >> _______________________________________________ > > >> jgraphtusers mailing list > > >> jgraphtusers@... > > >> https://lists.sourceforge.net/lists/listinfo/jgraphtusers > > >> > > > > > > > >  > Frank Gevaerts frank.gevaerts@... > fks bvba  Formal and Knowledge Systems http://www.fks.be/ > Schampbergstraat 32 Tel: ++32(0)1121 49 11 > B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 > 
From: Szabolcs Besenyei <besza.elte@gm...>  20170327 17:15:34

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 20170327 18:21 GMT+02:00 Frank Gevaerts <frank.gevaerts@...>: > 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 Hshaped 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 tradeoff 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.kinable@...> wrote: > > > > > Hi Frank, > > > > > > Currently JGraphT doesn't have algorithms for the Chinese Postman > Problem > > > (CPP). > > > > > > 1. Solving the CPP for mixed graphs is NPhard. 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 <frank.gevaerts@... > > > > > 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 frank.gevaerts@... > > >> fks bvba  Formal and Knowledge Systems http://www.fks.be/ > > >> Schampbergstraat 32 Tel: ++32(0)1121 > 49 11 > > >> B3511 KURINGENHASSELT Fax: ++32(0)1122 > 04 19 > > >> > > >>  > > >>  > > >> Check out the vibrant tech community on one of the world's most > > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot > > >> _______________________________________________ > > >> jgraphtusers mailing list > > >> jgraphtusers@... > > >> https://lists.sourceforge.net/lists/listinfo/jgraphtusers > > >> > > > > > > > >  > Frank Gevaerts frank.gevaerts@... > fks bvba  Formal and Knowledge Systems http://www.fks.be/ > Schampbergstraat 32 Tel: ++32(0)1121 49 11 > B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 > >  >  > Check out the vibrant tech community on one of the world's most > engaging tech sites, Slashdot.org! http://sdm.link/slashdot > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: Frank Gevaerts <frank.gevaerts@fk...>  20170327 16:21:32

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 Hshaped 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 tradeoff 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.kinable@...> wrote: > > > Hi Frank, > > > > Currently JGraphT doesn't have algorithms for the Chinese Postman Problem > > (CPP). > > > > 1. Solving the CPP for mixed graphs is NPhard. 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 <frank.gevaerts@...> > > 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 frank.gevaerts@... > >> fks bvba  Formal and Knowledge Systems http://www.fks.be/ > >> Schampbergstraat 32 Tel: ++32(0)1121 49 11 > >> B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 > >> > >>  > >>  > >> Check out the vibrant tech community on one of the world's most > >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot > >> _______________________________________________ > >> jgraphtusers mailing list > >> jgraphtusers@... > >> https://lists.sourceforge.net/lists/listinfo/jgraphtusers > >> > > > >  Frank Gevaerts frank.gevaerts@... fks bvba  Formal and Knowledge Systems http://www.fks.be/ Schampbergstraat 32 Tel: ++32(0)1121 49 11 B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 
From: J Kinable <j.kinable@gm...>  20170326 20:37:11

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 tradeoff 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.kinable@...> wrote: > Hi Frank, > > Currently JGraphT doesn't have algorithms for the Chinese Postman Problem > (CPP). > > 1. Solving the CPP for mixed graphs is NPhard. 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 <frank.gevaerts@...> > 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 frank.gevaerts@... >> fks bvba  Formal and Knowledge Systems http://www.fks.be/ >> Schampbergstraat 32 Tel: ++32(0)1121 49 11 >> B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 >> >>  >>  >> Check out the vibrant tech community on one of the world's most >> engaging tech sites, Slashdot.org! http://sdm.link/slashdot >> _______________________________________________ >> jgraphtusers mailing list >> jgraphtusers@... >> https://lists.sourceforge.net/lists/listinfo/jgraphtusers >> > > 
From: Frank Gevaerts <frank.gevaerts@fk...>  20170322 17:27:00

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 frank.gevaerts@... fks bvba  Formal and Knowledge Systems http://www.fks.be/ Schampbergstraat 32 Tel: ++32(0)1121 49 11 B3511 KURINGENHASSELT Fax: ++32(0)1122 04 19 
From: J Kinable <j.kinable@gm...>  20170313 18:26:03

Sure, feel free to do so. It may be a nice way to get comfortable with Github and the code submission system. Have a look at this first: https://github.com/jgrapht/jgrapht/wiki/ContributorGuidelines Joris On Mon, Mar 13, 2017 at 2:07 PM, apoorv <apoorvmishra101092@...> wrote: > Hi, I wanted to mention that I am relatively new to opensource. I see the > opportunity to use lambda expressions in a few classes for example, in > GraphMLDemo.java. Should I make a pull request to do that? > > > > >  > View this message in context: http://jgraphtusers.107614. > n3.nabble.com/Lambdaexpressionsinjgraphttp4025133p4025136.html > Sent from the jgraphtusers mailing list archive at Nabble.com. > >  >  > Check out the vibrant tech community on one of the world's most > engaging tech sites, Slashdot.org! http://sdm.link/slashdot > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: apoorv <apoorvmishra101092@gm...>  20170313 18:07:36

Hi, I wanted to mention that I am relatively new to opensource. I see the opportunity to use lambda expressions in a few classes for example, in GraphMLDemo.java. Should I make a pull request to do that?  View this message in context: http://jgraphtusers.107614.n3.nabble.com/Lambdaexpressionsinjgraphttp4025133p4025136.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: apoorv <apoorvmishra101092@gm...>  20170313 18:02:35

Thanks, will do so  View this message in context: http://jgraphtusers.107614.n3.nabble.com/Lambdaexpressionsinjgraphttp4025133p4025135.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: J Kinable <j.kinable@gm...>  20170313 17:53:34

In various places we are already using Lambda expressions. We've reworked numerous classes since we upgraded from java 7 to java 8, but inevitably there may some older pieces of code left. If you see any opportunities to improve the quality of the code or to improve the performance of an algorithm, feel free to submit a code contribution. br, Joris Kinable On Sun, Mar 12, 2017 at 3:31 PM, apoorv <apoorvmishra101092@...> wrote: > Does jgrapht dev team have any plans for using lambda expressions in place > of > anonymous classes? > > > >  > View this message in context: http://jgraphtusers.107614. > n3.nabble.com/Lambdaexpressionsinjgraphttp4025133.html > Sent from the jgraphtusers mailing list archive at Nabble.com. > >  >  > Announcing the Oxford Dictionaries API! The API offers worldrenowned > dictionary content that is easy and intuitive to access. Sign up for an > account today to start using our lexical data to power your apps and > projects. Get started today and enter our developer competition. > http://sdm.link/oxford > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: apoorv <apoorvmishra101092@gm...>  20170312 19:31:10

Does jgrapht dev team have any plans for using lambda expressions in place of anonymous classes?  View this message in context: http://jgraphtusers.107614.n3.nabble.com/Lambdaexpressionsinjgraphttp4025133.html Sent from the jgraphtusers mailing list archive at Nabble.com. 