Public Member Functions
	MySparseMatrix (int V, std::vector< int > reserve)

void	print_heap ()

void	print_heap (int row)

bool	heap_empty ()

max_heap_type	heap_top ()

void	update (int row, int col, float val)

void	insert (int row, int col, float val)

void	erase (int row, int col)

std::map< int, float > &	row (int r)

int	innerNonZero (int row)

void	setZero (int row)

void	print (std::ostream &stream)

Private Member Functions
void	print_heap (std::vector< max_heap_type > &H, std::vector< int > &H_ind, std::vector< int > &H_pos)

bool	heap_empty (std::vector< int > &H_ind)

int	heap_size (std::vector< int > &H_ind)

void	upheap (std::vector< max_heap_type > &H, std::vector< int > &H_ind, std::vector< int > &H_pos, int pos_heap)

void	downheap (std::vector< max_heap_type > &H, std::vector< int > &H_ind, std::vector< int > &H_pos, int pos_heap)

void	heap_update (std::vector< max_heap_type > &H, std::vector< int > &H_ind, std::vector< int > &H_pos, int pos_heap, max_heap_type h_new)

void	heap_insert (std::vector< max_heap_type > &H, std::vector< int > &H_ind, std::vector< int > &H_pos, max_heap_type h)

void	heap_erase (std::vector< max_heap_type > &H, std::vector< int > &H_ind, std::vector< int > &H_pos, int pos_heap)

Private Attributes
std::vector< std::map< int, float > >	_row

std::vector< max_heap_type >	_H

std::vector< int >	_H_ind

std::vector< int >	_H_pos

std::vector< std::vector< max_heap_type > >	_H_k

std::vector< std::vector< int > >	_H_k_ind

std::vector< std::vector< int > >	_H_k_pos

std::vector< std::map< int, int > >	_H_k_map

Detailed Description

sparse matrix implementation for fast modularity clustering algorithm, as described in:

CLAUSET, Aaron; NEWMAN, Mark EJ; MOORE, Cristopher. Finding community structure in very large networks. Physical review E, 2004, 70. Jg., Nr. 6, S. 066111.

The matrix can store explicit zeros, and access to elements is only allowed if they have been set before.

The data structure allows insert, removal and updates of arbitrary elements and keeps track of the maximum element of each row and the whole matrix in an efficient manner.

Insert, removal and update of elements, including book-keeping required to keep track of maximum elements, can be performed in O(n log n).

Definition at line 111 of file SFCLayoutAlgorithm.cpp.

Constructor & Destructor Documentation

◆ MySparseMatrix()

MySparseMatrix::MySparseMatrix	(	int	V,
		std::vector< int >	reserve
	)

inline

Construct sparse matrix with predefined size and number of elements in each row.

Parameters

V	number of nodes
reserve	vector containing size of each row

Definition at line 341 of file SFCLayoutAlgorithm.cpp.

Member Function Documentation

◆ downheap()

void MySparseMatrix::downheap	(	std::vector< max_heap_type > &	H,
		std::vector< int > &	H_ind,
		std::vector< int > &	H_pos,
		int	pos_heap
	)

inlineprivate

Perform a downheap operation after the heap has been changed.

Parameters

H	the elements of the heap
H_ind	the indirect array of the heap
H_pos	the position vector of the heap
pos_heap	the heap position that has changed

Definition at line 218 of file SFCLayoutAlgorithm.cpp.

◆ erase()

void MySparseMatrix::erase	(	int	row,
		int	col
	)

inline

Erase an element from the matrix. The element to be removed must exist.

Parameters

row	the row index of the element
col	the column index of the element

Definition at line 467 of file SFCLayoutAlgorithm.cpp.

◆ heap_empty() [1/2]

bool MySparseMatrix::heap_empty ( std::vector< int > & H_ind )

inlineprivate

Check if a given heap is empty.

Parameters

H_ind the indirect array of the heap

Definition at line 172 of file SFCLayoutAlgorithm.cpp.

◆ heap_empty() [2/2]

bool MySparseMatrix::heap_empty ( )

inline

Check if max-heap of all rows is empty.

Returns: true if the heap is empty, else false

Definition at line 383 of file SFCLayoutAlgorithm.cpp.

◆ heap_erase()

void MySparseMatrix::heap_erase	(	std::vector< max_heap_type > &	H,
		std::vector< int > &	H_ind,
		std::vector< int > &	H_pos,
		int	pos_heap
	)

inlineprivate

Perform a heap erase operation which removes an existing element from the heap.

Parameters

H	the elements of the heap
H_ind	the indirect array of the heap
H_pos	the position vector of the heap
pos_heap	the heap position of the element to remove

Definition at line 305 of file SFCLayoutAlgorithm.cpp.

◆ heap_insert()

void MySparseMatrix::heap_insert	(	std::vector< max_heap_type > &	H,
		std::vector< int > &	H_ind,
		std::vector< int > &	H_pos,
		max_heap_type	h
	)

inlineprivate

Insert a new element into a heap.

Parameters

H	the elements of the heap
H_ind	the indirect array of the heap
H_pos	the position vector of the heap
h	the value of the new heap element

Definition at line 285 of file SFCLayoutAlgorithm.cpp.

◆ heap_size()

int MySparseMatrix::heap_size ( std::vector< int > & H_ind )

inlineprivate

Return size of heap.

Parameters

H_ind the indirect array of the heap

Returns: the number of elements in the heap

Definition at line 181 of file SFCLayoutAlgorithm.cpp.

◆ heap_top()

max_heap_type MySparseMatrix::heap_top ( )

inline

Get the top element of all heaps. The heap must not be empty.

Returns: max_heap_type the maximum element of the matrix

Definition at line 391 of file SFCLayoutAlgorithm.cpp.

◆ heap_update()

void MySparseMatrix::heap_update	(	std::vector< max_heap_type > &	H,
		std::vector< int > &	H_ind,
		std::vector< int > &	H_pos,
		int	pos_heap,
		max_heap_type	h_new
	)

inlineprivate

Perform a heap update operation by changing the value of an existing heap element.

Parameters

H	the elements of the heap
H_ind	the indirect array of the heap
H_pos	the position vector of the heap
pos_heap	the heap position that is updated
h_new	the new value of the heap element

Definition at line 258 of file SFCLayoutAlgorithm.cpp.

◆ innerNonZero()

int MySparseMatrix::innerNonZero ( int row )

inline

Get the number of elements of a row.

Parameters

row	the selected row

Returns: the number of elements in the selected row

Definition at line 513 of file SFCLayoutAlgorithm.cpp.

◆ insert()

void MySparseMatrix::insert	(	int	row,
		int	col,
		float	val
	)

inline

Perform a matrix insert operation. The element to be inserted must not exist.

Parameters

row	the row index of the element
col	the column index of the element
val	the new value for the element

Definition at line 430 of file SFCLayoutAlgorithm.cpp.

◆ print()

void MySparseMatrix::print ( std::ostream & stream )

inline

Print the whole matrix (for debugging).

Parameters

stream print the matrix to this stream

Definition at line 544 of file SFCLayoutAlgorithm.cpp.

◆ print_heap() [1/3]

void MySparseMatrix::print_heap	(	std::vector< max_heap_type > &	H,
		std::vector< int > &	H_ind,
		std::vector< int > &	H_pos
	)

inlineprivate

Print heap (for debugging).

Parameters

H	the elements of the heap
H_ind	the indirect array of the heap
H_pos	the position vector of the heap

Definition at line 145 of file SFCLayoutAlgorithm.cpp.

◆ print_heap() [2/3]

void MySparseMatrix::print_heap ( )

inline

Print heap of maximum elements of each row.

Definition at line 367 of file SFCLayoutAlgorithm.cpp.

◆ print_heap() [3/3]

void MySparseMatrix::print_heap ( int row )

inline

Print heap of a given row.

Parameters

row	the heap to print

Definition at line 375 of file SFCLayoutAlgorithm.cpp.

◆ row()

std::map<int, float>& MySparseMatrix::row ( int r )

inline

Retrieve the container for elements of row The container and its elements must not be modified this way.

Parameters

r	the row to retrieve

Returns: the standard container for row r

Definition at line 504 of file SFCLayoutAlgorithm.cpp.

◆ setZero()

void MySparseMatrix::setZero ( int row )

inline

Remove all elements from a row and update heaps The row to be removed may already be empty.

Parameters

row	the row to remove

Definition at line 521 of file SFCLayoutAlgorithm.cpp.

◆ upheap()

void MySparseMatrix::upheap	(	std::vector< max_heap_type > &	H,
		std::vector< int > &	H_ind,
		std::vector< int > &	H_pos,
		int	pos_heap
	)

inlineprivate

Perform an upheap operation after the heap has been changed.

Parameters

H	the elements of the heap
H_ind	the indirect array of the heap
H_pos	the position vector of the heap
pos_heap	the heap position that has changed

Definition at line 192 of file SFCLayoutAlgorithm.cpp.

Member Data Documentation

◆ _H

std::vector<max_heap_type> MySparseMatrix::_H

private

main heap for largest elements of each row with non-zero elements

Definition at line 119 of file SFCLayoutAlgorithm.cpp.

◆ _H_ind

std::vector<int> MySparseMatrix::_H_ind

private

indirect array of elements in main heap

Definition at line 122 of file SFCLayoutAlgorithm.cpp.

◆ _H_k

std::vector< std::vector<max_heap_type> > MySparseMatrix::_H_k

private

max_heaps for rows with non-zero elements

Definition at line 129 of file SFCLayoutAlgorithm.cpp.

◆ _H_k_ind

std::vector< std::vector< int > > MySparseMatrix::_H_k_ind

private

indirect arrays of elements in heap of each row

Definition at line 132 of file SFCLayoutAlgorithm.cpp.

◆ _H_k_map

std::vector< std::map<int, int> > MySparseMatrix::_H_k_map

private

vector of maps between key value (column) and position in element array

Definition at line 138 of file SFCLayoutAlgorithm.cpp.

◆ _H_k_pos

std::vector< std::vector<int> > MySparseMatrix::_H_k_pos

private

vector of positions of elements in heap of each row

Definition at line 135 of file SFCLayoutAlgorithm.cpp.

◆ _H_pos

std::vector<int> MySparseMatrix::_H_pos

private

vector of positions of heap elements in main heap

Definition at line 125 of file SFCLayoutAlgorithm.cpp.

◆ _row

std::vector< std::map<int, float> > MySparseMatrix::_row

private

main index, organized in row major fashion

Definition at line 115 of file SFCLayoutAlgorithm.cpp.

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

plugins/SFCLayoutAlgorithm.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ MySparseMatrix()

Member Function Documentation

◆ downheap()

◆ erase()

◆ heap_empty() [1/2]

◆ heap_empty() [2/2]

◆ heap_erase()

◆ heap_insert()

◆ heap_size()

◆ heap_top()

◆ heap_update()

◆ innerNonZero()

◆ insert()

◆ print()

◆ print_heap() [1/3]

◆ print_heap() [2/3]

◆ print_heap() [3/3]

◆ row()

◆ setZero()

◆ upheap()

Member Data Documentation

◆ _H

◆ _H_ind

◆ _H_k

◆ _H_k_ind

◆ _H_k_map

◆ _H_k_pos

◆ _H_pos

◆ _row