A custom priority queue for the blossom algorithm, based on the PrioritizedMapQueue. It uses a std::unordered_map to store the handles, handles merge operations correctly, can iterate over its elements and offers a remove() function. More...

#include <ogdf/graphalg/matching_blossom/PQ.h>

Inheritance diagram for ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >:

Public Member Functions
	BlossomPQ ()

void	clear ()
	Removes all elements from this queue. More...

bool	contains (const E &element) const
	Returns whether this queue contains that key. More...

void	decrease (const E &element, const TWeight priority)
	Decreases the priority of the given element. More...

void	merge (ThisQueue &other)
	Merge this Priority Queue with another one. The other queue is cleared afterwards. More...

void	pop ()
	Removes the topmost element from the queue. More...

TWeight	priority (const E &element) const

void	push (const E &element, const TWeight priority)
	Adds a new element to the queue. More...

void	remove (const E &e)
	Remove `e` from the queue by decreasing its priority to the minimum. `e` must be present in the queue; if that's not guaranteed, use tryRemove() instead. More...

Public Member Functions inherited from ogdf::pq_internal::PrioritizedQueue< E, P, C, Impl >
	PrioritizedQueue (const C &cmp=C(), int initialSize=128)

void	decrease (Handle pos, const P &priority)

Handle	push (const E &element, const P &priority)
	Pushes a new element with the respective priority to the queue. More...

const E &	topElement () const
	Returns the topmost element in the queue. More...

const P &	topPriority () const
	Returns the priority of the topmost element in this queue. More...

Public Member Functions inherited from ogdf::PriorityQueue< T, C, Impl >
	PriorityQueue (const C &cmp=C(), int initialSize=128)
	Creates empty priority queue. More...

	PriorityQueue (const PriorityQueue &other)
	Copy constructor. More...

template<class InputIt >
	PriorityQueue (InputIt first, InputIt last, const C &cmp=C())
	Creates priority queue with contents of the given range. More...

	PriorityQueue (PriorityQueue &&other)
	Move constructor. More...

	PriorityQueue (std::initializer_list< value_type > init, const C &cmp=C())
	Creates priority queue with contents of the given initializer list. More...

	~PriorityQueue ()
	Destroys the underlying data structure. More...

void	clear ()
	Removes all the entries from the queue. More...

const C &	comparator () const
	Returns the comparator used for ordering elements. More...

void	decrease (handle pos, const T &value)
	Decreases value of the element specified by `handle` to `value`. More...

bool	empty () const
	Checks whether the queue is empty. More...

void	merge (PriorityQueue &other)
	Merges in enqueued values of `other` queue. More...

PriorityQueue &	operator= (PriorityQueue other)
	Copy and move assignment. More...

PriorityQueue &	operator= (std::initializer_list< value_type > ilist)
	Assigns the priority queue contents of the given initializer list. More...

void	pop ()
	Removes the top element from the heap. More...

handle	push (const value_type &value)
	Inserts a new element with given `value` into the queue. More...

template<class InputIt >
void	push (InputIt first, InputIt last)
	Inserts new elements specified by the given range. More...

void	push (std::initializer_list< value_type > ilist)
	Inserts new elements specified by the given initializer list. More...

size_type	size () const
	Returns the number of enqueued elements. More...

void	swap (PriorityQueue &other)
	Swaps the contents. More...

const T &	top () const
	Returns reference to the top element in the queue. More...

const T &	value (handle pos) const
	Returns the priority of that handle. More...

Public Member Functions inherited from ogdf::matching_blossom::BaseIteratorContainer< Iterator, Key, Value >
	BaseIteratorContainer (std::unordered_map< Key, Value > &map)

iterator	begin ()

iterator	end ()

size_t	size ()

Protected Types
using	Handle = typename SuperQueue::Handle

using	SuperQueue = PrioritizedQueue< E, TWeight, C, Impl >

using	ThisQueue = BlossomPQ< E, TWeight, C, Impl >

Protected Attributes
std::unordered_map< E, Handle >	m_handles

Additional Inherited Members
Public Types inherited from ogdf::pq_internal::PrioritizedQueue< E, P, C, Impl >
using	Handle = typename SuperQueue::handle
	The type of handle for accessing the elements of this queue. More...

Public Types inherited from ogdf::PriorityQueue< T, C, Impl >
using	const_reference = const value_type &

using	handle = typename SpecImpl::Handle

using	reference = value_type &

using	size_type = std::size_t

using	value_type = T

Detailed Description

template<typename E, typename TWeight, typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>
class ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >

A custom priority queue for the blossom algorithm, based on the PrioritizedMapQueue. It uses a std::unordered_map to store the handles, handles merge operations correctly, can iterate over its elements and offers a remove() function.

Definition at line 51 of file PQ.h.

Member Typedef Documentation

◆ Handle

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

using ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::Handle = typename SuperQueue::Handle

protected

Definition at line 57 of file PQ.h.

◆ SuperQueue

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

using ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::SuperQueue = PrioritizedQueue<E, TWeight, C, Impl>

protected

Definition at line 56 of file PQ.h.

◆ ThisQueue

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

using ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::ThisQueue = BlossomPQ<E, TWeight, C, Impl>

protected

Definition at line 55 of file PQ.h.

Constructor & Destructor Documentation

◆ BlossomPQ()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::BlossomPQ ( )

inline

Definition at line 62 of file PQ.h.

Member Function Documentation

◆ clear()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

void ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::clear ( )

inline

Removes all elements from this queue.

Definition at line 112 of file PQ.h.

◆ contains()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

bool ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::contains ( const E & element ) const

inline

Returns whether this queue contains that key.

Definition at line 65 of file PQ.h.

◆ decrease()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

void ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::decrease	(	const E &	element,
		const TWeight	priority
	)

inline

Decreases the priority of the given element.

Note that the behaviour is undefined if the key is not present or the given priority is greater than the former one.

Definition at line 97 of file PQ.h.

◆ merge()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

void ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::merge ( ThisQueue & other )

inline

Merge this Priority Queue with another one. The other queue is cleared afterwards.

Definition at line 103 of file PQ.h.

◆ pop()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

void ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::pop ( )

inline

Removes the topmost element from the queue.

Definition at line 87 of file PQ.h.

◆ priority()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

TWeight ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::priority ( const E & element ) const

inline

Definition at line 71 of file PQ.h.

◆ push()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

void ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::push	(	const E &	element,
		const TWeight	priority
	)

inline

Adds a new element to the queue.

Note that the behaviour is undefined if the key is already present.

Definition at line 81 of file PQ.h.

◆ remove()

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

void ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::remove ( const E & e )

inline

Remove e from the queue by decreasing its priority to the minimum. e must be present in the queue; if that's not guaranteed, use tryRemove() instead.

Definition at line 119 of file PQ.h.

Member Data Documentation

◆ m_handles

template<typename E , typename TWeight , typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>

std::unordered_map<E, Handle> ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >::m_handles

protected

Definition at line 59 of file PQ.h.

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

include/ogdf/graphalg/matching_blossom/PQ.h

OpenGraph DrawingFramework

Public Member Functions

Protected Types

Protected Attributes

Additional Inherited Members

Detailed Description

template<typename E, typename TWeight, typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap> class ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >

Member Typedef Documentation

◆ Handle

◆ SuperQueue

◆ ThisQueue

Constructor & Destructor Documentation

◆ BlossomPQ()

Member Function Documentation

◆ clear()

◆ contains()

◆ decrease()

◆ merge()

◆ pop()

◆ priority()

◆ push()

◆ remove()

Member Data Documentation

◆ m_handles

Open
Graph Drawing
Framework

template<typename E, typename TWeight, typename C = std::less<TWeight>, template< typename, class > class Impl = PairingHeap>
class ogdf::matching_blossom::BlossomPQ< E, TWeight, C, Impl >