Help on using boost relaxed heap

Question

Hello all,

I'm implementing a few graph algorithms at the moment and am wanting a container with the complexity of a fibonacci heap or a relaxed heap (specifically I want at least O(logN) for push and pop and O(1) for reduce_key).

I'm not keen on implementing this myself if at all possible (development and testing overhead and time) and I notice that the boost graph library references a couple of likely looking datastructures in the pending directory. The relaxed heap in relaxed_heap.hpp looks the ticket, but I can't quite work out how to use it. It has the following public functions (precised a little for clarity):

void push(const value_type& x);
value_type& top();
void pop();

Which are clear enough and implement my desired push and pop. Additionally there are:

void update(const value_type& x);
void remove(const value_type& x);

I'm presuming that I can implement a reduce_key using update but I'm not clear how. My particular issue is that I assume the value is copied upon calling push. What I feel I need is a pointer to the copy of the value in the heap so that I can modify it by reference and then call update to have it shuffled back to where it belongs. However such a pointer does not seem to be available?

Anyone with experience of relaxed heaps in general, or boost relaxed heaps in particular willing to put me out of my misery with an explanation or a nice code snippet?

Thanks,

Alex

Answer 1

Alex, if you checkout/download/browse boost library, there's a libs/graph/test directory. One of the tests is relaxed_heap_test.cpp which seems to have coverage of the update member function.

-s-