All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
NetworKit::Partition Class Reference

Implements a partition of a set, i.e. More...

#include <Partition.h>

Public Member Functions

 Partition ()
 
 Partition (index z)
 Create a new partition data structure for z elements. More...
 
 Partition (index z, index defaultValue)
 Create a new partition data structure for z elements. More...
 
 Partition (const std::vector< index > &data)
 
indexoperator[] (const index &e)
 Index operator. More...
 
const indexoperator[] (const index &e) const
 Index operator for const instances of this class. More...
 
index subsetOf (index e) const
 Get the set (id) in which the element e is contained. More...
 
index extend ()
 Extend the data structure and create a slot for one more element. More...
 
void remove (index e)
 Removes the entry for the given element by setting it to none. More...
 
void addToSubset (index s, index e)
 Add a (previously unassigned) element e to the set s. More...
 
void moveToSubset (index s, index e)
 Move the (previously assigned) element e to the set s. More...
 
void toSingleton (index e)
 Creates a singleton set containing the element e. More...
 
void allToSingletons ()
 Assigns every element to a singleton set. More...
 
void allToOnePartition ()
 Assigns every element to the same subset. More...
 
index mergeSubsets (index s, index t)
 Assigns the elements from both sets to a new set and returns the id of it. More...
 
void setUpperBound (index upper)
 Check if partition is a 1-partition, i.e. More...
 
index upperBound () const
 Return an upper bound for the subset ids that have been assigned. More...
 
index lowerBound () const
 Get a lower bound for the subset ids that have been assigned. More...
 
void compact (bool useTurbo=false)
 Change subset IDs to be consecutive, starting at 0. More...
 
bool contains (index e) const
 Check if partition assigns a valid subset to the element e. More...
 
bool inSameSubset (index e1, index e2) const
 Check if two elements e1 and e2 belong to the same subset. More...
 
std::vector< countsubsetSizes () const
 Get a list of subset sizes. More...
 
std::map< index, countsubsetSizeMap () const
 Get a map from subset id to size of the subset. More...
 
std::set< indexgetMembers (const index s) const
 Get the members of the subset s. More...
 
count numberOfElements () const
 
count numberOfSubsets () const
 Get the current number of sets in this partition. More...
 
std::vector< indexgetVector () const
 Get the actual vector representing the partition data structure. More...
 
std::set< std::set< index > > getSubsets () const
 
std::set< indexgetSubsetIds () const
 Get the ids of nonempty subsets. More...
 
void setName (std::string name)
 Set a human-readable identifier name for the instance. More...
 
std::string getName () const
 Get the human-readable identifier. More...
 
template<typename Callback >
void forEntries (Callback func) const
 Iterate over all entries (node, cluster id) and execute callback function func (lambda closure). More...
 
template<typename Callback >
void parallelForEntries (Callback handle) const
 Iterate over all entries (node, cluster id) in parallel and execute callback function handle (lambda closure). More...
 

Detailed Description

Implements a partition of a set, i.e.

a subdivision of the set into disjoint subsets.

Constructor & Destructor Documentation

NetworKit::Partition::Partition ( )
NetworKit::Partition::Partition ( index  z)

Create a new partition data structure for z elements.

Parameters
[in]zmaximum index
NetworKit::Partition::Partition ( index  z,
index  defaultValue 
)

Create a new partition data structure for z elements.

Initialize each entry to the default value. WARNING: this circumvents the standard interface and may leave the object in an inconsistent state. Use only in exceptional cases.

Parameters
[in]zmaximum index
[in]defaultValue
NetworKit::Partition::Partition ( const std::vector< index > &  data)

Member Function Documentation

void NetworKit::Partition::addToSubset ( index  s,
index  e 
)
inline

Add a (previously unassigned) element e to the set s.

Parameters
sThe index of the subset.
eThe element to add.
void NetworKit::Partition::allToOnePartition ( )

Assigns every element to the same subset.

Set id is equal to zero.

void NetworKit::Partition::allToSingletons ( )

Assigns every element to a singleton set.

Set id is equal to element id.

void NetworKit::Partition::compact ( bool  useTurbo = false)

Change subset IDs to be consecutive, starting at 0.

Parameters
useTurboDefault: false. If set to true, a vector instead of a map to assign new ids which results in a shorter running time but possibly a large space overhead.
bool NetworKit::Partition::contains ( index  e) const
inline

Check if partition assigns a valid subset to the element e.

Parameters
eThe element.
Returns
true if the assigned subset is valid, false otherwise.
index NetworKit::Partition::extend ( )
inline

Extend the data structure and create a slot for one more element.

Initializes the entry to none and returns the index of the entry.

template<typename Callback >
void NetworKit::Partition::forEntries ( Callback  func) const
inline

Iterate over all entries (node, cluster id) and execute callback function func (lambda closure).

Parameters
funcTakes parameters (node, index)
std::set< index > NetworKit::Partition::getMembers ( const index  s) const

Get the members of the subset s.

Parameters
sThe subset.
Returns
A set containing the members of s.
std::string NetworKit::Partition::getName ( ) const
inline

Get the human-readable identifier.

Returns
The name of this partition.
std::set< index > NetworKit::Partition::getSubsetIds ( ) const

Get the ids of nonempty subsets.

Returns
A set of ids of nonempty subsets.
std::set< std::set< index > > NetworKit::Partition::getSubsets ( ) const
Returns
the subsets of the partition as a set of sets.
std::vector< index > NetworKit::Partition::getVector ( ) const

Get the actual vector representing the partition data structure.

Returns
vector containing information about partitions.
bool NetworKit::Partition::inSameSubset ( index  e1,
index  e2 
) const
inline

Check if two elements e1 and e2 belong to the same subset.

Parameters
e1Element.
e2Element.
Returns
true if e1 and e2 belong to same subset, false otherwise.
index NetworKit::Partition::lowerBound ( ) const
inline

Get a lower bound for the subset ids that have been assigned.

Returns
The lower bound.
index NetworKit::Partition::mergeSubsets ( index  s,
index  t 
)

Assigns the elements from both sets to a new set and returns the id of it.

Parameters
sSet to merge.
tSet to merge.
Returns
Id of newly created set.
void NetworKit::Partition::moveToSubset ( index  s,
index  e 
)
inline

Move the (previously assigned) element e to the set s.

Parameters
sThe index of the subset.
eThe element to move.
count NetworKit::Partition::numberOfElements ( ) const
inline
Returns
number of elements in the partition.
count NetworKit::Partition::numberOfSubsets ( ) const

Get the current number of sets in this partition.

Returns
The current number of sets.
index& NetworKit::Partition::operator[] ( const index e)
inline

Index operator.

Parameters
[in]ean element
const index& NetworKit::Partition::operator[] ( const index e) const
inline

Index operator for const instances of this class.

Parameters
[in]ean element
template<typename Callback >
void NetworKit::Partition::parallelForEntries ( Callback  handle) const
inline

Iterate over all entries (node, cluster id) in parallel and execute callback function handle (lambda closure).

Parameters
handleTakes parameters (node, index)
void NetworKit::Partition::remove ( index  e)
inline

Removes the entry for the given element by setting it to none.

void NetworKit::Partition::setName ( std::string  name)
inline

Set a human-readable identifier name for the instance.

Parameters
nameThe name.
void NetworKit::Partition::setUpperBound ( index  upper)
inline

Check if partition is a 1-partition, i.e.

every element is assigned to the same set. Check if partition is a singleton partition, i.e. every element is assigned to a different set. Sets an upper bound for the subset ids that CAN be assigned.

Parameters
[in]upperhighest assigned subset ID + 1
index NetworKit::Partition::subsetOf ( index  e) const
inline

Get the set (id) in which the element e is contained.

Parameters
eIndex of element.
Returns
The index of the set in which e is contained.
std::map< index, count > NetworKit::Partition::subsetSizeMap ( ) const

Get a map from subset id to size of the subset.

Returns
A map from subset id to size of the subset.
std::vector< count > NetworKit::Partition::subsetSizes ( ) const

Get a list of subset sizes.

Indices do not necessarily correspond to subset ids.

Returns
A vector of subset sizes.
void NetworKit::Partition::toSingleton ( index  e)
inline

Creates a singleton set containing the element e.

Parameters
eThe index of the element.
index NetworKit::Partition::upperBound ( ) const
inline

Return an upper bound for the subset ids that have been assigned.

(This is the maximum id + 1.)

Returns
The upper bound.

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