Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ShellingOrderSet Class Reference

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. More...
 
 ShellingOrderSet (int n, adjEntry adjL=nullptr, adjEntry adjR=nullptr)
 Creates a shelling order set for n nodes. More...
 
bool hasLeft () const
 Returns true iff the adjacency entry to the left-node exists. More...
 
bool hasRight () const
 Returns true iff the adjacency entry to the right-node exists. More...
 
node left () const
 Returns the left-node of the set. More...
 
void left (node cl)
 Sets the left-node to cl. More...
 
adjEntry leftAdj () const
 Returns the adjacency entry pointing from z1 to the left node (or 0 if no such node). More...
 
void leftAdj (adjEntry adjL)
 Sets the adjacency entry pointing to the left-node to adjL. More...
 
int len () const
 Returns the length of the order set, i.e., the number of contained nodes. More...
 
nodeoperator[] (const int i)
 Returns the i-th node in the order set from left (the leftmost node has index 1). More...
 
node operator[] (const int i) const
 Returns the i-th node in the order set from left (the leftmost node has index 1). More...
 
node right () const
 Returns the right-node of the set. More...
 
void right (node cr)
 Sets the right-node to cr. More...
 
adjEntry rightAdj () const
 Returns the adjacency entry pointing from zp to the right node (or 0 if no such node). More...
 
void rightAdj (adjEntry adjR)
 Sets the adjacency entry pointing to the right-node to adjR. More...
 
- Public Member Functions inherited from ogdf::Array< node >
 Array ()
 Creates an array with empty index set. More...
 
 Array (Array< node, int > &&A)
 Creates an array containing the elements of A (move semantics). More...
 
 Array (const Array< node, int > &A)
 Creates an array that is a copy of A. More...
 
 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. More...
 
 Array (int a, int b)
 Creates an array with index set [a..b]. More...
 
 Array (int a, int b, const node &x)
 Creates an array with index set [a..b] and initializes each element with x. More...
 
 Array (int s)
 Creates an array with index set [0..s-1]. More...
 
 Array (std::initializer_list< node > initList)
 Creates an array containing the elements in the initializer list initList. More...
 
 ~Array ()
 Destruction. More...
 
int low () const
 Returns the minimal array index. More...
 
int high () const
 Returns the maximal array index. More...
 
int size () const
 Returns the size (number of elements) of the array. More...
 
bool empty () const
 Returns true iff there are no elements in the array. More...
 
const_reference operator[] (int i) const
 Returns a reference to the element at position i. More...
 
reference operator[] (int i)
 Returns a reference to the element at position i. More...
 
iterator begin ()
 Returns an iterator to the first element. More...
 
const_iterator begin () const
 Returns a const iterator to the first element. More...
 
const_iterator cbegin () const
 Returns a const iterator to the first element. More...
 
iterator end ()
 Returns an iterator to one past the last element. More...
 
const_iterator end () const
 Returns a const iterator to one past the last element. More...
 
const_iterator cend () const
 Returns a const iterator to one past the last element. More...
 
reverse_iterator rbegin ()
 Returns an reverse iterator to the last element. More...
 
const_reverse_iterator rbegin () const
 Returns a const reverse iterator to the last element. More...
 
const_reverse_iterator crbegin () const
 Returns a const reverse iterator to the last element. More...
 
reverse_iterator rend ()
 Returns an reverse iterator to one before the first element. More...
 
const_reverse_iterator rend () const
 Returns a const reverse iterator to one before the first element. More...
 
const_reverse_iterator crend () const
 Returns a const reverse iterator to one before the first element. More...
 
void init ()
 Reinitializes the array to an array with empty index set. More...
 
void init (int s)
 Reinitializes the array to an array with index set [0..s-1]. More...
 
void init (int a, int b)
 Reinitializes the array to an array with index set [a..b]. More...
 
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. More...
 
void fill (const node &x)
 Sets all elements to x. More...
 
void fill (int i, int j, const node &x)
 Sets elements in the intervall [i..j] to x. More...
 
void grow (int add, const node &x)
 Enlarges the array by add elements and sets new elements to x. More...
 
void grow (int add)
 Enlarges the array by add elements. More...
 
void resize (int newSize, const node &x)
 Resizes (enlarges or shrinks) the array to hold newSize elements and sets new elements to x. More...
 
void resize (int newSize)
 Resizes (enlarges or shrinks) the array to hold newSize elements. More...
 
Array< node, int > & operator= (const Array< node, int > &A)
 Assignment operator. More...
 
Array< node, int > & operator= (Array< node, int > &&A)
 Assignment operator (move semantics). More...
 
bool operator== (const Array< node, int > &L) const
 Equality operator. More...
 
bool operator!= (const Array< node, int > &L) const
 Inequality operator. More...
 
void swap (int i, int j)
 Swaps the elements at position i and j. More...
 
void permute (int l, int r)
 Randomly permutes the subarray with index set [l..r]. More...
 
void permute ()
 Randomly permutes the array. More...
 
void permute (int l, int r, RNG &rng)
 Randomly permutes the subarray with index set [l..r] using random number generator rng. More...
 
void permute (RNG &rng)
 Randomly permutes the array using random number generator rng. More...
 
int binarySearch (const node &e) const
 Performs a binary search for element e. More...
 
int binarySearch (int l, int r, const node &e) const
 Performs a binary search for element e within the array section [l, ..., r] . More...
 
int binarySearch (const node &e, const COMPARER &comp) const
 Performs a binary search for element e with comparer comp. More...
 
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. More...
 
int linearSearch (const node &e) const
 Performs a linear search for element e. More...
 
int linearSearch (const node &e, const COMPARER &comp) const
 Performs a linear search for element e with comparer comp. More...
 
void quicksort ()
 Sorts array using Quicksort. More...
 
void quicksort (int l, int r)
 Sorts subarray with index set [l, ..., r] using Quicksort. More...
 
void quicksort (const COMPARER &comp)
 Sorts array using Quicksort and a user-defined comparer comp. More...
 
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. More...
 
void leftShift (ArrayBuffer< int, int > &ind)
 Removes the components listed in ind by shifting the remaining components to the left. More...
 
void leftShift (ArrayBuffer< int, int > &ind, const node &val)
 Removes the components listed in ind by shifting the remaining components to the left. More...
 

Private Attributes

adjEntry m_leftAdj
 the adjacency entry pointing to the left-node. More...
 
node m_leftVertex
 the left-node of the set. More...
 
adjEntry m_rightAdj
 the adjacency entry pointing to the right-node. More...
 
node m_rightVertex
 the right-node of the set. More...
 

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. More...
 
using const_reference = const node &
 Provides a reference to a const element stored in an array for reading and performing const operations. More...
 
using const_reverse_iterator = ArrayConstReverseIterator< node >
 Provides a reverse random-access iterator that can read a const element in an array. More...
 
using iterator = ArrayIterator< node >
 Provides a random-access iterator that can read or modify any element in an array. More...
 
using reference = node &
 Provides a reference to an element stored in an array. More...
 
using reverse_iterator = ArrayReverseIterator< node >
 Provides a reverse random-access iterator that can read or modify any element in an array. More...
 
using value_type = node
 Represents the data type stored in an array element. More...
 
- 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. More...
 

Detailed Description

The node set in a shelling order of a graph.

Definition at line 43 of file ShellingOrder.h.

Constructor & Destructor Documentation

◆ ShellingOrderSet() [1/2]

ogdf::ShellingOrderSet::ShellingOrderSet ( )
inline

Creates an empty shelling order set.

Definition at line 47 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
nis the number of nodes in the set.
adjLpoints to the left-node of the set.
adjRpoints to the right-node of the set.

Definition at line 59 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 89 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 94 of file ShellingOrder.h.

◆ left() [1/2]

node ogdf::ShellingOrderSet::left ( ) const
inline

Returns the left-node of the set.

Definition at line 69 of file ShellingOrder.h.

◆ left() [2/2]

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

Sets the left-node to cl.

Definition at line 99 of file ShellingOrder.h.

◆ leftAdj() [1/2]

adjEntry ogdf::ShellingOrderSet::leftAdj ( ) const
inline

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

Definition at line 79 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 109 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 119 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 129 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 124 of file ShellingOrder.h.

◆ right() [1/2]

node ogdf::ShellingOrderSet::right ( ) const
inline

Returns the right-node of the set.

Definition at line 74 of file ShellingOrder.h.

◆ right() [2/2]

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

Sets the right-node to cr.

Definition at line 104 of file ShellingOrder.h.

◆ rightAdj() [1/2]

adjEntry ogdf::ShellingOrderSet::rightAdj ( ) const
inline

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

Definition at line 84 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 114 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 137 of file ShellingOrder.h.

◆ m_leftVertex

node ogdf::ShellingOrderSet::m_leftVertex
private

the left-node of the set.

Definition at line 135 of file ShellingOrder.h.

◆ m_rightAdj

adjEntry ogdf::ShellingOrderSet::m_rightAdj
private

the adjacency entry pointing to the right-node.

Definition at line 138 of file ShellingOrder.h.

◆ m_rightVertex

node ogdf::ShellingOrderSet::m_rightVertex
private

the right-node of the set.

Definition at line 136 of file ShellingOrder.h.


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