Vector subscript out of range exception when calling weighted_core_numbers

[Ian Robertson <irober67@…>]

I get a vector subscript out of range exception when calling the weighted_core_numbers function in the boost graph library. The exception is actually thrown from within the mutable_queue::update function, but I can't tell if the error is in mutable_queue or in weighted_core_numbers.

The attached test program is sufficient to show the problem. The test network is taken from Figure 1 of the Batagelj-Zaversnik paper (​http://vlado.fmf.uni-lj.si/pub/networks/doc/cores/cores.pdf), with random integer weights of 1, 2, or 3 added to each edge.

[Ian Robertson <irober67@…>]

Short self-contained test program

[Jeremiah Willcock]

(In [80421]) Changed core_numbers to use d_ary_heap and only update queue elements that are in the queue; fixes #7341

[Jeremiah Willcock]

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.

[Ian Robertson <irober67@…>]

Replying to 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

[Jeremiah Willcock]

Are you fine with releasing that code under the Boost license? Could you please attach a patch that makes the change that you want plus adds your name to the author list at the top of the file (if you think your changes are major enough for that)? Thank you.