Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::SubsetEnumerator< T > Class Template Reference

Enumerator for k-subsets of a given type. More...

#include <ogdf/basic/SubsetEnumerator.h>

Public Member Functions

template<typename ContainerType >
 SubsetEnumerator (const ContainerType &set)
 Constructor. More...
 
void array (Array< T > &array) const
 Obtains an array of the subset members. More...
 
void begin ()
 Initializes the SubsetEnumerator to enumerate all subsets. More...
 
void begin (int card)
 Initializes the SubsetEnumerator to enumerate subsets of given cardinality. More...
 
void begin (int low, int high)
 Initializes the SubsetEnumerator to enumerate subsets of cardinalities from low to high. More...
 
void forEachMember (std::function< void(const T &)> func) const
 Calls func for each member in the subset. More...
 
void forEachMemberAndNonmember (std::function< void(const T &)> funcIn, std::function< void(const T &)> funcNotIn) const
 Calls funcIn for each subset member and funcNotIn for each other element of the set. More...
 
template<typename ContainerType >
void getSubsetAndComplement (ContainerType &subset, ContainerType &complement, std::function< void(ContainerType &, T)> func) const
 Obtains a container of the subset members and a container of the other elements of the set. More...
 
bool hasMember (const T &element) const
 Checks in O(subset cardinality) whether element is a member of the subset. More...
 
void list (List< T > &subset) const
 Obtains (appends) a list of the subset members. More...
 
void list (List< T > &subset, List< T > &complement) const
 Obtains (appends) a list of the subset members and a list of the other elements of the set. More...
 
void next ()
 Obtains the next subset if possible. The result should be checked using the valid() method. More...
 
int numberOfMembersAndNonmembers () const
 Returns the cardinality of the (super-)set. This is the maximum size that can be used for a subset. More...
 
operator[] (int i) const
 Gets a member of subset by index (starting from 0). More...
 
void print (std::ostream &os, string delim=" ") const
 Prints subset to output stream os using delimiter delim. More...
 
int size () const
 Returns the cardinality of the subset. More...
 
bool testForAll (std::function< bool(const T &)> predicate) const
 Tests predicate for all subset members. More...
 
bool valid () const
 Checks if the current subset is valid. If not, the subset is either not initialized or all subsets have already been enumerated. More...
 

Protected Member Functions

void initSubset (int card)
 

Protected Attributes

Array< int > m_index
 
int m_maxCard
 
ArrayBuffer< T > m_subset
 
bool m_valid
 

Detailed Description

template<typename T>
class ogdf::SubsetEnumerator< T >

Enumerator for k-subsets of a given type.

Usage examples

  • Enumerate all subsets of edges with cardinality 3:
    List<edge> edges;
    do_something_eg_fill_edges();
    SubsetEnumerator<edge> subset(edges);
    for (subset.begin(3); subset.valid(); subset.next()) {
    do_something_with(subset[0], subset[1], subset[2]);
    }
  • Enumerate all subsets of edges:
    SubsetEnumerator<edge> subset(edges);
    for (subset.begin(); subset.valid(); subset.next()) {
    for (int i = 0; i < subset.size(); ++i) {
    do_something_with(subset[i]);
    }
    do_stuff();
    }
  • Do something with member lists and complement lists of all 2-, 3-, and 4-element subsets
    SubsetEnumerator<edge> subset(edges);
    for (subset.begin(2, 4); subset.valid(); subset.next()) {
    List<edge> list1, list2;
    subset.list(list1, list2);
    // if subset = { 1, 3, 4 } of { 1, 2, 3, 4, 5 },
    // then list1 = 1 3 4 and list2 = 2 5
    do_something_with(list1);
    do_another_things_with(list2);
    }

Please note that the internal data structures of SubsetEnumerator do not use references of the type T. Hence, T should either be a simple type or a pointer to a complex type (which is also only sane for Lists, too). Otherwise the data structure will slow down due to extensive implicit copying.

Definition at line 88 of file SubsetEnumerator.h.

Constructor & Destructor Documentation

◆ SubsetEnumerator()

template<typename T >
template<typename ContainerType >
ogdf::SubsetEnumerator< T >::SubsetEnumerator ( const ContainerType &  set)
inlineexplicit

Constructor.

Parameters
setThe container of elements we want to enumerate subsets for.

Definition at line 113 of file SubsetEnumerator.h.

Member Function Documentation

◆ array()

template<typename T >
void ogdf::SubsetEnumerator< T >::array ( Array< T > &  array) const
inline

Obtains an array of the subset members.

Definition at line 234 of file SubsetEnumerator.h.

◆ begin() [1/3]

template<typename T >
void ogdf::SubsetEnumerator< T >::begin ( )
inline

Initializes the SubsetEnumerator to enumerate all subsets.

Definition at line 142 of file SubsetEnumerator.h.

◆ begin() [2/3]

template<typename T >
void ogdf::SubsetEnumerator< T >::begin ( int  card)
inline

Initializes the SubsetEnumerator to enumerate subsets of given cardinality.

Definition at line 136 of file SubsetEnumerator.h.

◆ begin() [3/3]

template<typename T >
void ogdf::SubsetEnumerator< T >::begin ( int  low,
int  high 
)
inline

Initializes the SubsetEnumerator to enumerate subsets of cardinalities from low to high.

Definition at line 124 of file SubsetEnumerator.h.

◆ forEachMember()

template<typename T >
void ogdf::SubsetEnumerator< T >::forEachMember ( std::function< void(const T &)>  func) const
inline

Calls func for each member in the subset.

Definition at line 218 of file SubsetEnumerator.h.

◆ forEachMemberAndNonmember()

template<typename T >
void ogdf::SubsetEnumerator< T >::forEachMemberAndNonmember ( std::function< void(const T &)>  funcIn,
std::function< void(const T &)>  funcNotIn 
) const
inline

Calls funcIn for each subset member and funcNotIn for each other element of the set.

Definition at line 243 of file SubsetEnumerator.h.

◆ getSubsetAndComplement()

template<typename T >
template<typename ContainerType >
void ogdf::SubsetEnumerator< T >::getSubsetAndComplement ( ContainerType &  subset,
ContainerType &  complement,
std::function< void(ContainerType &, T)>  func 
) const
inline

Obtains a container of the subset members and a container of the other elements of the set.

Definition at line 257 of file SubsetEnumerator.h.

◆ hasMember()

template<typename T >
bool ogdf::SubsetEnumerator< T >::hasMember ( const T &  element) const
inline

Checks in O(subset cardinality) whether element is a member of the subset.

Definition at line 168 of file SubsetEnumerator.h.

◆ initSubset()

template<typename T >
void ogdf::SubsetEnumerator< T >::initSubset ( int  card)
inlineprotected

Definition at line 95 of file SubsetEnumerator.h.

◆ list() [1/2]

template<typename T >
void ogdf::SubsetEnumerator< T >::list ( List< T > &  subset) const
inline

Obtains (appends) a list of the subset members.

Definition at line 226 of file SubsetEnumerator.h.

◆ list() [2/2]

template<typename T >
void ogdf::SubsetEnumerator< T >::list ( List< T > &  subset,
List< T > &  complement 
) const
inline

Obtains (appends) a list of the subset members and a list of the other elements of the set.

Definition at line 267 of file SubsetEnumerator.h.

◆ next()

template<typename T >
void ogdf::SubsetEnumerator< T >::next ( )
inline

Obtains the next subset if possible. The result should be checked using the valid() method.

Definition at line 187 of file SubsetEnumerator.h.

◆ numberOfMembersAndNonmembers()

template<typename T >
int ogdf::SubsetEnumerator< T >::numberOfMembersAndNonmembers ( ) const
inline

Returns the cardinality of the (super-)set. This is the maximum size that can be used for a subset.

Definition at line 155 of file SubsetEnumerator.h.

◆ operator[]()

template<typename T >
T ogdf::SubsetEnumerator< T >::operator[] ( int  i) const
inline

Gets a member of subset by index (starting from 0).

Definition at line 179 of file SubsetEnumerator.h.

◆ print()

template<typename T >
void ogdf::SubsetEnumerator< T >::print ( std::ostream &  os,
string  delim = " " 
) const
inline

Prints subset to output stream os using delimiter delim.

Definition at line 286 of file SubsetEnumerator.h.

◆ size()

template<typename T >
int ogdf::SubsetEnumerator< T >::size ( ) const
inline

Returns the cardinality of the subset.

Definition at line 148 of file SubsetEnumerator.h.

◆ testForAll()

template<typename T >
bool ogdf::SubsetEnumerator< T >::testForAll ( std::function< bool(const T &)>  predicate) const
inline

Tests predicate for all subset members.

Definition at line 275 of file SubsetEnumerator.h.

◆ valid()

template<typename T >
bool ogdf::SubsetEnumerator< T >::valid ( ) const
inline

Checks if the current subset is valid. If not, the subset is either not initialized or all subsets have already been enumerated.

Definition at line 162 of file SubsetEnumerator.h.

Member Data Documentation

◆ m_index

template<typename T >
Array<int> ogdf::SubsetEnumerator< T >::m_index
protected

Definition at line 93 of file SubsetEnumerator.h.

◆ m_maxCard

template<typename T >
int ogdf::SubsetEnumerator< T >::m_maxCard
protected

Definition at line 91 of file SubsetEnumerator.h.

◆ m_subset

template<typename T >
ArrayBuffer<T> ogdf::SubsetEnumerator< T >::m_subset
protected

Definition at line 92 of file SubsetEnumerator.h.

◆ m_valid

template<typename T >
bool ogdf::SubsetEnumerator< T >::m_valid
protected

Definition at line 90 of file SubsetEnumerator.h.


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