Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::NodeSet< SupportFastSizeQuery > Class Template Reference

Node sets. More...

#include <ogdf/basic/NodeSet.h>

Public Types

using ListType = typename std::conditional< SupportFastSizeQuery, List< node >, ListPure< node > >::type
 

Public Member Functions

 NodeSet (const Graph &G)
 Creates an empty node set associated with graph G. More...
 
template<bool OtherSupportsFastSizeQuery>
 NodeSet (const NodeSet< OtherSupportsFastSizeQuery > &other)
 Copy constructor. More...
 
void clear ()
 Removes all nodes from this set. More...
 
const GraphgraphOf () const
 Returns the associated graph. More...
 
void insert (node v)
 Inserts node v into this set. More...
 
bool isMember (node v) const
 Returns true iff node v is contained in this set. More...
 
const ListTypenodes () const
 Returns a reference to the list of nodes contained in this set. More...
 
template<bool OtherSupportsFastSizeQuery>
NodeSetoperator= (const NodeSet< OtherSupportsFastSizeQuery > &other)
 Assignment operator. More...
 
void remove (node v)
 Removes node v from this set. More...
 
int size () const
 Returns the number of nodes in this set. More...
 

Private Attributes

NodeArray< ListIterator< node > > m_it
 m_it[v] contains the list iterator pointing to v if v is contained in this set, or an invalid list iterator otherwise. More...
 
ListType m_nodes
 The list of nodes contained in this set. More...
 

Detailed Description

template<bool SupportFastSizeQuery = true>
class ogdf::NodeSet< SupportFastSizeQuery >

Node sets.

Maintains a subset of nodes contained in an associated graph.

Provides efficient operations for testing membership, iteration, insertion, and deletion of elements, as well as clearing the set.

Template Parameters
SupportFastSizeQueryWhether this set supports querying it's size in constant instead of linear time (in the size).
See also
FaceSet

Definition at line 54 of file NodeSet.h.

Member Typedef Documentation

◆ ListType

template<bool SupportFastSizeQuery = true>
using ogdf::NodeSet< SupportFastSizeQuery >::ListType = typename std::conditional<SupportFastSizeQuery, List<node>, ListPure<node> >::type

Definition at line 56 of file NodeSet.h.

Constructor & Destructor Documentation

◆ NodeSet() [1/2]

template<bool SupportFastSizeQuery = true>
ogdf::NodeSet< SupportFastSizeQuery >::NodeSet ( const Graph G)
inlineexplicit

Creates an empty node set associated with graph G.

Definition at line 59 of file NodeSet.h.

◆ NodeSet() [2/2]

template<bool SupportFastSizeQuery = true>
template<bool OtherSupportsFastSizeQuery>
ogdf::NodeSet< SupportFastSizeQuery >::NodeSet ( const NodeSet< OtherSupportsFastSizeQuery > &  other)
inline

Copy constructor.

Definition at line 135 of file NodeSet.h.

Member Function Documentation

◆ clear()

template<bool SupportFastSizeQuery = true>
void ogdf::NodeSet< SupportFastSizeQuery >::clear ( )
inline

Removes all nodes from this set.

After this operation, this set is empty and still associated with the same graph. The runtime of this operations is linear in the size().

Definition at line 99 of file NodeSet.h.

◆ graphOf()

template<bool SupportFastSizeQuery = true>
const Graph& ogdf::NodeSet< SupportFastSizeQuery >::graphOf ( ) const
inline

Returns the associated graph.

Definition at line 121 of file NodeSet.h.

◆ insert()

template<bool SupportFastSizeQuery = true>
void ogdf::NodeSet< SupportFastSizeQuery >::insert ( node  v)
inline

Inserts node v into this set.

This operation has constant runtime. If the node is already contained in this set, nothing happens.

Precondition
v is a node in the associated graph.

Definition at line 68 of file NodeSet.h.

◆ isMember()

template<bool SupportFastSizeQuery = true>
bool ogdf::NodeSet< SupportFastSizeQuery >::isMember ( node  v) const
inline

Returns true iff node v is contained in this set.

This operation has constant runtime.

Precondition
v is a node in the associated graph.

Definition at line 110 of file NodeSet.h.

◆ nodes()

template<bool SupportFastSizeQuery = true>
const ListType& ogdf::NodeSet< SupportFastSizeQuery >::nodes ( ) const
inline

Returns a reference to the list of nodes contained in this set.

Definition at line 116 of file NodeSet.h.

◆ operator=()

template<bool SupportFastSizeQuery = true>
template<bool OtherSupportsFastSizeQuery>
NodeSet& ogdf::NodeSet< SupportFastSizeQuery >::operator= ( const NodeSet< OtherSupportsFastSizeQuery > &  other)
inline

Assignment operator.

Definition at line 141 of file NodeSet.h.

◆ remove()

template<bool SupportFastSizeQuery = true>
void ogdf::NodeSet< SupportFastSizeQuery >::remove ( node  v)
inline

Removes node v from this set.

This operation has constant runtime.

Precondition
v is a node in the associated graph. If the node is not contained in this set, nothing happens.

Definition at line 84 of file NodeSet.h.

◆ size()

template<bool SupportFastSizeQuery = true>
int ogdf::NodeSet< SupportFastSizeQuery >::size ( ) const
inline

Returns the number of nodes in this set.

This operation has either linear or constant runtime, depending on SupportFastSizeQuery.

Definition at line 129 of file NodeSet.h.

Member Data Documentation

◆ m_it

template<bool SupportFastSizeQuery = true>
NodeArray<ListIterator<node> > ogdf::NodeSet< SupportFastSizeQuery >::m_it
private

m_it[v] contains the list iterator pointing to v if v is contained in this set, or an invalid list iterator otherwise.

Definition at line 152 of file NodeSet.h.

◆ m_nodes

template<bool SupportFastSizeQuery = true>
ListType ogdf::NodeSet< SupportFastSizeQuery >::m_nodes
private

The list of nodes contained in this set.

Definition at line 155 of file NodeSet.h.


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