Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths
Brought to you by:
barak_naveh,
perfecthash
Menu
▾
▴
Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths
|
From: Sebastian M. <woo...@gm...> - 2013-04-17 10:49:55
|
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... <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...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
|