networkit.structures

class networkit.structures.Cover

Bases: object

Implements a cover of a set, i.e. an assignment of its elements to possibly overlapping subsets.

addToSubset(self, s, e)

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

s : index
A subset
e : index
An element
allToSingletons(self)

Assigns every element to a singleton set. Set id is equal to element id.

contains(self, index e)

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

e : index
An element.
bool
True, if e is assigned to a valid subset, False otherwise.
getMembers(self, s)

Get the members of a specific subset s.

set
The set of members of subset s.
getSubsetIds(self)

Get the ids of nonempty subsets.

set
A set of ids of nonempty subsets.
inSameSubset(self, index e1, index e2)

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

e1 : index
An element.
e2 : index
An element.
bool
True, if e1 and e2 belong to the same subset, False otherwise.
lowerBound(self)

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

index
A lower bound.
mergeSubsets(self, index s, index t)

Assigns the elements from both sets to a new set.

s : index
A subset
t : index
A subset
moveToSubset(self, index s, index e)

Move the element e to subset s, i.e. remove it from all other subsets and place it in the subset.

s : index
A subset
e : index
An element
numberOfElements(self)

Get the current number of elements in this cover.

count
The current number of elements.
numberOfSubsets(self)

Get the current number of sets in this cover.

count
The number of sets in this cover.
removeFromSubset(self, s, e)

Remove the element e from the set s.

s : index
A subset
e : index
An element
setUpperBound(self, index upper)
subsetSizeMap(self)

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

dict
A map from subset id to size of the subset.
subsetSizes(self)

Get a list of subset sizes.

list
A list of subset sizes.

Indices do not necessarily correspond to subset ids.

subsetsOf(self, e)

Get the ids of subsets in which the element e is contained.

e : index
An element
set
A set of subset ids in which e is contained.
toSingleton(self, index e)

Creates a singleton set containing the element e and returns the index of the new set.

e : index
An element
index
The index of the new set.
upperBound(self)

Get an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)

index
An upper bound.
class networkit.structures.Partition

Bases: object

Implements a partition of a set, i.e. a subdivision of the set into disjoint subsets.

Partition(z=0)

Create a new partition data structure for z elements.

size : index, optional
Maximum index of an element. Default is 0.
addToSubset(self, s, e)

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

s : index
The index of the subset.
e : index
The element to add.
allToSingletons(self)

Assigns every element to a singleton set. Set id is equal to element id.

compact(self, useTurbo=False)

Change subset IDs to be consecutive, starting at 0.

useTurbo : bool
Default: 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.
contains(self, index e)

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

e : index
The element.
bool
True if the assigned subset is valid, False otherwise.
extend(self)

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

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

index
The index of the new element.
getMembers(self, s)

Get the members of the subset s.

s : index
The subset.
set
A set containing the members of `s.
getName(self)

Get the human-readable identifier.

string
The name of this partition.
getSubsetIds(self)

Get the ids of nonempty subsets.

set
A set of ids of nonempty subsets.
getVector(self)

Get the actual vector representing the partition data structure.

vector
Vector containing information about partitions.
inSameSubset(self, index e1, index e2)

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

e1 : index
An Element.
e2 : index
An Element.
bool
True if e1 and e2 belong to same subset, False otherwise.
lowerBound(self)

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

index
The lower bound.
mergeSubsets(self, index s, index t)

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

s : index
Set to merge.
t : index
Set to merge.
index
Id of newly created set.
moveToSubset(self, index s, index e)

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

s : index
The index of the subset.
e : index
The element to move.
numberOfElements(self)
count
Number of elements in the partition.
numberOfSubsets(self)

Get the current number of sets in this partition.

count
The current number of sets.
setName(self, string name)

Set a human-readable identifier name for the instance.

name : string
The name.
setUpperBound(self, index upper)

Sets an upper bound for the subset ids that can be assigned.

upper : index
Highest assigned subset id + 1
subsetOf(self, e)

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

e : index
Index of element.
index
The index of the set in which e is contained.
subsetSizeMap(self)

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

dict
A map from subset id to size of the subset.
subsetSizes(self)

Get a list of subset sizes. Indices do not necessarily correspond to subset ids.

vector
A vector of subset sizes.
toSingleton(self, index e)

Creates a singleton set containing the element e.

e : index
The index of the element.
upperBound(self)

Return an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)

index
The upper bound.