General-purpose dense matrix (adjacency, distance, similarity, sociomatrix, etc.), used throughout SocNetV wherever a network needs to be represented or analyzed as an N x M grid of numbers. More...

#include <matrix.h>

Public Member Functions
	Matrix (int rowDim=0, int colDim=0)
	Constructs a rowDim x colDim matrix, all cells zero-initialized. Defaults to 0x0 (an empty matrix) - use resize()/zeroMatrix()/identityMatrix() to size it later.
	Matrix (const Matrix &b)
	Copy constructor: creates a Matrix identical to (an independent copy of) b. Allows the Matrix a = b declaration form.
	~Matrix ()
	Destructor: frees the data buffer and the row-pointer index.
void	clear ()
	Frees this matrix's data buffer and row-pointer index and resets it to 0x0. Called at the start of resize()/identityMatrix()/zeroMatrix()/operator= before they allocate a fresh buffer at the new size.
void	resize (const int m, const int n)
	Resizes this matrix to m x n, discarding any previous contents. All cells start zero-initialized.
qreal	item (int r, int c)
void	setItem (const int r, const int c, const qreal elem)
qreal *	operator[] (const int &r)
void	clearItem (int r, int c)
int	cols ()
int	rows ()
int	size ()
void	findMinMaxValues (qreal &min, qreal &max, bool &hasRealNumbers)
	Scans every cell of this matrix (including the diagonal) and reports the smallest and largest values found, plus whether any cell has a fractional (non-integer) part - used by report writers to decide display precision and, for distance matrices, whether the max value is RAND_MAX (meaning some pair is unreachable). Complexity: O(rows()*cols()).
void	NeighboursNearestFarthest (qreal &min, qreal &max, int &imin, int &jmin, int &imax, int &jmax)
	Like findMinMaxValues(), but skips the diagonal (r==c) and also reports which pair of distinct vertices achieved the min/max - used to find the closest and farthest pair of nodes in a distance/dissimilarity matrix (e.g. by hierarchical clustering, which repeatedly needs "which two clusters are nearest right now"). Complexity: O(rows()*cols()).
void	deleteRowColumn (int i)
	Deletes row erased and column erased from this (square) matrix, shifting every later row/column back by one to close the gap. Complexity: O(rows()*cols()) - rebuilds the whole matrix into a new, smaller buffer (see the comment inside).
void	identityMatrix (int dim)
	Makes this square matrix the identity square matrix I.
void	zeroMatrix (const int m, const int n)
	Makes this matrix the zero matrix of size mxn.
void	fillMatrix (qreal value)
	Fills every cell of this matrix with the given value. Complexity: O(rows()*cols()).
Matrix &	subtractFromI ()
	Replaces this matrix with I - this (the identity matrix minus this matrix), in place. Complexity: O(rows()*cols()).
Matrix &	operator= (Matrix &a)
	Matrix equality/assignment , operator = Allows copying a matrix onto another using b=a where b,a matrices Equals two matrices.
void	sum (Matrix &a, Matrix &b)
	Matrix addition: sets this matrix to a + b, cell by cell. Same result as operator+(), just a different calling interface: c.sum(a,b) instead of c = a + b. Complexity: O(rows()*cols()).
void	operator+= (Matrix &b)
	Adds matrix b to this matrix, in place, cell by cell. Allows A += B. Complexity: O(rows()*cols()).
Matrix &	operator+ (Matrix &b)
	Matrix addition, operator +. Adds this matrix and b (same dimensions) and returns the sum S. Allows S = A + B. Complexity: O(rows()*cols()).
Matrix &	operator- (Matrix &b)
	Matrix subtraction, operator -. Subtracts b (same dimensions) from this matrix and returns the result S. Allows S = A - B. Complexity: O(rows()*cols()).
Matrix &	operator* (Matrix &b)
	Matrix multiplication, operator . Allows P = A B, where A is this (m x n) and B is b (n x p); returns the m x p product P. Complexity: O(mnp).
void	operator*= (Matrix &b)
	Multiplies (right) this m x n matrix with given n x p matrix b, replacing this matrix's own contents with the m x p product. Allows A = B. Complexity: O(mn*p).
void	product (Matrix &A, Matrix &B, bool symmetry=false)
	Matrix Multiplication. Given two matrices A (mxn) and B (nxp), computes their product and stores it into the calling matrix, which becomes an m x p matrix. Allows P.product(A, B).
Matrix &	productSym (Matrix &a, Matrix &b)
	OBSOLETE - no caller found anywhere in the codebase. Was intended to take two (N x N) symmetric matrices a and b and write an upper-triangular product into this matrix (the lower triangle, i>=j, left at zero). Unlike inverseByGaussJordanElimination() (also uncalled, but explicitly kept for cross-checking matrix inversion), there is no stated reason to keep this one - a real candidate for removal. Complexity: O(N^3).
void	swapRows (int rowA, int rowB)
	Swaps row rowA with row rowB of this matrix, element by element. Used by inverseByGaussJordanElimination() and ludcmp() during partial pivoting (moving the row with the largest pivot candidate into the current position improves numerical stability of the elimination). Complexity: O(cols()).
void	multiplyScalar (const qreal &f)
	Multiplies every cell of this matrix, in place, by scalar f. Allows P.multiplyScalar(f). Complexity: O(rows()*cols()).
void	multiplyRow (int row, qreal value)
	Multiplies every element of the given row by value, in place. Complexity: O(cols()).
void	productByVector (qreal in[], qreal out[], const bool &leftMultiply=false)
	Calculates the matrix-by-vector product Ax of this matrix (or the left product xA, if leftMultiply is true). Used by powerIteration()'s inner loop. Complexity: O(rows()*cols()).
Matrix &	pow (int n, bool symmetry=false)
	Returns the n-th power of this matrix (X^n), via exponentiation by squaring (see expBySquaring2()). Used by the walks-matrix code (XM = AM.pow(length)): entry (i,j) of AM^n counts the number of walks of length n from vertex i to vertex j.
Matrix &	expBySquaring2 (Matrix &Y, Matrix &X, int n, bool symmetry=false)
	Recursive algorithm implementing "Exponentiation by squaring". Also known as Fast Modulo Multiplication, this algorithm allows fast computation of a large power n of square matrix X.
qreal	distanceManhattan (qreal x[], qreal y[], int n)
	Helper function, takes to vectors and returns their Manhattan distance (also known as l1 norm, Taxicab or L1 distance) which is the sum of the absolute differences of their coordinates.
qreal	distanceEuclidean (qreal x[], int n)
	Helper function, computes the Euclideian length (also known as L2 distance) of a vector: if x = (x1 x2 ... xn), then \|\|x\|\| = square_root(x1x1 + x2x2 + ... + xn*xn).
void	powerIteration (qreal x[], qreal &xsum, qreal &xmax, int &xmaxi, qreal &xmin, int &xmini, const qreal eps, const int &maxIter, std::function< bool()> cancelCheck=nullptr, qreal *lambdaMax=nullptr)
	Implementation of the Power method which computes the leading eigenvector x of this matrix, that is the eigenvector corresponding to the largest positive eigenvalue. In the process, it also computes min and max values. Used by Eigenvector Centrality (EVC).
Matrix &	degreeMatrix ()
	Returns the degree matrix of this matrix: a diagonal matrix where S(i,i) is the sum of row i (i.e. vertex i's degree, if this is an adjacency matrix). Allows S = A.degreeMatrix(). Used by laplacianMatrix(). Complexity: O(rows()*cols()).
Matrix &	laplacianMatrix ()
	Returns the Laplacian of this matrix: an N x N matrix L = D - A, where D is this matrix's degreeMatrix(). Allows S = A.laplacianMatrix(). Complexity: O(rows()*cols()).
Matrix &	transpose ()
	Returns the transpose of this matrix (T(i,j) = this(j,i)). Allows T = A.transpose(). Complexity: O(rows()*cols()).
Matrix &	cocitationMatrix ()
	Returns the cocitation matrix of this matrix (C = A * A^T). Allows T = A.cocitationMatrix(). C(i,j) counts how many nodes both i and j point to (or, read the other way with the transpose on the other side, how many nodes point to both i and j) - the basis of bibliometric cocitation/coupling analysis. Complexity: O(rows()^3) - transpose() is O(N^2), but the product() call that follows dominates at O(N^3).
Matrix &	inverseByGaussJordanElimination (Matrix &a)
	Inverts matrix A by Gauss-Jordan elimination with partial pivoting: starts this matrix as the identity, then applies the same row operations to both A and this that drive A to the identity - by the time A has become the identity, this matrix has become A's inverse. Input: matrix A. Output: A becomes the identity matrix; this matrix becomes A's inverse and is returned. Complexity: O(n^3).
bool	inverse (Matrix &a, std::function< bool()> cancelCheck=nullptr)
	Computes and returns the inverse of matrix a, into this matrix. Allows b.inverse(a). Decomposes a once via ludcmp() (LU decomposition with partial pivoting), then solves n separate systems - one per column of the identity matrix - via lubksb(), each giving one column of the inverse. This is the "lu" method createMatrixAdjacencyInverse() actually uses (as opposed to inverseByGaussJordanElimination()'s "gauss" method, which has no caller). If a is singular, ludcmp() returns false and this matrix is left unmodified (see the weak-singularity-detection finding, #269, in roadmap_ws5_matrices_modernization.md). Complexity: O(n^3) for the one-time ludcmp() decomposition, plus O(n) calls to lubksb() at O(n^2) each (one per column) - O(n^3) overall, same order as the decomposition itself.
bool	solve (qreal b[])
	Solves the linear system A*x = b, where A is this matrix, in place: b is overwritten with the solution vector x. Allows A.solve(b). Works on a private copy of this matrix (ludcmp() would otherwise decompose - and so overwrite - the caller's own data), via the same ludcmp()+lubksb() pair inverse() uses. Complexity: O(n^3), dominated by the one-time ludcmp() decomposition (lubksb() itself is only O(n^2)).
bool	ludcmp (Matrix &a, const int &n, int indx[], qreal &d, std::function< bool()> cancelCheck=nullptr)
	Given matrix a, it replaces a by the LU decomposition of a rowwise permutation of itself. Used in combination with lubksb to solve linear equations or invert a matrix. Complexity: O(n^3).
void	lubksb (Matrix &a, const int &n, int indx[], qreal b[])
	Solves the set of n linear equations A·X = b, where A nxn matrix decomposed as L·U (L lower triangular and U upper triangular) by forward substitution and backsubstitution. Complexity: O(n^2) - cheap compared to ludcmp()'s O(n^3) decomposition, which is exactly why ludcmp() is only run once and lubksb() can then be reused per right-hand side.
Matrix &	distancesMatrix (const int &metric, const QString varLocation, const bool &diagonal, const bool &considerWeights, std::function< bool()> cancelCheck=nullptr)
	Computes a dissimilarities matrix T: T(i,k) is how different variable i and variable k are, under the chosen metric, treating either this matrix's rows, its columns, or both (concatenated) as the "variables" being compared. Backs the Distances dialog's Euclidean/Manhattan/Jaccard/Hamming/Chebyshev options (see graph_reports.cpp's MATRIX_DISTANCES_* cases).
Matrix &	similarityMatrix (Matrix &AM, const int &measure, const QString varLocation="Rows", const bool &diagonal=false, const bool &considerWeights=true, std::function< bool()> cancelCheck=nullptr)
	Computes a pairwise similarity matrix SCM: SCM(i,k) is how alike variable i and variable k are, under the chosen matching measure, treating either AM's rows, its columns, or both (concatenated) as the "variables" being compared. The mirror image of distancesMatrix() (similarity instead of dissimilarity) - backs the Similarity dialog's simple-matching/Jaccard/Hamming/Cosine options.
Matrix &	pearsonCorrelationCoefficients (Matrix &AM, const QString &varLocation="Rows", const bool &diagonal=false, std::function< bool()> cancelCheck=nullptr)
	Computes the Pearson product-moment correlation coefficient between every pair of variables (AM's rows or its columns, per varLocation), where each variable's "sample" is the sequence of values across the other axis. r ranges -1 (perfect negative correlation) to +1 (perfect positive correlation), with 0 meaning no linear correlation.
bool	printHTMLTable (QTextStream &os, const bool markDiag=false, const bool &plain=false, const bool &printInfinity=true)
	Writes this matrix as an HTML table to os, one row of table cells per matrix row.
bool	printMatrixConsole (bool debug=true)
	Prints this matrix as plain text, one line per row, cells right-aligned to a fixed width. Cells >= RAND_MAX (unreachable/no edge) print as "x" instead of the raw number. A quick way to eyeball a matrix's contents while debugging. Complexity: O(rows()*cols()).
bool	illDefined ()
	Checks whether this matrix is "ill-defined": whether any cell holds RAND_MAX, the sentinel value used elsewhere in the codebase for "infinite"/unreachable (e.g. a distance matrix entry for a disconnected pair).

Private Member Functions
void	rebuildRowPtr ()

Private Attributes
qreal *	m_data
qreal **	m_rowPtr
int	m_rows
int	m_cols

Friends
QTextStream &	operator<< (QTextStream &os, Matrix &m)
	Prints matrix m to given textstream.

Detailed Description

General-purpose dense matrix (adjacency, distance, similarity, sociomatrix, etc.), used throughout SocNetV wherever a network needs to be represented or analyzed as an N x M grid of numbers.

Storage: 2D access on a 1D array, via a precomputed row-pointer index. Every cell lives in one single contiguous allocation (m_data, row-major: row 0's cells, then row 1's, and so on) - one allocation total for the whole grid, rather than one per row. A second, much smaller array (m_rowPtr) records where each row starts inside m_data - one pointer per row, computed once whenever the matrix is built or resized (see rebuildRowPtr()). Reading or writing cell (r,c) is then: look up row r's starting address in m_rowPtr (one array lookup), then step c cells forward from it (one pointer offset) - no multiplication needed at access time, no matter how large the matrix is.

operator[] (the a[i][j] syntax) returns a raw qreal* into m_data via m_rowPtr, because the LU-decomposition/inversion code (ludcmp(), lubksb(), inverse()) needs to modify cells in place with compound assignment (a[i][j] -= ...), which item()/ setItem() (a plain value-returning getter and a separate setter) can't express. Everything else in the codebase reads/writes exclusively through item()/setItem().

Constructor & Destructor Documentation

◆ Matrix() [1/2]

Matrix::Matrix	(	int	rowDim = 0,
		int	colDim = 0 )

Constructs a rowDim x colDim matrix, all cells zero-initialized. Defaults to 0x0 (an empty matrix) - use resize()/zeroMatrix()/identityMatrix() to size it later.

default constructor - default rows = cols = 0

Parameters

rowDim
colDim

◆ Matrix() [2/2]

Matrix::Matrix ( const Matrix & b )

Copy constructor: creates a Matrix identical to (an independent copy of) b. Allows the Matrix a = b declaration form.

Parameters

b

◆ ~Matrix()

Matrix::~Matrix ( )

Destructor: frees the data buffer and the row-pointer index.

Member Function Documentation

◆ clear()

void Matrix::clear ( )

Frees this matrix's data buffer and row-pointer index and resets it to 0x0. Called at the start of resize()/identityMatrix()/zeroMatrix()/operator= before they allocate a fresh buffer at the new size.

◆ clearItem()

void Matrix::clearItem	(	int	r,
		int	c )

inline

◆ cocitationMatrix()

Matrix & Matrix::cocitationMatrix ( )

Returns the cocitation matrix of this matrix (C = A * A^T). Allows T = A.cocitationMatrix(). C(i,j) counts how many nodes both i and j point to (or, read the other way with the transpose on the other side, how many nodes point to both i and j) - the basis of bibliometric cocitation/coupling analysis. Complexity: O(rows()^3) - transpose() is O(N^2), but the product() call that follows dominates at O(N^3).

Returns: Matrix T

◆ cols()

int Matrix::cols ( )

inline

◆ degreeMatrix()

Matrix & Matrix::degreeMatrix ( )

Returns the degree matrix of this matrix: a diagonal matrix where S(i,i) is the sum of row i (i.e. vertex i's degree, if this is an adjacency matrix). Allows S = A.degreeMatrix(). Used by laplacianMatrix(). Complexity: O(rows()*cols()).

Returns: Matrix S

◆ deleteRowColumn()

void Matrix::deleteRowColumn ( int erased )

Deletes row erased and column erased from this (square) matrix, shifting every later row/column back by one to close the gap. Complexity: O(rows()*cols()) - rebuilds the whole matrix into a new, smaller buffer (see the comment inside).

Parameters

erased row/col to delete

◆ distanceEuclidean()

qreal Matrix::distanceEuclidean	(	qreal	x[],
		int	n )

Helper function, computes the Euclideian length (also known as L2 distance) of a vector: if x = (x1 x2 ... xn), then ||x|| = square_root(x1*x1 + x2*x2 + ... + xn*xn).

Parameters

x
n

Returns

◆ distanceManhattan()

qreal Matrix::distanceManhattan	(	qreal	x[],
		qreal	y[],
		int	n )

Helper function, takes to vectors and returns their Manhattan distance (also known as l1 norm, Taxicab or L1 distance) which is the sum of the absolute differences of their coordinates.

Parameters

x
y

Returns

◆ distancesMatrix()

Matrix & Matrix::distancesMatrix	(	const int &	metric,
		const QString	varLocation,
		const bool &	diagonal,
		const bool &	considerWeights,
		std::function< bool()>	cancelCheck = nullptr )

Computes a dissimilarities matrix T: T(i,k) is how different variable i and variable k are, under the chosen metric, treating either this matrix's rows, its columns, or both (concatenated) as the "variables" being compared. Backs the Distances dialog's Euclidean/Manhattan/Jaccard/Hamming/Chebyshev options (see graph_reports.cpp's MATRIX_DISTANCES_* cases).

Parameters

metric	One of the METRIC_* constants declared at the top of matrix.h (Jaccard, Hamming, Euclidean, Manhattan, or Chebyshev - simple matching and Pearson are handled by similarityMatrix()/pearsonCorrelationCoefficients() instead, not here).
varLocation	"Rows", "Columns", or "Both" - which axis holds the variables being compared.
diagonal	If true, i==k / k==j comparisons are included; if false, they're skipped (a variable is never compared against itself).
considerWeights	Currently unused (Q_UNUSED) - accepted for interface symmetry with similarityMatrix()/pearsonCorrelationCoefficients(), which do use it. Complexity: O(N^2 * M), where N is the number of variables being compared and M is the length of each variable's sample (the other axis) - a triple-nested loop, effectively O(N^3) when varLocation is "Rows" or "Columns" (M==N there).

Returns: Matrix T, the dissimilarities matrix.

◆ expBySquaring2()

Matrix & Matrix::expBySquaring2	(	Matrix &	Y,
		Matrix &	X,
		int	n,
		bool	symmetry = false )

Recursive algorithm implementing "Exponentiation by squaring". Also known as Fast Modulo Multiplication, this algorithm allows fast computation of a large power n of square matrix X.

Parameters

Y	must be the Identity matrix on first call
X	the matrix to be powered
n	the power
symmetry

Returns: Matrix&

On first call, parameters must be: Y=I, X the orginal matrix to power and n the power. Returns the power of matrix X to this object. For n > 4 it is more efficient than naively multiplying the base with itself repeatedly: O(log(n)) matrix multiplications instead of O(n), each multiplication itself O(rows()^3).

◆ fillMatrix()

void Matrix::fillMatrix ( qreal value )

Fills every cell of this matrix with the given value. Complexity: O(rows()*cols()).

Parameters

value

◆ findMinMaxValues()

void Matrix::findMinMaxValues	(	qreal &	min,
		qreal &	max,
		bool &	hasRealNumbers )

Scans every cell of this matrix (including the diagonal) and reports the smallest and largest values found, plus whether any cell has a fractional (non-integer) part - used by report writers to decide display precision and, for distance matrices, whether the max value is RAND_MAX (meaning some pair is unreachable). Complexity: O(rows()*cols()).

Parameters

min	Output: the smallest value found.
max	Output: the largest value found.
hasRealNumbers	Output: true if any cell has a non-zero fractional part.

◆ identityMatrix()

void Matrix::identityMatrix ( int dim )

Makes this square matrix the identity square matrix I.

Parameters

dim

◆ illDefined()

bool Matrix::illDefined ( )

Checks whether this matrix is "ill-defined": whether any cell holds RAND_MAX, the sentinel value used elsewhere in the codebase for "infinite"/unreachable (e.g. a distance matrix entry for a disconnected pair).

Returns: true if at least one cell is RAND_MAX or greater; false otherwise. Complexity: O(rows()*cols()) worst case, but returns as soon as one such cell is found.

◆ inverse()

bool Matrix::inverse	(	Matrix &	a,
		std::function< bool()>	cancelCheck = nullptr )

Computes and returns the inverse of matrix a, into this matrix. Allows b.inverse(a). Decomposes a once via ludcmp() (LU decomposition with partial pivoting), then solves n separate systems - one per column of the identity matrix - via lubksb(), each giving one column of the inverse. This is the "lu" method createMatrixAdjacencyInverse() actually uses (as opposed to inverseByGaussJordanElimination()'s "gauss" method, which has no caller). If a is singular, ludcmp() returns false and this matrix is left unmodified (see the weak-singularity-detection finding, #269, in roadmap_ws5_matrices_modernization.md). Complexity: O(n^3) for the one-time ludcmp() decomposition, plus O(n) calls to lubksb() at O(n^2) each (one per column) - O(n^3) overall, same order as the decomposition itself.

Parameters

a

cancelCheck Optional callback, also forwarded to ludcmp() (see its own doc) since ludcmp()'s one-time O(n^3) decomposition is what this method actually spends most of its time in - checked there once per outer-loop iteration, and here once per column, before that column's lubksb() call; if it returns true, the loop stops early and this matrix holds only the columns already solved (the rest are left at whatever resize()/identityMatrix() initialized them to - not a valid inverse). Defaults to nullptr (never cancels), so existing callers are unaffected. Callers must check their own cancellation flag after calling this, not infer it from the return value - ludcmp() returns false identically for "canceled" and "singular", and this method has no way to tell those apart either.

Returns: true if a's inverse was fully computed into this matrix; false if a is singular (Fix #269: now a real relative-tolerance pivot check in ludcmp(), not a weak after-the-fact scan for nonzero entries) or cancelCheck fired, in which case this matrix is left unmodified/partial - callers must not treat its contents as valid without checking the return value first.

◆ inverseByGaussJordanElimination()

Matrix & Matrix::inverseByGaussJordanElimination ( Matrix & A )

Inverts matrix A by Gauss-Jordan elimination with partial pivoting: starts this matrix as the identity, then applies the same row operations to both A and this that drive A to the identity - by the time A has become the identity, this matrix has become A's inverse. Input: matrix A. Output: A becomes the identity matrix; this matrix becomes A's inverse and is returned. Complexity: O(n^3).

Note: Unreachable in the current codebase - createMatrixAdjacencyInverse()'s only caller always passes "lu" (Matrix::inverse()/ludcmp(), below), never "gauss". Kept rather than removed: matrix inversion is numerically sensitive code, and a second independent implementation is useful for cross-checking even while unused.

Parameters

A

Returns: This matrix, now holding A's inverse.

◆ item()

qreal Matrix::item	(	int	r,
		int	c )

inline

◆ laplacianMatrix()

Matrix & Matrix::laplacianMatrix ( )

Returns the Laplacian of this matrix: an N x N matrix L = D - A, where D is this matrix's degreeMatrix(). Allows S = A.laplacianMatrix(). Complexity: O(rows()*cols()).

Returns: Matrix S

◆ lubksb()

void Matrix::lubksb	(	Matrix &	a,
		const int &	n,
		int	indx[],
		qreal	b[] )

Solves the set of n linear equations A·X = b, where A nxn matrix decomposed as L·U (L lower triangular and U upper triangular) by forward substitution and backsubstitution. Complexity: O(n^2) - cheap compared to ludcmp()'s O(n^3) decomposition, which is exactly why ludcmp() is only run once and lubksb() can then be reused per right-hand side.

Given A = L·U we have A · x = (L · U) · x = L · (U · x) = b So, this routine first solves L · y = b for the vector y by forward substitution and then solves U · x = y for the vector x using backsubstitution

Parameters

a	input matrix a as the LU decomposition of A, returned by the routine ludcmp
n	input size of matrix
indx	input vector, records the row permutation, returned by the routine ludcmp
b	input array as the right-hand side vector B, and output with the solution vector X

Returns: :

a, n, and indx are not modified by this routine and can be left in place for successive calls with different right-hand sides b. This routine takes into account the possibility that b will begin with many zero elements, so it is efficient for use in matrix inversion.

Code adapted from Knuth's Numerical Recipes in C, pp 47

◆ ludcmp()

bool Matrix::ludcmp	(	Matrix &	a,
		const int &	n,
		int	indx[],
		qreal &	d,
		std::function< bool()>	cancelCheck = nullptr )

Given matrix a, it replaces a by the LU decomposition of a rowwise permutation of itself. Used in combination with lubksb to solve linear equations or invert a matrix. Complexity: O(n^3).

Parameters

a	input matrix n x n and output arranged as in Knuth's equation (2.3.14)
n	input size of matrix
indx	output vector, records the row permutation effected by the partial pivoting
d	output as ±1 depending on whether the number of row interchanges was even or odd
cancelCheck	Optional callback, checked once per outer-loop iteration in both the O(n^2) scaling pass and the O(n^3) Crout's-method pass; if it returns true, decomposition stops early and this returns false (same as the singular-matrix case - callers must not distinguish the two from this return value alone; inverse()'s post-cancelCheck() logic is what does that, not this). Defaults to nullptr (never cancels), so existing callers are unaffected. Added because ludcmp() is the dominant O(n^3) cost inverse() wraps - without this, inverse()'s own per-column cancelCheck (see below) can never fire in time, since it's only reached after ludcmp() already finished (see WS15 P1, roadmap_ws15_cancellation_progress_unification.md).

Returns: :

Code adapted from Knuth's Numerical Recipes in C, pp 46

◆ multiplyRow()

void Matrix::multiplyRow	(	int	row,
		qreal	value )

Multiplies every element of the given row by value, in place. Complexity: O(cols()).

Parameters

row
value

◆ multiplyScalar()

void Matrix::multiplyScalar ( const qreal & f )

Multiplies every cell of this matrix, in place, by scalar f. Allows P.multiplyScalar(f). Complexity: O(rows()*cols()).

Parameters

f

◆ NeighboursNearestFarthest()

void Matrix::NeighboursNearestFarthest	(	qreal &	min,
		qreal &	max,
		int &	imin,
		int &	jmin,
		int &	imax,
		int &	jmax )

Like findMinMaxValues(), but skips the diagonal (r==c) and also reports which pair of distinct vertices achieved the min/max - used to find the closest and farthest pair of nodes in a distance/dissimilarity matrix (e.g. by hierarchical clustering, which repeatedly needs "which two clusters are nearest right now"). Complexity: O(rows()*cols()).

Parameters

min	Output: the smallest off-diagonal value found.
max	Output: the largest off-diagonal value found.
imin	Output: row of the cell where the minimum was found.
jmin	Output: column of the cell where the minimum was found.
imax	Output: row of the cell where the maximum was found.
jmax	Output: column of the cell where the maximum was found.

◆ operator*()

Matrix & Matrix::operator* ( Matrix & b )

Matrix multiplication, operator *. Allows P = A * B, where A is this (m x n) and B is b (n x p); returns the m x p product P. Complexity: O(m*n*p).

Parameters

b

Returns: Matrix P

◆ operator*=()

void Matrix::operator*= ( Matrix & b )

Multiplies (right) this m x n matrix with given n x p matrix b, replacing this matrix's own contents with the m x p product. Allows A *= B. Complexity: O(m*n*p).

Parameters

b

◆ operator+()

Matrix & Matrix::operator+ ( Matrix & b )

Matrix addition, operator +. Adds this matrix and b (same dimensions) and returns the sum S. Allows S = A + B. Complexity: O(rows()*cols()).

Parameters

b

Returns: Matrix S

◆ operator+=()

void Matrix::operator+= ( Matrix & b )

Adds matrix b to this matrix, in place, cell by cell. Allows A += B. Complexity: O(rows()*cols()).

Parameters

b

◆ operator-()

Matrix & Matrix::operator- ( Matrix & b )

Matrix subtraction, operator -. Subtracts b (same dimensions) from this matrix and returns the result S. Allows S = A - B. Complexity: O(rows()*cols()).

Parameters

b

Returns: Matrix S

◆ operator=()

Matrix & Matrix::operator= ( Matrix & a )

Matrix equality/assignment , operator = Allows copying a matrix onto another using b=a where b,a matrices Equals two matrices.

Parameters

a

Returns

◆ operator[]()

qreal * Matrix::operator[] ( const int & r )

inline

◆ pearsonCorrelationCoefficients()

Matrix & Matrix::pearsonCorrelationCoefficients	(	Matrix &	AM,
		const QString &	varLocation = "Rows",
		const bool &	diagonal = false,
		std::function< bool()>	cancelCheck = nullptr )

Computes the Pearson product-moment correlation coefficient between every pair of variables (AM's rows or its columns, per varLocation), where each variable's "sample" is the sequence of values across the other axis. r ranges -1 (perfect negative correlation) to +1 (perfect positive correlation), with 0 meaning no linear correlation.

Parameters

AM	Input matrix whose rows or columns are being compared.
varLocation	"Rows" or "Columns" - which axis holds the variables being compared.
diagonal	If true, i==k comparisons are included (always r=1, trivially); if false, a variable is never compared against itself.

Returns: Matrix N x N (N = number of variables being compared) of Pearson r values. Complexity: O(N^2 * M), same shape as distancesMatrix() - see its complexity note.

◆ pow()

Matrix & Matrix::pow	(	int	n,
		bool	symmetry = false )

Returns the n-th power of this matrix (X^n), via exponentiation by squaring (see expBySquaring2()). Used by the walks-matrix code (XM = AM.pow(length)): entry (i,j) of AM^n counts the number of walks of length n from vertex i to vertex j.

Parameters

n
symmetry	Passed straight through to expBySquaring2()/product() - see product()'s own
symmetry	for what it does.

Returns: This matrix, raised to the n-th power. Complexity: O(log(n)) matrix multiplications, each O(rows()^3) - see expBySquaring2().

◆ powerIteration()

void Matrix::powerIteration	(	qreal	x[],
		qreal &	xsum,
		qreal &	xmax,
		int &	xmaxi,
		qreal &	xmin,
		int &	xmini,
		const qreal	eps,
		const int &	maxIter,
		std::function< bool()>	cancelCheck = nullptr,
		qreal *	lambdaMax = nullptr )

Implementation of the Power method which computes the leading eigenvector x of this matrix, that is the eigenvector corresponding to the largest positive eigenvalue. In the process, it also computes min and max values. Used by Eigenvector Centrality (EVC).

Meaning: start from any vector x, repeatedly multiply by the matrix and rescale back to unit length - the vector converges to the eigenvector for the matrix's largest eigenvalue (lambda_max), which is exactly the vector eigenvector centrality reports.

We use C arrays instead of std::vectors or anything else, as we know from start the size (n) of vectors x and tmp This approach is faster than using std::vector when n > 1000

Note: Uses n = rows() throughout (for tmp's size, and as both the row and column count passed to productByVector()/distanceEuclidean()/distanceManhattan()) - correct only for square matrices. Unlike pow(), this method does not check rows()==cols() itself; it relies on the caller (centralityEigenvector()) only ever passing a square (adjacency) matrix. Complexity: O(maxIter * n^2) - each iteration is one O(n^2) productByVector() call plus a handful of O(n) passes; iterates until the vector's Manhattan distance to its previous value drops below eps, or maxIter is reached.

Parameters

x
xsum
xmax
xmaxi
xmin
xmini
eps
maxIter
cancelCheck	Optional callback checked once per iteration; if it returns true, the loop stops early (x/xsum/xmax/xmin reflect the last completed iteration, not a full result). Defaults to nullptr (never cancels), so existing callers are unaffected.
lambdaMax	Optional out param: the largest eigenvalue itself, read off from the pre-normalization vector length on the final iteration (norm(Ax) ~= lambda_max once x has converged to unit length). Correctly reports exactly 0 for a nilpotent matrix (any directed acyclic graph - no cycles at all), meaning "no convergence bound, any value works" - this is the genuine mathematical answer, not a numerical-error placeholder (a symmetric/undirected adjacency matrix can never be nilpotent unless it's the zero matrix, so this only ever arises for directed graphs). Callers that only need the eigenvector (e.g. centralityEigenvector()) can leave this nullptr; callers that need to validate a convergence bound like Katz's alpha < 1/lambda_max need it.

◆ printHTMLTable()

bool Matrix::printHTMLTable	(	QTextStream &	os,
		const bool	markDiag = false,
		const bool &	plain = false,
		const bool &	printInfinity = true )

Writes this matrix as an HTML table to os, one row of table cells per matrix row.

Warning: Do not use on a network with disabled/deleted nodes - row/column headers are generated from a running counter, not the real vertex number, so they go out of sync with actual actor numbers once any vertex has been deleted.

Parameters

os	Output stream to write the HTML table to.
markDiag	If true, diagonal cells get distinct styling.
plain	If true, skip HTML styling/highlighting (a plain table).
printInfinity	If true, RAND_MAX cells print as the infinity symbol (unreachable/no edge) instead of the raw number.

Returns: true on success. Complexity: O(rows()*cols()).

◆ printMatrixConsole()

bool Matrix::printMatrixConsole ( bool debug = true )

Prints this matrix as plain text, one line per row, cells right-aligned to a fixed width. Cells >= RAND_MAX (unreachable/no edge) print as "x" instead of the raw number. A quick way to eyeball a matrix's contents while debugging. Complexity: O(rows()*cols()).

Parameters

debug If true, print to stderr; if false, print to stdout.

Returns: true.

◆ product()

void Matrix::product	(	Matrix &	A,
		Matrix &	B,
		bool	symmetry = false )

Matrix Multiplication. Given two matrices A (mxn) and B (nxp), computes their product and stores it into the calling matrix, which becomes an m x p matrix. Allows P.product(A, B).

Parameters

A
B
symmetry	If true, the result is assumed symmetric (P(i,j)==P(j,i)): only the upper triangle (i<=j) is actually computed, and each computed value is mirrored directly into its (j,i) counterpart instead of being recomputed - roughly half the multiply-accumulate work of the general case. Used where A and B are already known to be symmetric (e.g. cocitationMatrix(), which multiplies a matrix by its own transpose). Complexity: O(mnp), or roughly half that with symmetry=true.

◆ productByVector()

void Matrix::productByVector	(	qreal	in[],
		qreal	out[],
		const bool &	leftMultiply = false )

Calculates the matrix-by-vector product Ax of this matrix (or the left product xA, if leftMultiply is true). Used by powerIteration()'s inner loop. Complexity: O(rows()*cols()).

Parameters

in	input array/vector, cols() elements (rows(), if leftMultiply).
out	output array, rows() elements (cols(), if leftMultiply).
leftMultiply

◆ productSym()

Matrix & Matrix::productSym	(	Matrix &	a,
		Matrix &	b )

OBSOLETE - no caller found anywhere in the codebase. Was intended to take two (N x N) symmetric matrices a and b and write an upper-triangular product into this matrix (the lower triangle, i>=j, left at zero). Unlike inverseByGaussJordanElimination() (also uncalled, but explicitly kept for cross-checking matrix inversion), there is no stated reason to keep this one - a real candidate for removal. Complexity: O(N^3).

Parameters

a
b

◆ rebuildRowPtr()

void Matrix::rebuildRowPtr ( )

inlineprivate

◆ resize()

void Matrix::resize	(	const int	m,
		const int	n )

Resizes this matrix to m x n, discarding any previous contents. All cells start zero-initialized.

Parameters

m	New row count.
n	New column count.

◆ rows()

int Matrix::rows ( )

inline

◆ setItem()

void Matrix::setItem	(	const int	r,
		const int	c,
		const qreal	elem )

inline

◆ similarityMatrix()

Matrix & Matrix::similarityMatrix	(	Matrix &	AM,
		const int &	measure,
		const QString	varLocation = "Rows",
		const bool &	diagonal = false,
		const bool &	considerWeights = true,
		std::function< bool()>	cancelCheck = nullptr )

Computes a pairwise similarity matrix SCM: SCM(i,k) is how alike variable i and variable k are, under the chosen matching measure, treating either AM's rows, its columns, or both (concatenated) as the "variables" being compared. The mirror image of distancesMatrix() (similarity instead of dissimilarity) - backs the Similarity dialog's simple-matching/Jaccard/Hamming/Cosine options.

Parameters

AM	Input matrix whose rows/columns/both are being compared.
measure	One of the METRIC_* constants (simple matching, Jaccard, Hamming, Cosine - Pearson is handled separately by pearsonCorrelationCoefficients()).
varLocation	"Rows", "Columns", or "Both" - which axis holds the variables being compared.
diagonal	If true, i==k comparisons are included; if false, a variable is never compared against itself.
considerWeights	Whether edge weights factor into the match/mismatch decision.

Returns: Matrix SCM, N x N (N = number of variables being compared), with a similarity score for every pair. Complexity: O(N^2 * M), same shape as distancesMatrix() - see its complexity note.

◆ size()

int Matrix::size ( )

inline

◆ solve()

bool Matrix::solve ( qreal b[] )

Solves the linear system A*x = b, where A is this matrix, in place: b is overwritten with the solution vector x. Allows A.solve(b). Works on a private copy of this matrix (ludcmp() would otherwise decompose - and so overwrite - the caller's own data), via the same ludcmp()+lubksb() pair inverse() uses. Complexity: O(n^3), dominated by the one-time ludcmp() decomposition (lubksb() itself is only O(n^2)).

Parameters

b	Right-hand-side vector on input, solution vector x on output.

Returns: false if A is singular (b is left unmodified) or the working copy couldn't be allocated; true on success.

◆ subtractFromI()

Matrix & Matrix::subtractFromI ( )

Replaces this matrix with I - this (the identity matrix minus this matrix), in place. Complexity: O(rows()*cols()).

Returns: this, now holding I - this.

◆ sum()

void Matrix::sum	(	Matrix &	a,
		Matrix &	b )

Matrix addition: sets this matrix to a + b, cell by cell. Same result as operator+(), just a different calling interface: c.sum(a,b) instead of c = a + b. Complexity: O(rows()*cols()).

Parameters

a
b

◆ swapRows()

void Matrix::swapRows	(	int	rowA,
		int	rowB )

Swaps row rowA with row rowB of this matrix, element by element. Used by inverseByGaussJordanElimination() and ludcmp() during partial pivoting (moving the row with the largest pivot candidate into the current position improves numerical stability of the elimination). Complexity: O(cols()).

Parameters

rowA
rowB

◆ transpose()

Matrix & Matrix::transpose ( )

Returns the transpose of this matrix (T(i,j) = this(j,i)). Allows T = A.transpose(). Complexity: O(rows()*cols()).

Returns: Matrix T

◆ zeroMatrix()

void Matrix::zeroMatrix	(	const int	m,
		const int	n )

Makes this matrix the zero matrix of size mxn.

Parameters

m
n

◆ operator<<

QTextStream & operator<<	(	QTextStream &	os,
		Matrix &	m )

friend

Prints matrix m to given textstream.

Parameters

os
m

Returns

Member Data Documentation

◆ m_cols

int Matrix::m_cols

private

◆ m_data

qreal* Matrix::m_data

private

◆ m_rowPtr

qreal** Matrix::m_rowPtr

private

◆ m_rows

int Matrix::m_rows

private

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

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ Matrix() [1/2]

◆ Matrix() [2/2]

◆ ~Matrix()

Member Function Documentation

◆ clear()

◆ clearItem()

◆ cocitationMatrix()

◆ cols()

◆ degreeMatrix()

◆ deleteRowColumn()

◆ distanceEuclidean()

◆ distanceManhattan()

◆ distancesMatrix()

◆ expBySquaring2()

◆ fillMatrix()

◆ findMinMaxValues()

◆ identityMatrix()

◆ illDefined()

◆ inverse()

◆ inverseByGaussJordanElimination()

◆ item()

◆ laplacianMatrix()

◆ lubksb()

◆ ludcmp()

◆ multiplyRow()

◆ multiplyScalar()

◆ NeighboursNearestFarthest()

◆ operator*()

◆ operator*=()

◆ operator+()

◆ operator+=()

◆ operator-()

◆ operator=()

◆ operator[]()

◆ pearsonCorrelationCoefficients()

◆ pow()

◆ powerIteration()

◆ printHTMLTable()

◆ printMatrixConsole()

◆ product()

◆ productByVector()

◆ productSym()

◆ rebuildRowPtr()

◆ resize()

◆ rows()

◆ setItem()

◆ similarityMatrix()

◆ size()

◆ solve()

◆ subtractFromI()

◆ sum()

◆ swapRows()

◆ transpose()

◆ zeroMatrix()

Friends And Related Symbol Documentation

◆ operator<<

Member Data Documentation

◆ m_cols

◆ m_data

◆ m_rowPtr

◆ m_rows