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.
void	array (Array< T > &array) const
	Obtains an array of the subset members.
void	begin ()
	Initializes the SubsetEnumerator to enumerate all subsets.
void	begin (int card)
	Initializes the SubsetEnumerator to enumerate subsets of given cardinality.
void	begin (int low, int high)
	Initializes the SubsetEnumerator to enumerate subsets of cardinalities from low to high.
void	forEachMember (std::function< void(const T &)> func) const
	Calls func for each member in the subset.
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.
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.
bool	hasMember (const T &element) const
	Checks in O(subset cardinality) whether element is a member of the subset.
void	list (List< T > &subset) const
	Obtains (appends) a list of the subset members.
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.
void	next ()
	Obtains the next subset if possible. The result should be checked using the valid() method.
int	numberOfMembersAndNonmembers () const
	Returns the cardinality of the (super-)set. This is the maximum size that can be used for a subset.
T	operator[] (int i) const
	Gets a member of subset by index (starting from 0).
void	print (std::ostream &os, string delim=" ") const
	Prints subset to output stream os using delimiter delim.
int	size () const
	Returns the cardinality of the subset.
bool	testForAll (std::function< bool(const T &)> predicate) const
	Tests predicate for all subset members.
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.

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

set	The container of elements we want to enumerate subsets for.

Definition at line 112 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 207 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 134 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 131 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 120 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 195 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 215 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 229 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 148 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 202 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 236 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 165 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 141 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 158 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 252 of file SubsetEnumerator.h.

size()

template<typename T >

int ogdf::SubsetEnumerator< T >::size ( ) const

inline

Returns the cardinality of the subset.

Definition at line 137 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 242 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 145 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:

• include/ogdf/basic/SubsetEnumerator.h