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