Re: [Boost-bugs] [Boost C++ Libraries] #11838: contribution: Yen k-shortest paths

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11838: contribution: Yen k-shortest paths
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-06-28 18:26:25

#11838: contribution: Yen k-shortest paths
---------------------------------------+----------------------------
  Reporter:  Irek Szcześniak <irek@…>  |      Owner:  jewillco
      Type:  Library Submissions       |     Status:  new
 Milestone:  To Be Determined          |  Component:  graph
   Version:  Boost 1.57.0              |   Severity:  Not Applicable
Resolution:                            |   Keywords:
---------------------------------------+----------------------------

Comment (by anonymous):

 Hi again. Sorry, I think that there is a bug in yen_ksp.2.hpp. Basically I
 tested your program with a graph in which several composite paths have
 equal lengths, and where I could easily check by hand all the KSPs. What
 happens is that previously already identified KSPs reappear somewhere down
 the list of shortest paths. Of course they were all properly ordered and
 weights were correctly computed.

 Below are the relevant snippets for the reproduction of the issue, for a
 KSP from O to D, and the weight-path output. As you can see, some repeated
 paths occur, which should not happen.

 Best,
 Rytis

 {{{#!c
   Vertex X = *i++;
   Vertex O = *i++;
   Vertex D = *i++;
   Vertex L = *i++;
   Vertex R = *i;

   tie(ab, ba) = aue(g, O, X, 16);
   tie(ae, ea) = aue(g, X, D, 4 );
   tie(ac, ca) = aue(g, X, L, 25);
   tie(be, eb) = aue(g, X, R, 9 );
   tie(cd1, dc1) = aue(g, O, R, 25);
   tie(cd2, dc2) = aue(g, R, D, 13);
   tie(ce, ec)   = aue(g, D, L, 29);
   tie(aa,bb)   = aue(g, L, O, 41);
 }}}

 {{{
 20.000  O -- X -- D
 38.000  O -- R -- D
 38.000  O -- X -- R -- D
 38.000  O -- R -- X -- D
 70.000  O -- L -- D
 70.000  O -- L -- D
 70.000  O -- X -- L -- D
 70.000  O -- L -- D
 70.000  O -- L -- X -- D
 70.000  O -- L -- X -- D
 70.000  O -- L -- X -- D
 88.000  O -- R -- X -- L -- D
 88.000  O -- L -- X -- R -- D
 88.000  O -- L -- X -- R -- D
 88.000  O -- L -- X -- R -- D
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11838#comment:8>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.