Menu
▾
▴
Re: [jgrapht-users] Tr : "graph must contain the start vertex" when running KShortestPaths
|
From: Sebastian M. <woo...@gm...> - 2013-05-06 12:38:59
|
Osama, it is included in the latest commit on github: https://github.com/jgrapht/jgrapht Sebastian Am 06.05.2013 14:30, schrieb Osama Elswah: > Hello > Where can I find the fix to this problem ? > > > > On Tue, Apr 30, 2013 at 11:53 AM, gu boulmi <bou...@ya... > <mailto:bou...@ya...>> wrote: > > 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... <mailto:js...@gm...>> > *À :* gu boulmi <bou...@ya... <mailto:bou...@ya...>> > *Cc :* "jgr...@li... > <mailto:jgr...@li...>" > <jgr...@li... > <mailto: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... > <mailto:bou...@ya...>> wrote: > > I forgot the mailing list... > > > > ----- Mail transféré ----- > > De : gu boulmi <bou...@ya... <mailto:bou...@ya...>> > > À : John Sichi <js...@gm... <mailto:js...@gm...>> > > Cc : Sebastian Müller <woo...@gm... > <mailto: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... <mailto:js...@gm...>> > > À : gu boulmi <bou...@ya... <mailto:bou...@ya...>> > > Cc : Sebastian Müller <woo...@gm... > <mailto:woo...@gm...>>; > > "jgr...@li... > <mailto:jgr...@li...>" > <jgr...@li... > <mailto: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... > <mailto: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... <mailto:js...@gm...>> > > À : Sebastian Müller <woo...@gm... > <mailto:woo...@gm...>> > > Cc : "jgr...@li... > <mailto:jgr...@li...>" > > <jgr...@li... > <mailto: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... <mailto: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... <mailto:js...@gm...>> > > À : Osama Elswah <osa...@gm... > <mailto:osa...@gm...>> > > Cc : "jgr...@li... > <mailto:jgr...@li...>" > > <jgr...@li... > <mailto: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... <mailto: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... > <mailto: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... <mailto: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... > <mailto: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... > <mailto: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... > <mailto: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... > <mailto: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... > <mailto: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... > <mailto: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... > <mailto: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... > <mailto: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... > <mailto: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 |
