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