jgrapht-users

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

[Sebastian M. <woo...@gm...>]

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

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

[John S. <js...@gm...>]

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
>
>

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

[Osama E. <osa...@gm...>]

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
>
>

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

[John S. <js...@gm...>]

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
>>
>>
>

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

[Sebastian M. <woo...@gm...>]

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

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

[John S. <js...@gm...>]

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
>
>

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

[John S. <js...@gm...>]

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
>

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

[gu b. <bou...@ya...>]

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

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

[Osama E. <osa...@gm...>]

Hello
Where can I find the fix to this problem ?



On Tue, Apr 30, 2013 at 11:53 AM, gu boulmi <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...>
> *À :* 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
>
>
>
> ------------------------------------------------------------------------------
> 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
>
>

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

[Sebastian M. <woo...@gm...>]

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

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

[persteffen <per...@gm...>]

I had a similar problem, it turned out I had forgotten to implement the
hashCode() method. See:

https://github.com/jgrapht/jgrapht/wiki/EqualsAndHashCode




--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/graph-must-contain-the-start-vertex-when-running-KShortestPaths-tp4024797p4024833.html
Sent from the jgrapht-users mailing list archive at Nabble.com.