bipartite_graph.h File Reference

#include <cmr/element.h>
#include <cmr/matrix.h>

Go to the source code of this file.

Functions
CMR_ERROR	CMRchrmatSubmatrixBipartitePath (CMR *cmr, CMR_CHRMAT *matrix, CMR_CHRMAT *transpose, int *rowsGroup, int *columnsGroup, bool *pconnected, CMR_ELEMENT *ppathSource, CMR_ELEMENT *ppathTarget, CMR_ELEMENT *rowsPredecessor, CMR_ELEMENT *columnsPredecessor, int *psum)
	Finds a shortest path between different vertex groups in the bipartite graph of a submatrix of the given matrix. More...

Function Documentation

CMRchrmatSubmatrixBipartitePath()

CMR_ERROR CMRchrmatSubmatrixBipartitePath	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		int *	rowsGroup,
		int *	columnsGroup,
		bool *	pconnected,
		CMR_ELEMENT *	ppathSource,
		CMR_ELEMENT *	ppathTarget,
		CMR_ELEMENT *	rowsPredecessor,
		CMR_ELEMENT *	columnsPredecessor,
		int *	psum
	)

Finds a shortest path between different vertex groups in the bipartite graph of a submatrix of the given matrix.

The bipartite graph of a matrix \( M \) has the rows and columns of as vertices and edges for all nonzeros of \( M \). The rows and columns are assigned to groups, and some shortest path from any nonzero group to any larger nonzero group will be returned. Vertices whose group is negative are ignored.

Run BFS.

Parameters

cmr	CMR environment.
matrix	Matrix.
transpose	Transpose of matrix.
rowsGroup	Array that specifies each row's group.
columnsGroup	Array that specifies each column's group.
pconnected	Pointer for storing whether such a path exists; may be NULL.
ppathSource	Pointer for storing the source row/column; set to invalid if no path exists; may be NULL.
ppathTarget	Pointer for storing the target row/column; set to invalid if no path exists; may be NULL.
rowsPredecessor	Array for storing the predecessor of each row vertex; may be NULL.
columnsPredecessor	Array for storing the predecessor of each column vertex; may be NULL.
psum	Pointer for storing the sum of the edge entries on the path; may be NULL.