Ticket #7341 (reopened Bugs)
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
Change History
Changed 5 years ago by Ian Robertson <irober67@…>
- Attachment weighted_core_numbers_bug.txt added
comment:2 follow-up: ↓ 3 Changed 5 years 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 5 years 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 5 years 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.
Short self-contained test program