networkit.structures

class networkit.structures.Cover(n=0)

Bases: object

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

Parameters

n (int or networkit.Partition, optional) – Used for initialization of the cover. Either a node or a partition. Default: 0

addToSubset(s, e)

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

Parameters
  • s (int) – The input subset.

  • e (int) – The element to be added.

allToSingletons()

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

contains(e)

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

Parameters

e (int) – The input element.

Returns

True, if e is assigned to a valid subset, False otherwise.

Return type

bool

extend()

Add an additional element (node).

Returns

Id of added node.

Return type

int

getMembers(s)

Get the members of a specific subset s.

Returns

The list of members of subset s.

Return type

list(int)

getSubsetIds()

Get the ids of nonempty subsets.

Returns

A list of ids of nonempty subsets.

Return type

list(int)

inSameSubset(e1, e2)

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

Parameters
  • e1 (int) – The first element.

  • e2 (int) – The second element.

Returns

True if e1 and e2 belong to the same subset; False otherwise.

Return type

bool

lowerBound()

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

Returns

A lower bound.

Return type

int

mergeSubsets(s, t)

Assigns the elements from both sets to a new set.

Parameters
  • s (int) – The first subset.

  • t (int) – The second subset.

moveToSubset(s, e)

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

Parameters
  • s (int) – The input subset.

  • e (int) – The element to be moved.

numberOfElements()

Get the current number of elements in this cover.

Returns

The current number of elements.

Return type

int

numberOfSubsets()

Get the current number of sets in this cover.

Returns

The number of sets in this cover.

Return type

int

removeFromSubset(s, e)

Remove the element e from the set s.

Parameters
  • s (int) – The input subset.

  • e (int) – The element to be removed.

setUpperBound(upper)

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

Parameters

upper (int) – Upper bound.

subsetSizeMap()

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

Returns

dict(int ` – A map from subset id to size of the subset.

Return type

` int)

subsetSizes()

Get a list of subset sizes.

Returns

A list of subset sizes.

Return type

list(int)

Notes

Indices do not necessarily correspond to subset ids.

subsetsOf(e)

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

Parameters

e (int) – An element

Returns

A set of subset ids in which e is contained.

Return type

list(int)

toSingleton(e)

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

Parameters

e (int) – The input element.

Returns

The id of the new set.

Return type

int

upperBound()

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

Returns

An upper bound.

Return type

int

class networkit.structures.Partition(z=0)

Bases: object

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

Create a new partition data structure for z elements.

Parameters

size (int, optional) – Maximum index of an element. Default: 0

addToSubset(s, e)

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

Parameters
  • s (int) – The index of the subset.

  • e (int) – The element to add.

allToSingletons()

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

compact(userTurbo=False)

Change subset IDs to be consecutive, starting at 0.

Parameters

useTurbo (bool, optional) – If set to True, the C++ core uses a vector instead of a map to assign new ids which results in a shorter running time but possibly a large space overhead. Default: False

contains(e)

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

Parameters

e (int) – The input element.

Returns

True if the assigned subset is valid; False otherwise.

Return type

bool

extend()

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

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

Returns

The index of the new element.

Return type

int

getMembers(s)

Get the members of the subset s.

Parameters

s (int) – The input subset.

Returns

A list containing the members of s.

Return type

list(int)

getName()

Get the human-readable identifier.

Returns

The name of this partition.

Return type

str

getSubsetIds()

Get the ids of nonempty subsets.

Returns

A set of ids of nonempty subsets.

Return type

list(int)

getVector()

Get the actual vector representing the partition data structure.

Returns

List containing information about partitions.

Return type

list(int)

inSameSubset(e1, e2)

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

Parameters
  • e1 (int) – The first Element.

  • e2 (int) – The second Element.

Returns

True if e1 and e2 belong to same subset, False otherwise.

Return type

bool

lowerBound()

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

Returns

The lower bound.

Return type

int

mergeSubsets(s, t)

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

Parameters
  • s (int) – Set to merge.

  • t (int) – Set to merge.

Returns

Id of newly created set.

Return type

int

moveToSubset(s, e)

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

Parameters
  • s (int) – The index of the subset.

  • e (int) – The element to move.

numberOfElements()
Returns

Number of elements in the partition.

Return type

int

numberOfSubsets()

Get the current number of sets in this partition.

Returns

The current number of sets.

Return type

int

setName(name)

Set a human-readable identifier name for the instance.

Parameters

name (str) – The input name.

setUpperBound(upper)

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

Parameters

upper (int) – Highest assigned subset id + 1.

subsetOf(e)

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

Parameters

e (int) – Index of element.

Returns

The index of the set in which e is contained.

Return type

int

subsetSizeMap()

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

Returns

dict(int ` – A map from subset id to size of the subset.

Return type

` int)

subsetSizes()

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

Returns

A list of subset sizes.

Return type

list(int)

toSingleton(e)

Creates a singleton set containing the element e.

Parameters

e (int) – The index of the element.

upperBound()

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

Returns

The upper bound.

Return type

int