Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

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...> <js...@gm...>
> *À :* Osama Elswah <osa...@gm...><osa...@gm...>
> *Cc :* "jgr...@li..."<jgr...@li...>
> <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 lis...@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
>
>
>