Re: [jgrapht-users] Tr : "graph must contain the start vertex" when running KShortestPaths
Brought to you by:
barak_naveh,
perfecthash
From: gu b. <bou...@ya...> - 2013-04-30 09:53:38
|
I really also hope that it is the last ==/equals bug in the KSP algorithm ! Your remark about the String ID's is good and it makes think that the bug raised by Sebastian could only apply to graphs constructed this way. Good point ! Guillaume ________________________________ De : John Sichi <js...@gm...> À : gu boulmi <bou...@ya...> Cc : "jgr...@li..." <jgr...@li...> Envoyé le : Mardi 30 avril 2013 7h12 Objet : Re: [jgrapht-users] Tr : "graph must contain the start vertex" when running KShortestPaths Thanks a lot for following up. I've applied all of the changes for completeness. Regarding your PS, I do not believe that any ID's actually "changed" during the execution. It's just that when the strings are read in from the text file, multiple String objects are created with the same value. And even though there's only one D007 vertex object added to the graph, there can be different String objects in the edges which reference it. I hope that is the last ==/equals bug (we've had the same problem show up in other algorithms). It's hard to write a findbugs rule to catch it since there are legitimate reasons to use == in some cases. JVS On Mon, Apr 29, 2013 at 8:02 AM, gu boulmi <bou...@ya...> wrote: > I forgot the mailing list... > > ----- Mail transféré ----- > De : gu boulmi <bou...@ya...> > À : John Sichi <js...@gm...> > Cc : Sebastian Müller <woo...@gm...> > Envoyé le : Samedi 27 avril 2013 15h32 > > Objet : Re: [jgrapht-users] "graph must contain the start vertex" when > running KShortestPaths > > Hi, > Actually a lost of JUnit tests on graphs with cycles (e.g. all the tests on > complete graphs) already exists and it works. > > In fact, I think that the initial isSimplePath method would work fine on any > graph provided that a String vertex does not > change id during the execution of the KSP algorithm (see my comments in my > mail 17.04.2013). > > The root cause of the problem encountered by Sebastian about the non-simple > paths result is rather (again) the use of the != instead of !equals in a > method, namely in the KShortestPathsIterator#updateOutgoingVertices method : > // check if the path does not loop over the start vertex. > if (vertexReachedByEdge != this.startVertex) > > instead it should be : > if (!vertexReachedByEdge.equals(this.startVertex)) > > The correction from my previous mail 24.04.2013 of the isSimplePath method > can be preserved however. > Indeed, accordinf to the name of the method is should return true only for a > path path with no repeated vertices and the > former implementation made an exception to that for the start vertex. > > To sum up, the correction attached to the KShortestPathsIterator class would > be enough. Nevertheless the correction from my mail 24.04.2013 can be > preserved anyway for the sake of clarity of the isSimplePath method. > > Best regards, > Guillaume > > P.S. : I do not know yet why a String vertex like D007 would change id > during the execution of the algorithm. I guess it is specific to String > vertices... > > > De : John Sichi <js...@gm...> > À : gu boulmi <bou...@ya...> > Cc : Sebastian Müller <woo...@gm...>; > "jgr...@li..." <jgr...@li...> > Envoyé le : Jeudi 25 avril 2013 9h08 > Objet : Re: [jgrapht-users] "graph must contain the start vertex" when > running KShortestPaths > > Thanks! I will update github. Probably the reason the existing tests > didn't catch the problem is that they use a graph without cycles? > > Looks like in the past it has already been spotted out there in the wild, so > I am glad it is getting fixed! > > http://jgrapht-users.107614.n3.nabble.com/Re-JGraphT-Enquiry-KShortestPaths-Bug-td4024711.html > > JVS > > On Wed, Apr 24, 2013 at 4:50 AM, gu boulmi <bou...@ya...> wrote: > > Hi, > You're so right with the do/while. > Please find attached a new correction to the RankingPathElementList class > along with a JUnit test (reproducing the test program of Sebastian that led > to the IllegalArgumentException with text "graph must contain the start > vertex"). > I just wonder why this error did not pop up earlier with the existing JUnit > tests about the number of paths returned by the KSP algorithm. > > I think that there is no problem with the PathMask constructor. No change > needed. > > Best regards, > Guillaume > > De : John Sichi <js...@gm...> > À : Sebastian Müller <woo...@gm...> > Cc : "jgr...@li..." > <jgr...@li...> > Envoyé le : Jeudi 18 avril 2013 0h18 > Objet : Re: [jgrapht-users] "graph must contain the start vertex" when > running KShortestPaths > > Guillaume: thanks for looking into this! > > Sebastian: you're right about the non-simple paths. Looking at the same > isSimplePath method, it looks like it should be using a do/while construct > instead of a while/do construct. If I make that change, then with your test > case, I get back only simple paths (which are longer than the "cheating by > running around in circles" non-simple paths). Guillaume, do you think I > should make this change? If so do I need to make a corresponding change in > the PathMask constructor? > > > On Wed, Apr 17, 2013 at 3:49 AM, Sebastian Müller <woo...@gm...> > wrote: > > Hi all, > > I can confirm that the exception is now gone. Thanks for the quick fix! > Just one more thing. The javadoc for KShortestPaths states 'The algorithm > determines the k shortest simple paths [...]'. According to my understanding > the paths calculated by KShortestPaths are not simple. See my example below. > > [code] > <M042 M013 0.90> : 0.90 > <M042 M043 0.76> <M043 M042 0.76> <M042 M013 > 0.909439166411278> : 2.43 > <M042 M029 0.87> <M029 M042 0.96> <M042 M013 0.90> > : 2.74 > <M042 M044 0.92> <M044 M043 0.76> <M043 M042 0.76> > <M042 M013 0.90> : 3.36 > <M042 M028 0.91> <M028 M043 0.81> <M043 M042 0.76> > <M042 M013 0.90> : 3.39 > [/code] > > > Thanks for the great work with JGraphT, all! > > Sebastian > > > Am 17.04.2013 11:52, schrieb gu boulmi: > > Hi all, > I just made a debug thanks to the test provided by Sebastian. > See attached the correction. > > I came to the conclusion that was a mistake in the way to test whether there > is a loop in a path (i.e. two of the same vertex in the path) in the method > org.jgrapht.alg.RankingPathElementList#isSimplePath > > Actually, the test failed when testing the simple path property of a path > resulting from adding the edge M004-D007 at the end of path > M014-D010-D007-M004. Of course the resulting path is not simple (twice > D007), however it returned true. > When debugging, it appears that the id of the D007 vertex of the edge > M004-D007 and the id of the D007 vertex of the path M014-D010-D007-M004 were > not the same, although they represent the same vertex (namely D007). The > existing implementation wrongly returned true because the ids of D007 were > not the same while it tested the equality with the == method. > > I changed it by replacing the == by the equals method and it just works. > New implementation is now : > private boolean isSimplePath( > RankingPathElement<V, E> prevPathElement, > E edge) > { > RankingPathElement<V, E> pathElementToTest = prevPathElement; > while (pathElementToTest.getPrevEdge() != null) { > if (pathElementToTest.getVertex().equals(this.vertex)) { > return false; > } else { > pathElementToTest = pathElementToTest.getPrevPathElement(); > } > } > > return true; > } > > Strange anyway : no guess why a String vertex like D007 would change id > during the execution of the algorithm. > > Best regards, > Guillaume > > De : John Sichi <js...@gm...> > À : Osama Elswah <osa...@gm...> > Cc : "jgr...@li..." > <jgr...@li...> > Envoyé le : Mardi 16 avril 2013 23h04 > Objet : Re: [jgrapht-users] "graph must contain the start vertex" when > running KShortestPaths > > Before my previous reply, I reproduced Sebastian's problem by running his > code, which is why I say it's a bug. His input graph is correctly > constructed, so there's no reason that assertion should be hit. > > > On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah <osa...@gm...> > wrote: > > I have been using KShortestPath for some time now, and it has been doing its > purpose. I am not sure it has a bug. > This is how I use it > > for(V n : network.vertexSet()) > { > KShortestPaths<V, E> k = new KShortestPaths<V, E>(network, n, > k); > for(Demand<V> d : demands.getAllDemands()) > { > if((d.getSourceNode().equals(n))) > { > demand_paths = k.getPaths(d.getTargetNode()); > pathsMap.put(d.getSourceNode(), d.getTargetNode(), > demand_paths); > } > } > } > } > > What is the output of this line ? > > DefaultWeightedEdge src = graph.getEdge("M013", "M014"); > > I believe if you debug more there you will find the problem > > good luck > > > On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...> wrote: > > Looks like a bug in KShortestPaths. Internally, the algorithm uses a masked > version of the original graph, and the mask omits a vertex on which the > algorithm attempts the connectivity test, leading to the assertion failure. > Anyone know the algorithm well enough to submit a fix with confidence? > > JVS > > > > On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...> > wrote: > > Hello, > > sorry this is such a long mail, but I included a test program, and my graph > is quite large. > > I am using JGraphT to create graphs of my data with great success so far. > However, now I am trying to calculate the shortest paths between two nodes > using KShortestPaths, and I only receive the following exception: > > [code] > java.lang.IllegalArgumentException: graph must contain the start vertex > at > org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170) > at > org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92) > at > org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142) > at > org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208) > at > org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347) > at > org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364) > at > org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203) > at > org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361) > at > org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398) > at > org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177) > at org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150) > at KShortestPathsMain.main(KShortestPathsMain.java:97) > [/code] > > Note that I am only getting this exception with that one, large graph I > created from my data. When I create a graph by hand, it does not occur. Here > is my test program. The graph is attached. > > [code] > import java.io.BufferedReader; > import java.io.FileNotFoundException; > import java.io.FileReader; > import java.io.IOException; > import java.util.List; > > import org.jgrapht.GraphPath; > import org.jgrapht.alg.KShortestPaths; > import org.jgrapht.graph.DefaultWeightedEdge; > import org.jgrapht.graph.SimpleWeightedGraph; > > public class KShortestPathsMain { > > public KShortestPathsMain() {} > > public static void main(String[] args) { > > SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new > SimpleWeightedGraph<>(DefaultWeightedEdge.class); > > FileReader fstream = null; > try { > fstream = new FileReader("edges.txt"); > } catch (FileNotFoundException e1) { > e1.printStackTrace(); > } > BufferedReader in = new BufferedReader(fstream); > > String[] edgeText; > DefaultWeightedEdge ed; > String line = null; > try { > line = in.readLine(); > } catch (IOException e1) { > // TODO Auto-generated catch block > e1.printStackTrace(); > } > while(line != null) { > edgeText = line.split("\t"); > > graph.addVertex(edgeText[0]); > graph.addVertex(edgeText[1]); > ed = graph.addEdge(edgeText[0], edgeText[1]); > graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2])); > > try { > line = in.readLine(); > } catch (IOException e) { > e.printStackTrace(); > } > } > > // Close the input stream > try { > in.close(); > } catch (IOException e1) { > e1.printStackTrace(); > } > > DefaultWeightedEdge src = graph.getEdge("M013", "M014"); > > KShortestPaths<String, DefaultWeightedEdge> kPaths = new > KShortestPaths<String, DefaultWeightedEdge>( > graph, graph.getEdgeSource(src), 5); > List<GraphPath<String,DefaultWeightedEdge>> paths = null; > > try { > paths = kPaths.getPaths(graph.getEdgeTarget(src)); > for (GraphPath<String, DefaultWeightedEdge> path : paths) { > for (DefaultWeightedEdge edge : path.getEdgeList()) { > System.out.print("<" + graph.getEdgeSource(edge) + "\t" > + graph.getEdgeTarget(edge) + "\t" + edge + > ">\t"); > } > System.out.println(": " + path.getWeight()); > } > } catch (IllegalArgumentException e) { > e.printStackTrace(); > } > } > } > > [/code] > > I tried different edges, and directed and undirected graphs. Same result. If > anyone has a clue what might be going on here, I'd very much appreciate > help. > > > Sebastian > > ------------------------------------------------------------------------------ > Precog is a next-generation analytics platform capable of advanced > analytics on semi-structured data. The platform includes APIs for building > apps and a phenomenal toolset for data science. Developers can use > our toolset for easy data analysis & visualization. Get a free account! > http://www2.precog.com/precogplatform/slashdotnewsletter > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > > > > ------------------------------------------------------------------------------ > Precog is a next-generation analytics platform capable of advanced > analytics on semi-structured data. The platform includes APIs for building > apps and a phenomenal toolset for data science. Developers can use > our toolset for easy data analysis & visualization. Get a free account! > http://www2.precog.com/precogplatform/slashdotnewsletter > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > > > > > ------------------------------------------------------------------------------ > Precog is a next-generation analytics platform capable of advanced > analytics on semi-structured data. The platform includes APIs for building > apps and a phenomenal toolset for data science. Developers can use > our toolset for easy data analysis & visualization. Get a free account! > http://www2.precog.com/precogplatform/slashdotnewsletter > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > > > > > ------------------------------------------------------------------------------ > Precog is a next-generation analytics platform capable of advanced > analytics on semi-structured data. The platform includes APIs for building > apps and a phenomenal toolset for data science. Developers can use > our toolset for easy data analysis & visualization. Get a free account! > http://www2.precog.com/precogplatform/slashdotnewsletter > > > > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > > > > ------------------------------------------------------------------------------ > Precog is a next-generation analytics platform capable of advanced > analytics on semi-structured data. The platform includes APIs for building > apps and a phenomenal toolset for data science. Developers can use > our toolset for easy data analysis & visualization. Get a free account! > http://www2.precog.com/precogplatform/slashdotnewsletter > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > > > > ------------------------------------------------------------------------------ > Precog is a next-generation analytics platform capable of advanced > analytics on semi-structured data. The platform includes APIs for building > apps and a phenomenal toolset for data science. Developers can use > our toolset for easy data analysis & visualization. Get a free account! > http://www2.precog.com/precogplatform/slashdotnewsletter > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > > > > > > > > > ------------------------------------------------------------------------------ > Try New Relic Now & We'll Send You this Cool Shirt > New Relic is the only SaaS-based application performance monitoring service > that delivers powerful full stack analytics. Optimize and monitor your > browser, app, & servers with just a few lines of code. Try New Relic > and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr > _______________________________________________ > jgrapht-users mailing list > jgr...@li... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > ------------------------------------------------------------------------------ Introducing AppDynamics Lite, a free troubleshooting tool for Java/.NET Get 100% visibility into your production application - at no cost. Code-level diagnostics for performance bottlenecks with <2% overhead Download for free and get started troubleshooting in minutes. http://p.sf.net/sfu/appdyn_d2d_ap1 _______________________________________________ jgrapht-users mailing list jgr...@li... https://lists.sourceforge.net/lists/listinfo/jgrapht-users |