Modify

Ticket #7341 (reopened Bugs)

Opened 20 months ago

Last modified 20 months ago

Vector subscript out of range exception when calling weighted_core_numbers

Reported by: Ian Robertson <irober67@…> Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost 1.51.0 Severity: Showstopper
Keywords: weighted_core_numbers mutable_queue Cc:

Description

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.

Attachments

weighted_core_numbers_bug.txt Download (1.5 KB) - added by Ian Robertson <irober67@…> 20 months ago.
Short self-contained test program

Change History

Changed 20 months ago by Ian Robertson <irober67@…>

Short self-contained test program

comment:1 Changed 20 months ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

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

comment:2 follow-up: ↓ 3 Changed 20 months ago by 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.

comment:3 in reply to: ↑ 2 Changed 20 months ago by Ian Robertson <irober67@…>

  • Status changed from closed to reopened
  • Resolution fixed deleted

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

comment:4 Changed 20 months ago by jewillco

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.

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as reopened
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.