Re: [Boost-bugs] [Boost C++ Libraries] #7341: Vector subscript out of range exception when calling weighted_core_numbers

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #7341: Vector subscript out of range exception when calling weighted_core_numbers
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2012-09-10 14:08:45

#7341: Vector subscript out of range exception when calling weighted_core_numbers
-------------------------------------------------+--------------------------
  Reporter:  Ian Robertson <irober67@…>          |       Owner:  jewillco                           
      Type:  Bugs                                |      Status:  reopened                           
 Milestone:  To Be Determined                    |   Component:  graph                              
   Version:  Boost 1.51.0                        |    Severity:  Showstopper                        
Resolution:                                      |    Keywords:  weighted_core_numbers mutable_queue
-------------------------------------------------+--------------------------
Changes (by Ian Robertson <irober67@…>):

  * status:  closed => reopened
  * resolution:  fixed =>

Comment:

 Replying to [comment:2 jewillco]:
 > Could you please check the version that I just committed?  One thing
 that I changed was to only update elements in the heap when they were
 already there (i.e., not re-push elements that had been removed).  Doing
 otherwise seemed to cause an infinite loop, but I don't know the algorithm
 well enough to tell if what I did was correct.

 Thank you for the fix - dropping the mutable_queue in favour of the
 d_ary_heap has fixed the subscript-out-of-range problem. Unfortunately
 this has now exposed a bug in the logic of the weighted cores algorithm
 itself. The core numbers coming back from the test network I submitted are
 not correct.

 I have taken a look at the code, and the problem seems to lie in the
 vertex priority adjustment in procedure {{{core_numbers_impl(Graph& g,
 CoreMap c, EdgeWeightMap wm, MutableQueue& Q, Visitor vis)}}}. The coded
 adjustment is incorrectly allowing the priority (core number) of vertices
 adjacent to the current vertex to fall below that of the current vertex
 itself. The correct adjustment formula is given in line 4.3.1 of Algorithm
 3.2 on page 6 of the generalised cores paper by Batagelj and Zaversnik
 [http://vlado.fmf.uni-lj.si/pub/preprint/imfm0799.pdf].

 I am enclosing a corrected version of the procedure, which fixes the
 problem.  The required correction lies on the line immediately preceding
 the Q.update(u) call. The modified procedure also eliminates the redundant
 test for graph/queue membership, which is now tested explicitly and
 robustly through the Q.contains(u) call.


 {{{
 // the version for weighted graphs is a little different
 template <typename Graph, typename CoreMap,
           typename EdgeWeightMap, typename MutableQueue,
           typename Visitor>
 typename property_traits<CoreMap>::value_type
 core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm, MutableQueue& Q,
 Visitor vis)
 {
    typename property_traits<CoreMap>::value_type v_cn = 0;
    typedef typename graph_traits<Graph>::vertex_descriptor vertex;
    while (!Q.empty())
    {
       // remove v from the Q, and then adjust
       // the core numbers of its successors
       vertex v = Q.top();
       vis.examine_vertex(v,g);
       Q.pop();
       v_cn = get(c,v);
       typename graph_traits<Graph>::out_edge_iterator oi,oi_end;
       for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi)
       {
          vis.examine_edge(*oi,g);
          vertex u = target(*oi,g);
          // if the Q contains u, then u is still in the graph
          if (Q.contains(u))
          {
             // remove the edge, and adjust the core-number for u
             put(c, u, std::max(v_cn, get(c, u) - get(wm, *oi)));
             Q.update(u);
          }
       }
       vis.finish_vertex(v,g);
    }
    return (v_cn);
 }

 }}}

 I think this is a good fix, but if you would like more supporting material
 or test examples, I would be happy to provide them.

 Thank you.
 Ian Robertson

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