---

Buckets< nodesPerBucket > Class Template 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 <buckets.h>

List of all members.

Public Types
typedef int	BucketID
Public Methods
	Buckets (EdgeVector< Edge > &graph, MST &result, BucketID noOfBuckets, 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 appropriate external bucket or to the appropriate internal bucket if the edge belongs to the external bucket which is processed at the moment.
Static Public Methods
BucketID	noOfExtBuckets (NodeCount noOfNodes, NodeCount noOfNodesInIntMem)
	Computes the number of external buckets that are needed.
Private Types
typedef stxxl::STACK_GENERATOR< RelabeledEdge, stxxl::external, stxxl::grow_shrink2, DS_EXT_PAGE_SIZE, DS_EXT_BLOCK_SIZE >::result	EdgesOfSeveralNodes
	The type of an external bucket which contains the edges of several nodes.
typedef REWS_SparingStack< DS_INT_EDGES_PER_BLOCK, DS_INT_NO_OF_BLOCKS >	EdgesOfOneNode
	The type of an internal bucket which contains the edges of one node.
typedef CommonPoolOfBlocks< RelabeledEdgeWithoutSource, DS_INT_EDGES_PER_BLOCK, DS_INT_NO_OF_BLOCKS >	PoolEdgesOfOneNode
	The type of the common pool of the internal buckets.
Private Methods
void	initBuckets ()
	Initializes the external buckets and distributes the edges to the external buckets.
void	reduceNodes ()
	Reduces the number of nodes.
BucketID	bucketID (NodeID nodeID) const
	Returns the ID of the bucket which contains the edges of the given node.
void	addToExternalBucket (const RelabeledEdge &edge)
	Adds the given edge to the appropriate external bucket.
void	addToExternalBucket (const RelabeledEdge &edge, BucketID newBucketID)
	Adds the given edge to the bucket which is specified by newBucketID.
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.
std::vector< EdgesOfSeveralNodes * >	_extBuckets
	The external buckets.
stxxl::prefetch_pool< EdgesOfSeveralNodes::block_type >	_prefetchPool
	The prefetch pool that is used by the external buckets.
stxxl::write_pool< EdgesOfSeveralNodes::block_type >	_writePool
	The write pool that is used by the external buckets.
EdgesOfOneNode	_intBuckets [nodesPerBucket]
	The internal buckets.
NodeID	_firstNodeIDofCurrentBucket
	The identifier of the first node in the current external bucket will be used to compute the internal bucket index of a node.

---

Detailed Description

template<NodeCount nodesPerBucket = 1>
class Buckets< nodesPerBucket >

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 several buckets.

template parameter: The number of nodes per bucket. This value doesn't apply to the first bucket, because it contains the edges of the first "_noOfNodesInIntMem" nodes.

Definition at line 36 of file buckets.h.

---

Constructor & Destructor Documentation

template<NodeCount nodesPerBucket = 1> Buckets< nodesPerBucket >::Buckets (  EdgeVector< Edge > &    graph, MST &    result, BucketID    noOfBuckets, 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 noOfBuckets  the number of external buckets which should be used noOfNodesInIntMem  the number of nodes which fit in internal memory Definition at line 70 of file buckets.h. References Buckets< nodesPerBucket >::_extBuckets, Buckets< nodesPerBucket >::_graph, Buckets< nodesPerBucket >::_noOfNodesInIntMem, Buckets< nodesPerBucket >::_prefetchPool, Buckets< nodesPerBucket >::_result, Buckets< nodesPerBucket >::_writePool, Buckets< nodesPerBucket >::initBuckets(), and Buckets< nodesPerBucket >::reduceNodes().

---

Member Function Documentation

template<NodeCount nodesPerBucket> Buckets< nodesPerBucket >::BucketID Buckets< nodesPerBucket >::bucketID (  NodeID    nodeID )  const [inline, private]

Returns the ID of the bucket which contains the edges of the given node. The first external bucket has the ID -1 because it is a special case. The second bucket is the first element of _extBuckets and has the ID 0 and so on. Definition at line 170 of file buckets.h. References Buckets< nodesPerBucket >::_noOfNodesInIntMem. Referenced by Buckets< nodesPerBucket >::add(), Buckets< nodesPerBucket >::addToExternalBucket(), and Buckets< nodesPerBucket >::initBuckets().

template<NodeCount nodesPerBucket> void Buckets< nodesPerBucket >::reduceNodes (    )  [private]

Reduces the number of nodes. Only the first bucket "survives". Definition at line 81 of file buckets.cpp. References Buckets< nodesPerBucket >::_extBuckets, Buckets< nodesPerBucket >::_firstExtBucket, Buckets< nodesPerBucket >::_firstNodeIDofCurrentBucket, Buckets< nodesPerBucket >::_intBuckets, Buckets< nodesPerBucket >::_noOfNodesInIntMem, Buckets< nodesPerBucket >::_result, Buckets< nodesPerBucket >::add(), REWS_SparingStack< DS_INT_EDGES_PER_BLOCK, DS_INT_NO_OF_BLOCKS >::determineMinEdge(), Buckets< nodesPerBucket >::EdgesOfSeveralNodes, SparingStack< RelabeledEdgeWithoutSource, elementsPerBlock, noOfBlocks >::empty(), CommonPoolOfBlocks< value_type, elementsPerBlock, noOfBlocks >::increaseReserveMemory(), EdgeVector< RelabeledEdge >::noOfEdges(), EdgeVector< RelabeledEdge >::noOfNodes(), Buckets< nodesPerBucket >::PoolEdgesOfOneNode, SparingStack< RelabeledEdgeWithoutSource, elementsPerBlock, noOfBlocks >::pop(), SparingStack< RelabeledEdgeWithoutSource, elementsPerBlock, noOfBlocks >::setPool(), SparingStack< RelabeledEdgeWithoutSource, elementsPerBlock, noOfBlocks >::size(), EdgeWithoutSource::target(), and SparingStack< RelabeledEdgeWithoutSource, elementsPerBlock, noOfBlocks >::top(). Referenced by Buckets< nodesPerBucket >::Buckets().

---

Member Data Documentation

template<NodeCount nodesPerBucket = 1> std::vector<EdgesOfSeveralNodes*> Buckets< nodesPerBucket >::_extBuckets [private]

The external buckets. Each bucket contains the edges of several nodes. Definition at line 113 of file buckets.h. Referenced by Buckets< nodesPerBucket >::addToExternalBucket(), Buckets< nodesPerBucket >::Buckets(), Buckets< nodesPerBucket >::initBuckets(), and Buckets< nodesPerBucket >::reduceNodes().

template<NodeCount nodesPerBucket = 1> EdgesOfOneNode Buckets< nodesPerBucket >::_intBuckets[nodesPerBucket] [private]

The internal buckets. Each bucket contains the edges of one node. Definition at line 125 of file buckets.h. Referenced by Buckets< nodesPerBucket >::add(), and Buckets< nodesPerBucket >::reduceNodes().

---

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

• buckets.h
• buckets.cpp

---