PaStiX Handbook: Graph

Functions to generate and manipulate the graph structure. More...

Macros
#define	assert_graph(_graph_)

Graph basic subroutines
int	graphPrepare (pastix_data_t pastix_data, const spmatrix_t spm, pastix_graph_t **graph)
	This routine initializes the graph. More...

void	graphBase (pastix_graph_t *graph, pastix_int_t baseval)
	Rebase the graph to the given value. More...

void	graphExit (pastix_graph_t *graph)
	Free the content of the graph structure. More...

void	graphInitEmpty (pastix_graph_t *graph, PASTIX_Comm comm)
	Initialize an empty graph. More...

Graph IO subroutines
void	graphLoad (const pastix_data_t pastix_data, pastix_graph_t graph)
	Load a graph from a file. More...

void	graphSave (pastix_data_t pastix_data, const pastix_graph_t graph)
	Save a graph to file. More...

Graph manipulation subroutines
int	graphCopy (pastix_graph_t graphdst, const pastix_graph_t graphsrc)
	This routine copy a given ordering in a new one. More...

int	graphSpm2Graph (pastix_graph_t graph, const spmatrix_t spm)
	This routine build a graph thanks to an spm;. More...

void	graphSort (pastix_graph_t *graph)
	This routine sortes the subarray of edges of each vertex. More...

void	graphNoDiag (pastix_graph_t *graph)
	This routine removes the diagonal edges from a centralized graph. More...

int	graphSymmetrize (pastix_graph_t *graph)
	Symmetrize a given graph. More...

int	graphUpdateComputedFields (pastix_graph_t *graph)
	Update dofs, nnz, nnzexp, gnnz, n, nexp, gN of a given graph. More...

int	graphScatterInPlace (pastix_graph_t *graph, PASTIX_Comm comm)
	This routine scatter a graph from node root to the other nodes. More...

int	graphGatherInPlace (pastix_graph_t *graph)
	This routine gather a distributed graph on each note in place. More...

int	graphIsolate (const pastix_graph_t ingraph, pastix_graph_t outgraph, pastix_int_t isolate_n, pastix_int_t isolate_list, pastix_int_t new_perm, pastix_int_t *new_invp)
	Isolate a subset of vertices from a given graph. More...

int	graphApplyPerm (const pastix_graph_t graphA, const pastix_int_t perm, pastix_graph_t *graphPA)

int	graphIsolateRange (const pastix_graph_t graph, const pastix_order_t order, pastix_graph_t *out_graph, pastix_int_t fnode, pastix_int_t lnode, pastix_int_t distance)
	Isolate the subgraph associated to a range of unknowns in the permuted graph. More...

void	graphComputeProjection (const pastix_graph_t graph, const int vertlvl, pastix_order_t order, const pastix_graph_t subgraph, pastix_order_t suborder, pastix_int_t fnode, pastix_int_t lnode, pastix_int_t sn_level, pastix_int_t distance, pastix_int_t maxdepth, pastix_int_t maxwidth, pastix_int_t depthsze)

pastix_int_t	graphIsolateConnectedComponents (const pastix_graph_t graph, pastix_int_t comp_vtx, pastix_int_t *comp_sze)

int	graphComputeKway (const pastix_graph_t graph, pastix_order_t order, pastix_int_t peritab, pastix_int_t comp_nbr, pastix_int_t comp_sze, pastix_int_t comp_vtx, pastix_int_t comp_id, pastix_int_t nbpart)
	Compute the K-way partition of a given set of unknowns. More...

pastix_int_t *	graphGetWeights (const pastix_graph_t *graph)
	Build the vertex weight array out of the dof array. More...

Detailed Description

Functions to generate and manipulate the graph structure.

This module provides the set of function to prepare the graph structure associated to a given sparse matrix. It is possible to symmetrize a graph, to extract a subgraph and to apply a new permutation.

Macro Definition Documentation

◆ assert_graph

#define assert_graph ( _graph_ )

Value:

    do {                                                \
        assert( (_graph_)->fmttype == SpmCSC     );     \
        assert( (_graph_)->flttype == SpmPattern );     \
        assert( (_graph_)->values  == NULL       );     \
    } while (0)

Definition at line 24 of file graph.c.

Function Documentation

◆ graphPrepare()

int graphPrepare	(	pastix_data_t *	pastix_data,
		const spmatrix_t *	spm,
		pastix_graph_t **	graph
	)

This routine initializes the graph.

This routine will also symmetrize the graph, remove duplicates, remove the diagonal elements, and keep only the lower part.

Parameters

[in,out]	pastix_data	The pointer to the solver instance. On exit, the fields n, cols, rows and loc2glob are initialized for future steps of the solver.
[in]	spm	The initial user spm that needs to be transformed in a correct graph for future call in ordering and symbolic factorization routines.
[out]	graph	On exit, the pointer to the allocated graph structure is returned. The graph can then be used with ordering and symbol factorization tools. The graph is symmetrized without diagonal elements and rows array is sorted.

Return values

PASTIX_SUCCESS	on success,
!0	on failure.

Definition at line 115 of file graph_prepare.c.

References graphLoad(), graphNoDiag(), graphSort(), graphSpm2Graph(), graphSymmetrize(), IPARM_IO_STRATEGY, IPARM_VERBOSE, PASTIX_SUCCESS, PastixIOLoadGraph, and PastixVerboseNo.

◆ graphBase()

void graphBase	(	pastix_graph_t *	graph,
		pastix_int_t	baseval
	)

Rebase the graph to the given value.

Parameters

[in,out]	graph	The graph to rebase.
[in]	baseval	The base value to use in the graph (0 or 1).

Definition at line 100 of file graph.c.

Referenced by graphIsolateRange(), ocpts_graph_init(), ocs_graph_init(), orderAmalgamate(), and orderComputePTScotch().

◆ graphExit()

void graphExit ( pastix_graph_t * graph )

Free the content of the graph structure.

Parameters

[in,out] graph The pointer graph structure to free.

Definition at line 71 of file graph.c.

Referenced by graphComputeKway(), and pastixFinalize().

◆ graphInitEmpty()

void graphInitEmpty	(	pastix_graph_t *	graph,
		PASTIX_Comm	comm
	)

Initialize an empty graph.

Parameters

[in,out]	graph	The empty graph to init.
[in]	comm	The MPI communicator used for the graph.

Definition at line 46 of file graph.c.

References graphUpdateComputedFields().

Referenced by graphIsolate().

◆ graphLoad()

void graphLoad	(	const pastix_data_t *	pastix_data,
		pastix_graph_t *	graph
	)

Load a graph from a file.

The file is named 'graphname' in the local directory.

Parameters

[in]	pastix_data	The pointer to the solver instance to get options as rank, communicators, ...
[in,out]	graph	The graph structure to store the loaded graph. The graph is read from the file named by the environment variable PASTIX_FILE_GRAPH, and if PASTIX_FILE_GRAPH is not defined, the default filename "graphname" in the local directory is used.

Definition at line 45 of file graph_io.c.

Referenced by graphPrepare().

◆ graphSave()

void graphSave	(	pastix_data_t *	pastix_data,
		const pastix_graph_t *	graph
	)

Save a graph to file.

The file is named 'graphgen' in the local directory.

Parameters

[in]	pastix_data	The pointer to the solver instance to get options as rank, communicators, ...
[in]	graph	The graph structure to store the loaded graph. The graph is written to the file named by the environment variable PASTIX_FILE_GRAPH, and if PASTIX_FILE_GRAPH is not defined, the default filename "graphname" in the local directory is used.

Definition at line 102 of file graph_io.c.

References pastix_fname(), and pastix_gendirectories().

◆ graphCopy()

int graphCopy	(	pastix_graph_t *	graphdst,
		const pastix_graph_t *	graphsrc
	)

This routine copy a given ordering in a new one.

This function copies a graph structure into another one. If all subpointers are NULL, then they are all allocated and contains the original graphsrc values on exit. If one or more array pointers are not NULL, then, only those are copied to the graphdst structure.

Parameters

	[output]	graphdst The destination graph. Must be allocated on entry.
[in]	graphsrc	The source graph

Return values

PASTIX_SUCCESS	on successful exit
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect.

Definition at line 149 of file graph.c.

References PASTIX_ERR_BADPARAMETER.

Referenced by graphIsolate(), and graphIsolateRange().

◆ graphSpm2Graph()

int graphSpm2Graph	(	pastix_graph_t *	graph,
		const spmatrix_t *	spm
	)

This routine build a graph thanks to an spm;.

This function copies an spm structure into a graph one. If all subpointers are NULL, then they are all allocated and contains the original spm values on exit. If one or more array pointers are not NULL, then, only those are copied to the graphdst structure. We will take care that our graph does not contain coefficients, therefore has SpmPattern floating type and is a SpmCSC format type.

Parameters

[in,out]	graph	The destination graph.
[in]	graphsrc	The source Sparse Matrix.

Return values

PASTIX_SUCCESS	on successful exit
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect.

Definition at line 380 of file graph.c.

References PASTIX_ERR_BADPARAMETER, and PASTIX_SUCCESS.

Referenced by graphPrepare().

◆ graphSort()

void graphSort ( pastix_graph_t * graph )

This routine sortes the subarray of edges of each vertex.

WARNING: The sort is always performed, do not call this routine when it is not required.

Parameters

[in,out] graph On entry, the pointer to the graph structure. On exit, the same graph with subarrays of edges sorted by ascending order.

Definition at line 283 of file graph.c.

Referenced by graphPrepare().

◆ graphNoDiag()

void graphNoDiag ( pastix_graph_t * graph )

This routine removes the diagonal edges from a centralized graph.

Parameters

[in,out] graph On entry, the pointer to the graph structure with possible diagonal edges (i,i). On exit, all entries of type (i,i) are removed from the graph.

Definition at line 37 of file graph_prepare.c.

References graphUpdateComputedFields().

Referenced by graphPrepare().

◆ graphSymmetrize()

int graphSymmetrize ( pastix_graph_t * graph )

Symmetrize a given graph.

Parameters

[in,out] graph The initialized graph structure that will be symmetrized.

Return values

PASTIX_SUCCESS	on success,
PASTIX_ERR_BADPARAMETER	if incorrect parameters are given.

Definition at line 308 of file graph.c.

References PASTIX_ERR_BADPARAMETER.

Referenced by graphPrepare().

◆ graphUpdateComputedFields()

int graphUpdateComputedFields ( pastix_graph_t * graph )

Update dofs, nnz, nnzexp, gnnz, n, nexp, gN of a given graph.

Parameters

[in,out] graph The initialized graph structure that will be updated.

Return values

PASTIX_SUCCESS	on success,
PASTIX_ERR_BADPARAMETER	if incorrect parameters are given.

Definition at line 339 of file graph.c.

References PASTIX_ERR_BADPARAMETER.

Referenced by graph_isolate_compress(), graphInitEmpty(), graphIsolateRange(), and graphNoDiag().

◆ graphScatterInPlace()

int graphScatterInPlace	(	pastix_graph_t *	graph,
		PASTIX_Comm	comm
	)

This routine scatter a graph from node root to the other nodes.

Parameters

[in,out]	graph	On entry, the graph to scatter. On exit, the scattered graph
[in]	comm	MPI communicator.

Return values

1	if the graph has been scattered, 0 if untouched

Definition at line 192 of file graph.c.

◆ graphGatherInPlace()

int graphGatherInPlace ( pastix_graph_t * graph )

This routine gather a distributed graph on each note in place.

Parameters

[in]	graph	On entry, the distributed graph. On exit, the gathered graph
[in]	root	The root where we want to gather the graph

Return values

1	if the graph has been gathered, 0 if untouched

Definition at line 240 of file graph.c.

◆ graphIsolate()

int graphIsolate	(	const pastix_graph_t *	ingraph,
		pastix_graph_t *	outgraph,
		pastix_int_t	isolate_n,
		pastix_int_t *	isolate_list,
		pastix_int_t **	new_perm,
		pastix_int_t **	new_invp
	)

Isolate a subset of vertices from a given graph.

Return a new graph cleaned from those vertices.

Parameters

[in]	n	The number of columns of the original GRAPH matrix.
[in]	colptr	Array of size n+1. Index of first element of each column in rowptr array.
[in]	rowptr	Array of size nnz = colptr[n] - colptr[0]. Rows of each non zero entries.
[in]	isolate_n	The number of columns to isolate from the original graph.
[in,out]	isolate_list	Array of size isolate_n. List of columns to isolate. On exit, the list is sorted by ascending indexes. Must be based as the graph.
[out]	new_colptr	Array of size n-isolate_n+1. Index of first element of each column in rows array for the new graph. If new_colptr == NULL, nothing is returned, otherwise the pointer to the allocated structure based as the input colptr.
[out]	new_rowptr	Array of size new_nnz = (new_colptr)[n] - (new_colptr)[0]. Rows of each non zero entries for the new graph. If new_rows == NULL, nothing is returned, otherwise the pointer to the allocated structure based as the input rows.
[out]	new_perm	Array of size n-isolate_n. Contains permutation generated to isolate the columns at the end of the graph that is 0-based. If new_perm == NULL, nothing is returned, otherwise the pointer to the allocated structure.
[out]	new_invp	Array of size n-isolate_n. Contains the inverse permutation generated to isolate the columns at the end of the graph that is 0-based. If new_invp == NULL, nothing is returned, otherwise the pointer to the allocated structure.

Return values

PASTIX_SUCCESS	on success,
PASTIX_ERR_ALLOC	if allocation went wrong,
PASTIX_ERR_BADPARAMETER	if incorrect parameters are given.

Definition at line 287 of file graph_isolate.c.

References graph_isolate_assign_ptr(), graph_isolate_compress(), graph_isolate_everything(), graph_isolate_permutations(), graphCopy(), graphInitEmpty(), PASTIX_ERR_BADPARAMETER, and PASTIX_SUCCESS.

◆ graphIsolateRange()

int graphIsolateRange	(	const pastix_graph_t *	graph,
		const pastix_order_t *	order,
		pastix_graph_t *	out_graph,
		pastix_int_t	fnode,
		pastix_int_t	lnode,
		pastix_int_t	distance
	)

Isolate the subgraph associated to a range of unknowns in the permuted graph.

This routine isolates a continuous subset of vertices from a given graph, and returns a new graph made of those vertices and internal connexions. Extra edges are created between vertices if they are connected through a halo at a distance d given in parameter.

Parameters

[in]	graph	The original graph associated from which vertices and edges must be extracted.
[in]	order	The ordering structure associated to the graph.
[in,out]	out_graph	The extracted graph. If the graph is allocated, it is freed before usage. On exit, contains the subgraph of the vertices invp[fnode] to invp[lnode-1].
[in]	fnode	The index of the first node to extract in the inverse permutation.
[in]	lnode	The index (+1) of the last node to extract in the inverse permutation.
[in]	distance	Distance considered in number of edges to create an edge in isolated graph.

Return values

PASTIX_SUCCESS	on success.
PASTIX_ERR_ALLOC	if allocation went wrong.
PASTIX_ERR_BADPARAMETER	if incorrect parameters are given.

Definition at line 462 of file graph_isolate.c.

References pastix_order_s::cblknbr, extendint_Exit(), extendint_Init(), graph_iRange_fill_outptr(), graphBase(), graphCopy(), graphUpdateComputedFields(), PASTIX_ERR_BADPARAMETER, and PASTIX_SUCCESS.

Referenced by graphComputeKway(), orderDraw(), and orderSupernodes().

◆ graphComputeKway()

int graphComputeKway	(	const pastix_graph_t *	graph,
		pastix_order_t *	order,
		pastix_int_t *	peritab,
		pastix_int_t *	comp_nbr,
		pastix_int_t *	comp_sze,
		pastix_int_t *	comp_vtx,
		pastix_int_t	comp_id,
		pastix_int_t	nbpart
	)

Compute the K-way partition of a given set of unknowns.

Take a graph with its own associated ordering, and generates a k-way partition of the graph.

Parameters

[in]	graph	The pointer to the graph structure on wich to apply the K-way partitioning on the subcomponent comp_id.
[in,out]	order	The order structure associated to the given graph. On entry, the structure is initialized through previous operation on the graph, and on exit vertices are reordered by components in the K-way partitioning.
[in,out]	peritab	Array of size n. Pointer to the peritab array of the global graph in which the subproblem belongs to. This array is updated according to the eprmutation performed for the K-way partitioning.
[in,out]	comp_nbr	On entry the number of components in the graph. On exit, the new number of components after K-way partitioning.
[in,out]	comp_size	The size of each components in the graph. On entry, only the first comp_nbr sizes are initialized, others are 0. On exit, the array is extended to store the size of the new components generated by the k-way partitionning.
[in,out]	comp_vtx	Array of size n that hold the index of the component for each vertex of the graph.
[in]	comp_id	The index of the component that must be split by K-way paritioning.
[in]	nbpart	The number of part wanted in the k-way partitioning.

Return values

PASTIX_SUCCESS	on success,
PASTIX_ERR_UNKNOWN	if something went wrong with Scotch.

Definition at line 80 of file graph_compute_kway.c.

References pastix_order_s::baseval, graphExit(), graphIsolateRange(), PASTIX_ERR_BADPARAMETER, PASTIX_ERR_UNKNOWN, PASTIX_SUCCESS, pastix_order_s::peritab, and pastix_order_s::permtab.

◆ graphGetWeights()

pastix_int_t * graphGetWeights ( const pastix_graph_t * graph )

Build the vertex weight array out of the dof array.

Parameters

[in] graph Pointer to the graph structure.

Return values

The	vertex weight array if graph->dof != 1, NULL otherwise.

Definition at line 432 of file graph.c.

Referenced by ocpts_graph_init(), and ocs_graph_init().

Macros

Graph basic subroutines

Graph IO subroutines

Graph manipulation subroutines

Detailed Description

Macro Definition Documentation

◆ assert_graph

Function Documentation

◆ graphPrepare()

◆ graphBase()

◆ graphExit()

◆ graphInitEmpty()

◆ graphLoad()

◆ graphSave()

◆ graphCopy()

◆ graphSpm2Graph()

◆ graphSort()

◆ graphNoDiag()

◆ graphSymmetrize()

◆ graphUpdateComputedFields()

◆ graphScatterInPlace()

◆ graphGatherInPlace()

◆ graphIsolate()

◆ graphIsolateRange()

◆ graphComputeKway()

◆ graphGetWeights()