Dynamic arrays indexed with edges. More...

#include <ogdf/basic/EdgeArray.h>

Inheritance diagram for ogdf::EdgeArray< T >:

Public Types
using	const_iterator = internal::GraphArrayConstIterator< EdgeArray< T > >
	The type for edge array const iterators.

using	iterator = internal::GraphArrayIterator< EdgeArray< T > >
	The type for edge array iterators.

using	key_type = edge
	The type for array keys.

using	value_type = T
	The type for array entries.

Public Member Functions
	EdgeArray ()
	Constructs an empty edge array associated with no graph.

	EdgeArray (const EdgeArray< T > &A)
	Constructs an edge array that is a copy of `A`.

	EdgeArray (const Graph &G)
	Constructs an edge array associated with `G`.

	EdgeArray (const Graph &G, const T &x)
	Constructs an edge array associated with `G`.

	EdgeArray (EdgeArray< T > &&A)
	Constructs an edge array containing the elements of `A` (move semantics).

Access methods
These methods provide access to elements, size, and corresponding graph.
bool	valid () const
	Returns true iff the array is associated with a graph.

const Graph *	graphOf () const
	Returns a pointer to the associated graph.

const T &	operator[] (edge e) const
	Returns a reference to the element with index `e`.

T &	operator[] (edge e)
	Returns a reference to the element with index `e`.

const T &	operator() (edge e) const
	Returns a reference to the element with index `e`.

T &	operator() (edge e)
	Returns a reference to the element with index `e`.

const T &	operator[] (adjEntry adj) const
	Returns a reference to the element with index edge of `adj`.

T &	operator[] (adjEntry adj)
	Returns a reference to the element with index edge of `adj`.

const T &	operator() (adjEntry adj) const
	Returns a reference to the element with index edge of `adj`.

T &	operator() (adjEntry adj)
	Returns a reference to the element with index edge of `adj`.

const T &	operator[] (int index) const
	Returns a reference to the element with index `index`.

T &	operator[] (int index)
	Returns a reference to the element with index `index`.

Iterators
These methods return bidirectional iterators to elements in the array.
iterator	begin ()
	Returns an iterator to the first entry in the edge array.

const_iterator	begin () const
	Returns a const iterator to the first entry in the edge array.

const_iterator	cbegin () const
	Returns a const iterator to the first entry in the edge array.

iterator	end ()
	Returns an iterator to one-past-last entry in the edge array.

const_iterator	end () const
	Returns a const iterator to one-past-last entry in the edge array.

const_iterator	cend () const
	Returns a const iterator to one-past-last entry in the edge array.

Initialization and assignment
These methods can be used to reinitialize the array, or to initialize all elements with a given value.
void	init ()
	Reinitializes the array. Associates the array with no graph.

void	init (const Graph &G)
	Reinitializes the array. Associates the array with `G`.

void	init (const Graph &G, const T &x)
	Reinitializes the array. Associates the array with `G`.

void	fill (const T &x)
	Sets all array elements to `x`.

EdgeArray< T > &	operator= (const EdgeArray< T > &a)
	Assignment operator.

EdgeArray< T > &	operator= (EdgeArray< T > &&a)
	Assignment operator (move semantics).

Static Public Member Functions
Helper functions
These methods are mainly intended for internal use.
static key_type	findSuccKey (key_type key)

static key_type	findPredKey (key_type key)

Private Member Functions
virtual void	disconnect ()
	Virtual function called when array is disconnected from the graph.

virtual void	enlargeTable (int newTableSize)
	Virtual function called when table size has to be enlarged.

virtual void	reinit (int initTableSize)
	Virtual function called when table has to be reinitialized.

Private Member Functions inherited from ogdf::Array< T >
	Array ()
	Creates an array with empty index set.

	Array (Array< T, int > &&A)
	Creates an array containing the elements of `A` (move semantics).

	Array (const Array< T, int > &A)
	Creates an array that is a copy of `A`.

	Array (const ArrayBuffer< T, int > &A)
	Creates an array that is a copy of `A`. The array-size is set to be the number of elements (not the capacity) of the buffer.

	Array (int a, int b)
	Creates an array with index set [`a`..`b`].

	Array (int a, int b, const T &x)
	Creates an array with index set [`a`..`b`] and initializes each element with `x`.

	Array (int s)
	Creates an array with index set [0..`s-1`].

	Array (std::initializer_list< T > initList)
	Creates an array containing the elements in the initializer list `initList`.

	~Array ()
	Destruction.

int	low () const
	Returns the minimal array index.

int	high () const
	Returns the maximal array index.

int	size () const
	Returns the size (number of elements) of the array.

bool	empty () const
	Returns `true` iff there are no elements in the array.

const_reference	operator[] (int i) const
	Returns a reference to the element at position `i`.

reference	operator[] (int i)
	Returns a reference to the element at position `i`.

iterator	begin ()
	Returns an iterator to the first element.

const_iterator	begin () const
	Returns a const iterator to the first element.

const_iterator	cbegin () const
	Returns a const iterator to the first element.

iterator	end ()
	Returns an iterator to one past the last element.

const_iterator	end () const
	Returns a const iterator to one past the last element.

const_iterator	cend () const
	Returns a const iterator to one past the last element.

reverse_iterator	rbegin ()
	Returns an reverse iterator to the last element.

const_reverse_iterator	rbegin () const
	Returns a const reverse iterator to the last element.

const_reverse_iterator	crbegin () const
	Returns a const reverse iterator to the last element.

reverse_iterator	rend ()
	Returns an reverse iterator to one before the first element.

const_reverse_iterator	rend () const
	Returns a const reverse iterator to one before the first element.

const_reverse_iterator	crend () const
	Returns a const reverse iterator to one before the first element.

void	init ()
	Reinitializes the array to an array with empty index set.

void	init (int s)
	Reinitializes the array to an array with index set [0..`s-1`].

void	init (int a, int b)
	Reinitializes the array to an array with index set [`a`..`b`].

void	init (int a, int b, const T &x)
	Reinitializes the array to an array with index set [`a`..`b`] and sets all entries to `x`.

void	fill (const T &x)
	Sets all elements to `x`.

void	fill (int i, int j, const T &x)
	Sets elements in the intervall [`i`..`j`] to `x`.

void	grow (int add, const T &x)
	Enlarges the array by `add` elements and sets new elements to `x`.

void	grow (int add)
	Enlarges the array by `add` elements.

void	resize (int newSize, const T &x)
	Resizes (enlarges or shrinks) the array to hold `newSize` elements and sets new elements to `x`.

void	resize (int newSize)
	Resizes (enlarges or shrinks) the array to hold `newSize` elements.

Array< T, int > &	operator= (const Array< T, int > &A)
	Assignment operator.

Array< T, int > &	operator= (Array< T, int > &&A)
	Assignment operator (move semantics).

bool	operator== (const Array< T, int > &L) const
	Equality operator.

bool	operator!= (const Array< T, int > &L) const
	Inequality operator.

void	swap (int i, int j)
	Swaps the elements at position `i` and `j`.

void	permute (int l, int r)
	Randomly permutes the subarray with index set [`l`..`r`].

void	permute ()
	Randomly permutes the array.

void	permute (int l, int r, RNG &rng)
	Randomly permutes the subarray with index set [`l`..`r`] using random number generator `rng`.

void	permute (RNG &rng)
	Randomly permutes the array using random number generator `rng`.

int	binarySearch (const T &e) const
	Performs a binary search for element `e`.

int	binarySearch (int l, int r, const T &e) const
	Performs a binary search for element `e` within the array section [`l`, ..., `r`] .

int	binarySearch (const T &e, const COMPARER &comp) const
	Performs a binary search for element `e` with comparer `comp`.

int	binarySearch (int l, int r, const T &e, const COMPARER &comp) const
	Performs a binary search for element `e` within the array section [`l`, ..., `r`] with comparer `comp`.

int	linearSearch (const T &e) const
	Performs a linear search for element `e`.

int	linearSearch (const T &e, const COMPARER &comp) const
	Performs a linear search for element `e` with comparer `comp`.

void	quicksort ()
	Sorts array using Quicksort.

void	quicksort (int l, int r)
	Sorts subarray with index set [`l`, ..., `r`] using Quicksort.

void	quicksort (const COMPARER &comp)
	Sorts array using Quicksort and a user-defined comparer `comp`.

void	quicksort (int l, int r, const COMPARER &comp)
	Sorts the subarray with index set [`l`, ..., `r`] using Quicksort and a user-defined comparer `comp`.

void	leftShift (ArrayBuffer< int, int > &ind)
	Removes the components listed in `ind` by shifting the remaining components to the left.

void	leftShift (ArrayBuffer< int, int > &ind, const T &val)
	Removes the components listed in `ind` by shifting the remaining components to the left.

Private Attributes
T	m_x
	The default value for array elements.

Additional Inherited Members
Protected Member Functions inherited from ogdf::EdgeArrayBase
	EdgeArrayBase ()
	Initializes an edge array not associated with a graph.

	EdgeArrayBase (const Graph *pG)
	Initializes an edge array associated with `pG`.

	EdgeArrayBase (EdgeArrayBase &base)
	Moves edge array `base` to this edge array.

virtual	~EdgeArrayBase ()

void	moveRegister (EdgeArrayBase &base)
	Moves array registration from `base` to this array.

void	reregister (const Graph *pG)
	Associates the array with a new graph.

Protected Attributes inherited from ogdf::EdgeArrayBase
const Graph *	m_pGraph
	The associated graph.

Private Types inherited from ogdf::Array< T >
using	const_iterator = ArrayConstIterator< T >
	Provides a random-access iterator that can read a const element in an array.

using	const_reference = const T &
	Provides a reference to a const element stored in an array for reading and performing const operations.

using	const_reverse_iterator = ArrayConstReverseIterator< T >
	Provides a reverse random-access iterator that can read a const element in an array.

using	iterator = ArrayIterator< T >
	Provides a random-access iterator that can read or modify any element in an array.

using	reference = T &
	Provides a reference to an element stored in an array.

using	reverse_iterator = ArrayReverseIterator< T >
	Provides a reverse random-access iterator that can read or modify any element in an array.

using	value_type = T
	Represents the data type stored in an array element.

Static Private Attributes inherited from ogdf::Array< T >
static const int	maxSizeInsertionSort
	Threshold used by quicksort() such that insertion sort is called for instances smaller than maxSizeInsertionSort.

Detailed Description

template<class T>
class ogdf::EdgeArray< T >

Dynamic arrays indexed with edges.

Edge arrays represent a mapping from edges to data of type T. They adjust their table size automatically when the graph grows.

Warning: Undefined behavior can occur when the array is used in the left-hand side of an assignment and the observed graph is changed in the right-hand side. To resolve the issue, use:

auto tmp = RHS; LHS = std::move(tmp);

getDoubleFactoredZeroAdjustedMerger
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
Definition multilevelmixer.cpp:36

Template Parameters

T	is the element type.

Definition at line 125 of file EdgeArray.h.

Member Typedef Documentation

◆ const_iterator

template<class T >

using ogdf::EdgeArray< T >::const_iterator = internal::GraphArrayConstIterator<EdgeArray<T> >

The type for edge array const iterators.

Definition at line 137 of file EdgeArray.h.

◆ iterator

template<class T >

using ogdf::EdgeArray< T >::iterator = internal::GraphArrayIterator<EdgeArray<T> >

The type for edge array iterators.

Definition at line 135 of file EdgeArray.h.

◆ key_type

template<class T >

using ogdf::EdgeArray< T >::key_type = edge

The type for array keys.

Definition at line 130 of file EdgeArray.h.

◆ value_type

template<class T >

using ogdf::EdgeArray< T >::value_type = T

The type for array entries.

Definition at line 132 of file EdgeArray.h.

Constructor & Destructor Documentation

◆ EdgeArray() [1/5]

template<class T >

ogdf::EdgeArray< T >::EdgeArray ( )

inline

Constructs an empty edge array associated with no graph.

Definition at line 140 of file EdgeArray.h.

◆ EdgeArray() [2/5]

template<class T >

ogdf::EdgeArray< T >::EdgeArray ( const Graph & G )

inlineexplicit

Constructs an edge array associated with G.

Definition at line 143 of file EdgeArray.h.

◆ EdgeArray() [3/5]

template<class T >

ogdf::EdgeArray< T >::EdgeArray	(	const Graph &	G,
		const T &	x
	)

inline

Constructs an edge array associated with G.

Parameters

G	is the associated graph.
x	is the default value for all array elements.

Definition at line 150 of file EdgeArray.h.

◆ EdgeArray() [4/5]

template<class T >

ogdf::EdgeArray< T >::EdgeArray ( const EdgeArray< T > & A )

inline

Constructs an edge array that is a copy of A.

Associates the array with the same graph as A and copies all elements.

Definition at line 157 of file EdgeArray.h.

◆ EdgeArray() [5/5]

template<class T >

ogdf::EdgeArray< T >::EdgeArray ( EdgeArray< T > && A )

inline

Constructs an edge array containing the elements of A (move semantics).

Edge array A is empty afterwards and not associated with any graph.

Definition at line 163 of file EdgeArray.h.

Member Function Documentation

◆ begin() [1/2]

template<class T >

iterator ogdf::EdgeArray< T >::begin ( )

inline

Returns an iterator to the first entry in the edge array.

If the edge array is empty, a null pointer iterator is returned.

Definition at line 252 of file EdgeArray.h.

◆ begin() [2/2]

template<class T >

const_iterator ogdf::EdgeArray< T >::begin ( ) const

inline

Returns a const iterator to the first entry in the edge array.

If the edge array is empty, a null pointer iterator is returned.

Definition at line 258 of file EdgeArray.h.

◆ cbegin()

template<class T >

const_iterator ogdf::EdgeArray< T >::cbegin ( ) const

inline

Returns a const iterator to the first entry in the edge array.

If the edge array is empty, a null pointer iterator is returned.

Definition at line 264 of file EdgeArray.h.

◆ cend()

template<class T >

const_iterator ogdf::EdgeArray< T >::cend ( ) const

inline

Returns a const iterator to one-past-last entry in the edge array.

This is always a null pointer iterator.

Definition at line 282 of file EdgeArray.h.

◆ disconnect()

template<class T >

virtual void ogdf::EdgeArray< T >::disconnect ( )

inlineprivatevirtual

Virtual function called when array is disconnected from the graph.

Implements ogdf::EdgeArrayBase.

Definition at line 358 of file EdgeArray.h.

◆ end() [1/2]

template<class T >

iterator ogdf::EdgeArray< T >::end ( )

inline

Returns an iterator to one-past-last entry in the edge array.

This is always a null pointer iterator.

Definition at line 270 of file EdgeArray.h.

◆ end() [2/2]

template<class T >

const_iterator ogdf::EdgeArray< T >::end ( ) const

inline

Returns a const iterator to one-past-last entry in the edge array.

This is always a null pointer iterator.

Definition at line 276 of file EdgeArray.h.

◆ enlargeTable()

template<class T >

virtual void ogdf::EdgeArray< T >::enlargeTable ( int newTableSize )

inlineprivatevirtual

Virtual function called when table size has to be enlarged.

Implements ogdf::EdgeArrayBase.

Definition at line 354 of file EdgeArray.h.

◆ fill()

template<class T >

void ogdf::EdgeArray< T >::fill ( const T & x )

inline

Sets all array elements to x.

Definition at line 314 of file EdgeArray.h.

◆ findPredKey()

template<class T >

static key_type ogdf::EdgeArray< T >::findPredKey ( key_type key )

inlinestatic

Definition at line 349 of file EdgeArray.h.

◆ findSuccKey()

template<class T >

static key_type ogdf::EdgeArray< T >::findSuccKey ( key_type key )

inlinestatic

Definition at line 347 of file EdgeArray.h.

◆ graphOf()

template<class T >

const Graph * ogdf::EdgeArray< T >::graphOf ( ) const

inline

Returns a pointer to the associated graph.

Definition at line 175 of file EdgeArray.h.

◆ init() [1/3]

template<class T >

void ogdf::EdgeArray< T >::init ( )

inline

Reinitializes the array. Associates the array with no graph.

Definition at line 292 of file EdgeArray.h.

◆ init() [2/3]

template<class T >

void ogdf::EdgeArray< T >::init ( const Graph & G )

inline

Reinitializes the array. Associates the array with G.

Definition at line 298 of file EdgeArray.h.

◆ init() [3/3]

template<class T >

void ogdf::EdgeArray< T >::init	(	const Graph &	G,
		const T &	x
	)

inline

Reinitializes the array. Associates the array with G.

Parameters

G	is the associated graph.
x	is the default value.

Definition at line 308 of file EdgeArray.h.

◆ operator()() [1/4]

template<class T >

T & ogdf::EdgeArray< T >::operator() ( adjEntry adj )

inline

Returns a reference to the element with index edge of adj.

Definition at line 224 of file EdgeArray.h.

◆ operator()() [2/4]

template<class T >

const T & ogdf::EdgeArray< T >::operator() ( adjEntry adj ) const

inline

Returns a reference to the element with index edge of adj.

Definition at line 218 of file EdgeArray.h.

◆ operator()() [3/4]

template<class T >

T & ogdf::EdgeArray< T >::operator() ( edge e )

inline

Returns a reference to the element with index e.

Definition at line 199 of file EdgeArray.h.

◆ operator()() [4/4]

template<class T >

const T & ogdf::EdgeArray< T >::operator() ( edge e ) const

inline

Returns a reference to the element with index e.

Definition at line 192 of file EdgeArray.h.

◆ operator=() [1/2]

template<class T >

EdgeArray< T > & ogdf::EdgeArray< T >::operator= ( const EdgeArray< T > & a )

inline

Assignment operator.

Definition at line 322 of file EdgeArray.h.

◆ operator=() [2/2]

template<class T >

EdgeArray< T > & ogdf::EdgeArray< T >::operator= ( EdgeArray< T > && a )

inline

Assignment operator (move semantics).

Edge array a is empty afterwards and not associated with any graph.

Definition at line 333 of file EdgeArray.h.

◆ operator[]() [1/6]

template<class T >

T & ogdf::EdgeArray< T >::operator[] ( adjEntry adj )

inline

Returns a reference to the element with index edge of adj.

Definition at line 212 of file EdgeArray.h.

◆ operator[]() [2/6]

template<class T >

const T & ogdf::EdgeArray< T >::operator[] ( adjEntry adj ) const

inline

Returns a reference to the element with index edge of adj.

Definition at line 206 of file EdgeArray.h.

◆ operator[]() [3/6]

template<class T >

T & ogdf::EdgeArray< T >::operator[] ( edge e )

inline

Returns a reference to the element with index e.

Definition at line 185 of file EdgeArray.h.

◆ operator[]() [4/6]

template<class T >

const T & ogdf::EdgeArray< T >::operator[] ( edge e ) const

inline

Returns a reference to the element with index e.

Definition at line 178 of file EdgeArray.h.

◆ operator[]() [5/6]

template<class T >

T & ogdf::EdgeArray< T >::operator[] ( int index )

inline

Returns a reference to the element with index index.

Attention: Make sure that index is a valid index for an edge in the associated graph!

Deprecated:: "Edge arrays should be indexed by an edge, not an integer index."

Definition at line 239 of file EdgeArray.h.

◆ operator[]() [6/6]

template<class T >

const T & ogdf::EdgeArray< T >::operator[] ( int index ) const

inline

Returns a reference to the element with index index.

Attention: Make sure that index is a valid index for an edge in the associated graph!

Deprecated:: "Edge arrays should be indexed by an edge, not an integer index."

Definition at line 233 of file EdgeArray.h.

◆ reinit()

template<class T >

virtual void ogdf::EdgeArray< T >::reinit ( int initTableSize )

inlineprivatevirtual

Virtual function called when table has to be reinitialized.

Implements ogdf::EdgeArrayBase.

Definition at line 356 of file EdgeArray.h.

◆ valid()

template<class T >

bool ogdf::EdgeArray< T >::valid ( ) const

inline

Returns true iff the array is associated with a graph.

Definition at line 172 of file EdgeArray.h.

Member Data Documentation

◆ m_x

template<class T >

T ogdf::EdgeArray< T >::m_x

private

The default value for array elements.

Definition at line 126 of file EdgeArray.h.

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

include/ogdf/basic/EdgeArray.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ iterator

◆ key_type

◆ value_type

Constructor & Destructor Documentation

◆ EdgeArray() [1/5]

◆ EdgeArray() [2/5]

◆ EdgeArray() [3/5]

◆ EdgeArray() [4/5]

◆ EdgeArray() [5/5]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ disconnect()

◆ end() [1/2]

◆ end() [2/2]

◆ enlargeTable()

◆ fill()

◆ findPredKey()

◆ findSuccKey()

◆ graphOf()

◆ init() [1/3]

◆ init() [2/3]

◆ init() [3/3]

◆ operator()() [1/4]

◆ operator()() [2/4]

◆ operator()() [3/4]

◆ operator()() [4/4]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/6]

◆ operator[]() [2/6]

◆ operator[]() [3/6]

◆ operator[]() [4/6]

◆ operator[]() [5/6]

◆ operator[]() [6/6]

◆ reinit()

◆ valid()

Member Data Documentation

◆ m_x

Open
Graph Drawing
Framework