"graph must contain the start vertex" when running KShortestPaths

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

"graph must contain the start vertex" when running KShortestPaths

Sebastian Müller
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

edges.txt (27K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

John Sichi
Administrator
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 <[hidden email]> 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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

Osama Elswah
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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

John Sichi
Administrator
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

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 <[hidden email]>
À : Osama Elswah <[hidden email]>
Cc : "[hidden email]" <[hidden email]>
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

RankingPathElementList.java (20K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

Sebastian Müller
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 [hidden email]
À : Osama Elswah [hidden email]
Cc : [hidden email] [hidden email]
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

John Sichi
Administrator
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 <[hidden email]> 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 [hidden email]
À : Osama Elswah [hidden email]
Cc : [hidden email] [hidden email]
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

gu boulmi
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 <[hidden email]>
À : Sebastian Müller <[hidden email]>
Cc : "[hidden email]" <[hidden email]>
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 <[hidden email]> 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 [hidden email]
À : Osama Elswah [hidden email]
Cc : [hidden email] [hidden email]
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

KSP-yet-another-correction_24042013.zip (20K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

John Sichi
Administrator
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!


JVS

On Wed, Apr 24, 2013 at 4:50 AM, gu boulmi <[hidden email]> 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 <[hidden email]>
À : Sebastian Müller <[hidden email]>
Cc : "[hidden email]" <[hidden email]>
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 <[hidden email]> 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 [hidden email]
À : Osama Elswah [hidden email]
Cc : [hidden email] [hidden email]
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Tr : "graph must contain the start vertex" when running KShortestPaths

gu boulmi
I forgot the mailing list...

----- Mail transféré -----
De : gu boulmi <[hidden email]>
À : John Sichi <[hidden email]>
Cc : Sebastian Müller <[hidden email]>
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 <[hidden email]>
À : gu boulmi <[hidden email]>
Cc : Sebastian Müller <[hidden email]>; "[hidden email]" <[hidden email]>
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!


JVS

On Wed, Apr 24, 2013 at 4:50 AM, gu boulmi <[hidden email]> 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 <[hidden email]>
À : Sebastian Müller <[hidden email]>
Cc : "[hidden email]" <[hidden email]>
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 <[hidden email]> 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 [hidden email]
À : Osama Elswah [hidden email]
Cc : [hidden email] [hidden email]
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

KShortestPathsIterator.java (16K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Tr : "graph must contain the start vertex" when running KShortestPaths

John Sichi
Administrator
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 <[hidden email]> wrote:

> I forgot the mailing list...
>
> ----- Mail transféré -----
> De : gu boulmi <[hidden email]>
> À : John Sichi <[hidden email]>
> Cc : Sebastian Müller <[hidden email]>
> 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 <[hidden email]>
> À : gu boulmi <[hidden email]>
> Cc : Sebastian Müller <[hidden email]>;
> "[hidden email]" <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]>
> À : Sebastian Müller <[hidden email]>
> Cc : "[hidden email]"
> <[hidden email]>
> 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 <[hidden email]>
> 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 <[hidden email]>
> À : Osama Elswah <[hidden email]>
> Cc : "[hidden email]"
> <[hidden email]>
> 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 <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]>
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Tr : "graph must contain the start vertex" when running KShortestPaths

gu boulmi
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 <[hidden email]>
À : gu boulmi <[hidden email]>
Cc : "[hidden email]" <[hidden email]>
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 <[hidden email]> wrote:

> I forgot the mailing list...
>
> ----- Mail transféré -----
> De : gu boulmi <[hidden email]>
> À : John Sichi <[hidden email]>
> Cc : Sebastian Müller <[hidden email]>
> 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 <[hidden email]>
> À : gu boulmi <[hidden email]>
> Cc : Sebastian Müller <[hidden email]>;
> "[hidden email]" <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]>
> À : Sebastian Müller <[hidden email]>
> Cc : "[hidden email]"
> <[hidden email]>
> 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 <[hidden email]>
> 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 <[hidden email]>
> À : Osama Elswah <[hidden email]>
> Cc : "[hidden email]"
> <[hidden email]>
> 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 <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]>
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Tr : "graph must contain the start vertex" when running KShortestPaths

Osama Elswah
Hello
Where can I find the fix to this problem ?



On Tue, Apr 30, 2013 at 11:53 AM, gu boulmi <[hidden email]> 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 <[hidden email]>
À : gu boulmi <[hidden email]>
Cc : "[hidden email]" <[hidden email]>
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 <[hidden email]> wrote:
> I forgot the mailing list...
>
> ----- Mail transféré -----
> De : gu boulmi <[hidden email]>
> À : John Sichi <[hidden email]>
> Cc : Sebastian Müller <[hidden email]>
> 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 <[hidden email]>
> À : gu boulmi <[hidden email]>
> Cc : Sebastian Müller <[hidden email]>;
> "[hidden email]" <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]>
> À : Sebastian Müller <[hidden email]>
> Cc : "[hidden email]"
> <[hidden email]>
> 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 <[hidden email]>
> 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 <[hidden email]>
> À : Osama Elswah <[hidden email]>
> Cc : "[hidden email]"
> <[hidden email]>
> 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 <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]>
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Tr : "graph must contain the start vertex" when running KShortestPaths

Sebastian Müller
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 <[hidden email]> 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 <[hidden email]>
À : gu boulmi <[hidden email]>
Cc : "[hidden email]" <[hidden email]>
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 <[hidden email]> wrote:
> I forgot the mailing list...
>
> ----- Mail transféré -----
> De : gu boulmi <[hidden email]>
> À : John Sichi <[hidden email]>
> Cc : Sebastian Müller <[hidden email]>
> 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 <[hidden email]>
> À : gu boulmi <[hidden email]>
> Cc : Sebastian Müller <[hidden email]>;
> "[hidden email]" <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]>
> À : Sebastian Müller <[hidden email]>
> Cc : "[hidden email]"
> <[hidden email]>
> 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 <[hidden email]>
> 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 <[hidden email]>
> À : Osama Elswah <[hidden email]>
> Cc : "[hidden email]"
> <[hidden email]>
> 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 <[hidden email]>
> 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 <[hidden email]> 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 <[hidden email]>
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
> [hidden email]
> 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
[hidden email]
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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "graph must contain the start vertex" when running KShortestPaths

persteffen
In reply to this post by Sebastian Müller
I had a similar problem, it turned out I had forgotten to implement the hashCode() method. See:

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