The node set in a shelling order of a graph. More...

#include <ogdf/planarlayout/ShellingOrder.h>

Inheritance diagram for ogdf::ShellingOrderSet:

Public Member Functions
	ShellingOrderSet ()
	Creates an empty shelling order set.

	ShellingOrderSet (int n, adjEntry adjL=nullptr, adjEntry adjR=nullptr)
	Creates a shelling order set for `n` nodes.

bool	hasLeft () const
	Returns true iff the adjacency entry to the left-node exists.

bool	hasRight () const
	Returns true iff the adjacency entry to the right-node exists.

node	left () const
	Returns the left-node of the set.

void	left (node cl)
	Sets the left-node to `cl`.

adjEntry	leftAdj () const
	Returns the adjacency entry pointing from z₁ to the left node (or 0 if no such node).

void	leftAdj (adjEntry adjL)
	Sets the adjacency entry pointing to the left-node to `adjL`.

int	len () const
	Returns the length of the order set, i.e., the number of contained nodes.

node &	operator[] (const int i)
	Returns the i-th node in the order set from left (the leftmost node has index 1).

node	operator[] (const int i) const
	Returns the i-th node in the order set from left (the leftmost node has index 1).

node	right () const
	Returns the right-node of the set.

void	right (node cr)
	Sets the right-node to `cr`.

adjEntry	rightAdj () const
	Returns the adjacency entry pointing from z_p to the right node (or 0 if no such node).

void	rightAdj (adjEntry adjR)
	Sets the adjacency entry pointing to the right-node to `adjR`.

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

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

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

	Array (const ArrayBuffer< node, 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 node &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< node > 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 node &x)
	Reinitializes the array to an array with index set [`a`..`b`] and sets all entries to `x`.

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

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

void	grow (int add, const node &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 node &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< node, int > &	operator= (const Array< node, int > &A)
	Assignment operator.

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

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

bool	operator!= (const Array< node, 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 node &e) const
	Performs a binary search for element `e`.

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

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

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

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

int	linearSearch (const node &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 node &val)
	Removes the components listed in `ind` by shifting the remaining components to the left.

Private Attributes
adjEntry	m_leftAdj
	the adjacency entry pointing to the left-node.

node	m_leftVertex
	the left-node of the set.

adjEntry	m_rightAdj
	the adjacency entry pointing to the right-node.

node	m_rightVertex
	the right-node of the set.

Additional Inherited Members
Public Types inherited from ogdf::Array< node >
using	const_iterator = ArrayConstIterator< node >
	Provides a random-access iterator that can read a const element in an array.

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

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

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

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

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

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

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

Detailed Description

The node set in a shelling order of a graph.

Definition at line 42 of file ShellingOrder.h.

Constructor & Destructor Documentation

◆ ShellingOrderSet() [1/2]

ogdf::ShellingOrderSet::ShellingOrderSet ( )

inline

Creates an empty shelling order set.

Definition at line 45 of file ShellingOrder.h.

◆ ShellingOrderSet() [2/2]

ogdf::ShellingOrderSet::ShellingOrderSet	(	int	n,
		adjEntry	adjL = `nullptr`,
		adjEntry	adjR = `nullptr`
	)

inline

Creates a shelling order set for n nodes.

Parameters

n	is the number of nodes in the set.
adjL	points to the left-node of the set.
adjR	points to the right-node of the set.

Definition at line 56 of file ShellingOrder.h.

Member Function Documentation

◆ hasLeft()

bool ogdf::ShellingOrderSet::hasLeft ( ) const

inline

Returns true iff the adjacency entry to the left-node exists.

Definition at line 76 of file ShellingOrder.h.

◆ hasRight()

bool ogdf::ShellingOrderSet::hasRight ( ) const

inline

Returns true iff the adjacency entry to the right-node exists.

Definition at line 79 of file ShellingOrder.h.

◆ left() [1/2]

node ogdf::ShellingOrderSet::left ( ) const

inline

Returns the left-node of the set.

Definition at line 64 of file ShellingOrder.h.

◆ left() [2/2]

void ogdf::ShellingOrderSet::left ( node cl )

inline

Sets the left-node to cl.

Definition at line 82 of file ShellingOrder.h.

◆ leftAdj() [1/2]

adjEntry ogdf::ShellingOrderSet::leftAdj ( ) const

inline

Returns the adjacency entry pointing from z₁ to the left node (or 0 if no such node).

Definition at line 70 of file ShellingOrder.h.

◆ leftAdj() [2/2]

void ogdf::ShellingOrderSet::leftAdj ( adjEntry adjL )

inline

Sets the adjacency entry pointing to the left-node to adjL.

Definition at line 88 of file ShellingOrder.h.

◆ len()

int ogdf::ShellingOrderSet::len ( ) const

inline

Returns the length of the order set, i.e., the number of contained nodes.

Definition at line 94 of file ShellingOrder.h.

◆ operator[]() [1/2]

node & ogdf::ShellingOrderSet::operator[] ( const int i )

inline

Returns the i-th node in the order set from left (the leftmost node has index 1).

Definition at line 100 of file ShellingOrder.h.

◆ operator[]() [2/2]

node ogdf::ShellingOrderSet::operator[] ( const int i ) const

inline

Returns the i-th node in the order set from left (the leftmost node has index 1).

Definition at line 97 of file ShellingOrder.h.

◆ right() [1/2]

node ogdf::ShellingOrderSet::right ( ) const

inline

Returns the right-node of the set.

Definition at line 67 of file ShellingOrder.h.

◆ right() [2/2]

void ogdf::ShellingOrderSet::right ( node cr )

inline

Sets the right-node to cr.

Definition at line 85 of file ShellingOrder.h.

◆ rightAdj() [1/2]

adjEntry ogdf::ShellingOrderSet::rightAdj ( ) const

inline

Returns the adjacency entry pointing from z_p to the right node (or 0 if no such node).

Definition at line 73 of file ShellingOrder.h.

◆ rightAdj() [2/2]

void ogdf::ShellingOrderSet::rightAdj ( adjEntry adjR )

inline

Sets the adjacency entry pointing to the right-node to adjR.

Definition at line 91 of file ShellingOrder.h.

Member Data Documentation

◆ m_leftAdj

adjEntry ogdf::ShellingOrderSet::m_leftAdj

private

the adjacency entry pointing to the left-node.

Definition at line 106 of file ShellingOrder.h.

◆ m_leftVertex

node ogdf::ShellingOrderSet::m_leftVertex

private

the left-node of the set.

Definition at line 104 of file ShellingOrder.h.

◆ m_rightAdj

adjEntry ogdf::ShellingOrderSet::m_rightAdj

private

the adjacency entry pointing to the right-node.

Definition at line 107 of file ShellingOrder.h.

◆ m_rightVertex

node ogdf::ShellingOrderSet::m_rightVertex

private

the right-node of the set.

Definition at line 105 of file ShellingOrder.h.

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

include/ogdf/planarlayout/ShellingOrder.h

OpenGraph DrawingFramework

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ ShellingOrderSet() [1/2]

◆ ShellingOrderSet() [2/2]

Member Function Documentation

◆ hasLeft()

◆ hasRight()

◆ left() [1/2]

◆ left() [2/2]

◆ leftAdj() [1/2]

◆ leftAdj() [2/2]

◆ len()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ right() [1/2]

◆ right() [2/2]

◆ rightAdj() [1/2]

◆ rightAdj() [2/2]

Member Data Documentation

◆ m_leftAdj

◆ m_leftVertex

◆ m_rightAdj

◆ m_rightVertex

Open
Graph Drawing
Framework