pqueue_boost.h

用改进的数据结构快速计算复杂网络的社区划分

/*-
 * Copyright (c) 2008, Alexandre P. Francisco <[e-mail]>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef _PQUEUE_BOOST_H_
#define _PQUEUE_BOOST_H_

#include <boost/pending/indirect_cmp.hpp>
#include <boost/pending/relaxed_heap.hpp>

using namespace std;
using namespace boost;

/* Randomized greater. */
template <class _Tp>
struct rand_greater : public binary_function<_Tp, _Tp, bool>
{
	bool
	operator()(const _Tp& __x, const _Tp& __y) const
	{

		if (__x > __y)
			return true;

		if (__x < __y)
			return false;

#ifdef _RAND_CMP
#define rand_p() (((double) rand()) / RAND_MAX)

	return (rand_p() > 0.5) ? true : false;
#else
	return true;
#endif /* _RAND_CMP */
	}
};

/*
 * Relaxed heaps allow all usual priority queue operations with worst
 * case constant time, except for delete which takes O(log N) time.
 * Here is used an implementation of relaxed heaps provided by the 
 * boost graph library (check the includes above).
 */
typedef indirect_cmp< double *, rand_greater< double > > cmp_t;
typedef relaxed_heap< int, cmp_t > _pqueue;
typedef _pqueue pqueue;

#define pqueue_new(size, k, ignored)                                           \
	new _pqueue(size + 1, cmp_t(k - 1, rand_greater< double >()))

#define pqueue_free(qq) do {                                                   \
	delete qq;                                                             \
} while (0)

#define pqueue_push(qq, ii)   (*qq).push(ii + 1)

#define pqueue_update(qq, ii) (*qq).update(ii + 1)

#define pqueue_pop(qq)        (*qq).pop()

#define pqueue_top(qq)        ((*qq).top() - 1)

#define pqueue_empty(qq)      (*qq).empty()

#endif /* _PQUEUE_BOOST_H_ */