---

DuplicatesRemover< SuperContainer > Class Template Reference

A container which can be used as an 'intermediate station' in order to remove multiple edges. More...

#include <duplicatesRemover.h>

List of all members.

Public Methods
	DuplicatesRemover (SuperContainer *superContainer)
	Creates a DuplicatesRemover.
void	insert (const RelabeledEdgeWithoutSource &edge, NodeID source)
	Adds an edge to the container.
void	clear (NodeID source)
	Clears the container.
Private Types
typedef std::pair< RelabeledEdgeWithoutSource, int >	HashMapElement
	The type of a hashMap-element.
Private Methods
int	hashFunction (NodeID x) const
	Returns the hash value for the given node ID.
int	find (NodeID x) const
	Returns the position of an edge with the given node ID in the hashMap.
void	clearLocal (NodeID x)
	Removes entries from the hashMap beginning with the hash value of the given node ID and ending with the first empty entry which is found.
bool	empty (int index) const
	Returns true iff the given position in the hashMap is empty.
Private Attributes
RelabeledEdgeWithoutSource	_edges [_maxSize]
	This array contains all edges without vacancies.
HashMapElement	_hashMap [_hashMapSize]
	The hashMap which contains the edges.
EdgeCount	_size
	The number of edges which are stored in this container.
SuperContainer *	_superContainer
	A pointer to the super container, i.e.
Static Private Attributes
const EdgeCount	_maxSize = 1024
	The capacity of the container.
const EdgeCount	_hashMapSize = 2 * _maxSize
	The size of the hash map.

---

Detailed Description

template<typename SuperContainer>
class DuplicatesRemover< SuperContainer >

A container which can be used as an 'intermediate station' in order to remove multiple edges.

If there is more than one edge with the same target node (the source node is always the same during one pass), only the edge with minimum weight is preserved. If the capacity of the container is exhausted, further edges which can't be stored are output directly.

Definition at line 23 of file duplicatesRemover.h.

---

Member Typedef Documentation

template<typename SuperContainer> typedef std::pair<RelabeledEdgeWithoutSource, int> DuplicatesRemover< SuperContainer >::HashMapElement [private]

The type of a hashMap-element. The first component stores the edge, the second the index in the array '_edges'. Definition at line 93 of file duplicatesRemover.h. Referenced by DuplicatesRemover< SuperContainer >::insert().

---

Constructor & Destructor Documentation

template<typename SuperContainer> DuplicatesRemover< SuperContainer >::DuplicatesRemover (  SuperContainer *    superContainer )  [inline]

Creates a DuplicatesRemover. Parameters: superContainer  a pointer to the super container, i.e. the container that uses this DuplicatesRemover (either a Buckets or a PQueue object). This is required in order to be able to put the edges to the super container when the capacity of this container is exhausted or when this container is cleared. Definition at line 35 of file duplicatesRemover.h. References DuplicatesRemover< SuperContainer >::_size, and DuplicatesRemover< SuperContainer >::_superContainer.

---

Member Function Documentation

template<typename SuperContainer> void DuplicatesRemover< SuperContainer >::clear (  NodeID    source )  [inline]

Clears the container. The edges are written to the appropriate buckets. Definition at line 74 of file duplicatesRemover.h. References DuplicatesRemover< SuperContainer >::_edges, DuplicatesRemover< SuperContainer >::_size, DuplicatesRemover< SuperContainer >::_superContainer, and DuplicatesRemover< SuperContainer >::clearLocal().

template<typename SuperContainer> int DuplicatesRemover< SuperContainer >::find (  NodeID    x )  const [inline, private]

Returns the position of an edge with the given node ID in the hashMap. If no appropriate edge is found, the position where such an edge should be stored is returned. Definition at line 127 of file duplicatesRemover.h. References DuplicatesRemover< SuperContainer >::_hashMap, DuplicatesRemover< SuperContainer >::_hashMapSize, DuplicatesRemover< SuperContainer >::empty(), and DuplicatesRemover< SuperContainer >::hashFunction(). Referenced by DuplicatesRemover< SuperContainer >::insert().

template<typename SuperContainer> void DuplicatesRemover< SuperContainer >::insert (  const RelabeledEdgeWithoutSource &    edge, NodeID    source )  [inline]

Adds an edge to the container. If an edge with the same target node is already in the container, the new edge replaces the old one if it has a lower weight, otherwise it is discarded. Definition at line 45 of file duplicatesRemover.h. References DuplicatesRemover< SuperContainer >::_edges, DuplicatesRemover< SuperContainer >::_hashMap, DuplicatesRemover< SuperContainer >::_maxSize, DuplicatesRemover< SuperContainer >::_size, DuplicatesRemover< SuperContainer >::_superContainer, DuplicatesRemover< SuperContainer >::empty(), DuplicatesRemover< SuperContainer >::find(), DuplicatesRemover< SuperContainer >::HashMapElement, and EdgeWithoutSource::target().

---

Member Data Documentation

template<typename SuperContainer> RelabeledEdgeWithoutSource DuplicatesRemover< SuperContainer >::_edges[_maxSize] [private]

This array contains all edges without vacancies. This is useful in order to clear the container without traversing the whole hashMap. Definition at line 100 of file duplicatesRemover.h. Referenced by DuplicatesRemover< SuperContainer >::clear(), and DuplicatesRemover< SuperContainer >::insert().

template<typename SuperContainer> SuperContainer* DuplicatesRemover< SuperContainer >::_superContainer [private]

A pointer to the super container, i.e. the container that uses this DuplicatesRemover (either a Buckets or a PQueue object). This is required in order to be able to put the edges to the super container when the capacity of this container is exhausted or when this container is cleared. Definition at line 115 of file duplicatesRemover.h. Referenced by DuplicatesRemover< SuperContainer >::clear(), DuplicatesRemover< SuperContainer >::DuplicatesRemover(), and DuplicatesRemover< SuperContainer >::insert().

---

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

• duplicatesRemover.h

---