|
From: John S. <js...@gm...> - 2013-04-16 08:04:03
|
Looks like a bug in KShortestPaths. Internally, the algorithm uses a
masked version of the original graph, and the mask omits a vertex on which
the algorithm attempts the connectivity test, leading to the assertion
failure. Anyone know the algorithm well enough to submit a fix with
confidence?
JVS
On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>wrote:
> Hello,
>
> sorry this is such a long mail, but I included a test program, and my
> graph is quite large.
>
> I am using JGraphT to create graphs of my data with great success so far.
> However, now I am trying to calculate the shortest paths between two nodes
> using KShortestPaths, and I only receive the following exception:
>
> [code]
> java.lang.**IllegalArgumentException: graph must contain the start vertex
> at org.jgrapht.traverse.**CrossComponentIterator.<init>(**
> CrossComponentIterator.java:**170)
> at org.jgrapht.traverse.**BreadthFirstIterator.<init>(**
> BreadthFirstIterator.java:92)
> at org.jgrapht.alg.**ConnectivityInspector.**connectedSetOf(**
> ConnectivityInspector.java:**142)
> at org.jgrapht.alg.**ConnectivityInspector.**pathExists(**
> ConnectivityInspector.java:**208)
> at org.jgrapht.alg.**RankingPathElementList.**
> isGuardVertexDisconnected(**RankingPathElementList.java:**347)
> at org.jgrapht.alg.**RankingPathElementList.**isNotValidPath(**
> RankingPathElementList.java:**364)
> at org.jgrapht.alg.**RankingPathElementList.**addPathElements(**
> RankingPathElementList.java:**203)
> at org.jgrapht.alg.**KShortestPathsIterator.**tryToAddNewPaths(**
> KShortestPathsIterator.java:**361)
> at org.jgrapht.alg.**KShortestPathsIterator.**updateOutgoingVertices(*
> *KShortestPathsIterator.java:**398)
> at org.jgrapht.alg.**KShortestPathsIterator.next(**
> KShortestPathsIterator.java:**177)
> at org.jgrapht.alg.**KShortestPaths.getPaths(**
> KShortestPaths.java:150)
> at KShortestPathsMain.main(**KShortestPathsMain.java:97)
> [/code]
>
> Note that I am only getting this exception with that one, large graph I
> created from my data. When I create a graph by hand, it does not occur.
> Here is my test program. The graph is attached.
>
> [code]
> import java.io.BufferedReader;
> import java.io.FileNotFoundException;
> import java.io.FileReader;
> import java.io.IOException;
> import java.util.List;
>
> import org.jgrapht.GraphPath;
> import org.jgrapht.alg.**KShortestPaths;
> import org.jgrapht.graph.**DefaultWeightedEdge;
> import org.jgrapht.graph.**SimpleWeightedGraph;
>
> public class KShortestPathsMain {
>
> public KShortestPathsMain() {}
>
> public static void main(String[] args) {
>
> SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
> SimpleWeightedGraph<>(**DefaultWeightedEdge.class);
>
> FileReader fstream = null;
> try {
> fstream = new FileReader("edges.txt");
> } catch (FileNotFoundException e1) {
> e1.printStackTrace();
> }
> BufferedReader in = new BufferedReader(fstream);
>
> String[] edgeText;
> DefaultWeightedEdge ed;
> String line = null;
> try {
> line = in.readLine();
> } catch (IOException e1) {
> // TODO Auto-generated catch block
> e1.printStackTrace();
> }
> while(line != null) {
> edgeText = line.split("\t");
>
> graph.addVertex(edgeText[0]);
> graph.addVertex(edgeText[1]);
> ed = graph.addEdge(edgeText[0], edgeText[1]);
> graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]**
> ));
>
> try {
> line = in.readLine();
> } catch (IOException e) {
> e.printStackTrace();
> }
> }
>
> // Close the input stream
> try {
> in.close();
> } catch (IOException e1) {
> e1.printStackTrace();
> }
>
> DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
> KShortestPaths<String, DefaultWeightedEdge> kPaths = new
> KShortestPaths<String, DefaultWeightedEdge>(
> graph, graph.getEdgeSource(src), 5);
> List<GraphPath<String,**DefaultWeightedEdge>> paths = null;
>
> try {
> paths = kPaths.getPaths(graph.**getEdgeTarget(src));
> for (GraphPath<String, DefaultWeightedEdge> path : paths) {
> for (DefaultWeightedEdge edge : path.getEdgeList()) {
> System.out.print("<" + graph.getEdgeSource(edge) + "\t"
> + graph.getEdgeTarget(edge) + "\t" + edge +
> ">\t");
> }
> System.out.println(": " + path.getWeight());
> }
> } catch (IllegalArgumentException e) {
> e.printStackTrace();
> }
> }
> }
>
> [/code]
>
> I tried different edges, and directed and undirected graphs. Same result.
> If anyone has a clue what might be going on here, I'd very much appreciate
> help.
>
>
> Sebastian
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
|
