Re: [jgrapht-users] JGraphT Enquiry: KShortestPaths Bug?

[H.N. de R. <hnr...@gr...>]

On Thu, Jun 21, 2012 at 01:05:33PM -0700, John Sichi wrote:

Hello Ron,

the change you describe below is not a good fix: It hides the problem rather
than avoiding or solving it. Could you provide a small reproduction for the
error? A single method that creates the 'Hillary' graph from the article and
calls the kshortestpath method on it will do.

Thanks,
   Ernst

> On Mon, Jun 18, 2012 at 2:13 AM, Genliang Guan
> <gen...@sy...> wrote:
> > Dear John,
> >
> > This is Ron Guan, studying at School of IT, University of Sydney.
> >
> > I am using the fantastic JGraphT library, or more specifically the
> > KShortestPaths, to implement the algorithm proposed at "Multi-Sentence
> > Compression: Finding Shortest Paths inWord Graphs"
> >  (http://dejanseo.com.au/research/google/36338.pdf). You may just look at
> > the graph in the paper to understand the ideas.
> >
> > The included testing cases work fine, but when I run the examples in the
> > paper (Hillary sentences), it gives me this error:
> > graph must contain the start vertex: visit
> >
> > I tried to fix it by modifying ConnectivityInspector.pathExists().
> >
> > Originally, it was
> >
> > --------------------------------------------------------------------------------------------------------------
> >     Set<V> sourceSet =  connectedSetOf(sourceVertex);
> >         return sourceSet.contains(targetVertex);
> > --------------------------------------------------------------------------------------------------------------
> >
> > Then I added a few lines to catch the exception:
> >
> > ========================================================
> >         //ron
> >     Set<V> sourceSet = null;
> >     try{
> >     sourceSet = connectedSetOf(sourceVertex);
> >     }
> >     catch(IllegalArgumentException e)
> >     {
> >     return false;
> >     }
> >
> >         return sourceSet.contains(targetVertex);
> > ========================================================
> >
> > This seems fix the problem and gives correct output, but I am not sure what
> > really happens deep in the algorithm and whether it is a good fix.
> >
> > Could you help on this issue?  Many thanks!

-- 
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org