---

PQueue Class Reference

Represents an algorithm for reducing the number of nodes of a graph (in order to compute a minimum spanning tree) and the required data structures. More...

#include <pQueue.h>

List of all members.

Public Methods
	PQueue (EdgeVector< Edge > &graph, MST &result, NodeCount noOfNodesInIntMem)
	Reduces the number of nodes of a graph (in order to compute a minimum spanning tree).
InternalMemoryBucket *	getIntMemBucket ()
	Returns a pointer to the first external bucket which contains the edges of the nodes which fit in internal memory.
void	add (const RelabeledEdge &edge)
	Adds the given edge to the first external bucket or to the priority queue depending on the source vertex ID.
Private Types
typedef stxxl::PRIORITY_QUEUE_GENERATOR< RelabeledEdge, SourceWeightOrdering< RelabeledEdge >, DS_PQUEUE_INTERNAL_MEMORY, DS_PQUEUE_MAX_SIZE >::result	PriorityQueue
	The type of the priority queue that is used during the node reduction phase.
Private Methods
void	initPQueue ()
	Initializes the priority queue and distributes the edges to the first external bucket and the priority queue.
void	reduceNodes ()
	Reduces the number of nodes.
Private Attributes
EdgeVector< Edge > &	_graph
	Reference to the given graph.
MST &	_result
	Reference to a MST object which stores the result.
NodeCount	_noOfNodesInIntMem
	The number of nodes which fit in internal memory.
InternalMemoryBucket *	_firstExtBucket
	The first external bucket which contains the edges of the nodes which fit in internal memory.
stxxl::prefetch_pool< PriorityQueue::block_type >	_prefetchPool
	The prefetch pool that is used by the priority queue.
stxxl::write_pool< PriorityQueue::block_type >	_writePool
	The write pool that is used by the priority queue.
PriorityQueue	_pqueue
	The priority queue.

---

Detailed Description

Represents an algorithm for reducing the number of nodes of a graph (in order to compute a minimum spanning tree) and the required data structures.

This implementation uses an external priority queue.

Definition at line 27 of file pQueue.h.

---

Constructor & Destructor Documentation

PQueue::PQueue (  EdgeVector< Edge > &    graph, MST &    result, NodeCount    noOfNodesInIntMem )  [inline]

Reduces the number of nodes of a graph (in order to compute a minimum spanning tree). Parameters: graph  a reference to an EdgeVector which represents the graph result  a reference to a MST object which stores the result noOfNodesInIntMem  the number of nodes which fit in internal memory Definition at line 44 of file pQueue.h. References _graph, _noOfNodesInIntMem, _pqueue, _prefetchPool, _result, _writePool, initPQueue(), and reduceNodes().

---

Member Function Documentation

void PQueue::reduceNodes (    )  [private]

Reduces the number of nodes. Only the first external bucket "survives". Definition at line 62 of file pQueue.cpp. References _noOfNodesInIntMem, _pqueue, _result, add(), MST::add(), Edge::source(), and EdgeWithoutSource::target(). Referenced by PQueue().

---

The documentation for this class was generated from the following files:

• pQueue.h
• pQueue.cpp

---