attachment set

Thu, 06 Sep 2012 15:07:52 GMT

attachment → weighted_core_numbers_bug.txt

Short self-contained test program

status changed; resolution set

Jeremiah Willcock — Thu, 06 Sep 2012 15:31:46 GMT

status new → closed
resolution → fixed

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

Jeremiah Willcock — Thu, 06 Sep 2012 15:33:08 GMT

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.

status changed; resolution deleted

Mon, 10 Sep 2012 14:08:45 GMT

status closed → reopened
resolution fixed

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 — Mon, 10 Sep 2012 14:12:29 GMT

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.

Boost C++ Libraries: Ticket #7341: Vector subscript out of range exception when calling weighted_core_numbers

attachment set

status changed; resolution set

status changed; resolution deleted