PaStiX Handbook
6.2.1

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...  
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  graphIsolate (pastix_int_t n, const pastix_int_t *colptr, const pastix_int_t *rowptr, pastix_int_t isolate_n, pastix_int_t *isolate_list, pastix_int_t **new_colptr, pastix_int_t **new_rowptr, 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 Kway partition of a given set of unknowns. More...  
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.
#define assert_graph  (  _graph_  ) 
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.
[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. 
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.
void graphBase  (  pastix_graph_t *  graph, 
pastix_int_t  baseval  
) 
Rebase the graph to the given value.
[in,out]  graph  The graph to rebase. 
[in]  baseval  The base value to use in the graph (0 or 1). 
Definition at line 70 of file graph.c.
Referenced by graphIsolateRange(), and pastixOrderAmalgamate().
void graphExit  (  pastix_graph_t *  graph  ) 
Free the content of the graph structure.
[in,out]  graph  The pointer graph structure to free. 
Definition at line 41 of file graph.c.
Referenced by graphComputeKway(), and pastixFinalize().
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.
[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().
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.
[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().
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.
[in,out]  graphdst  The destination graph 
[in]  graphsrc  The source graph 
PASTIX_SUCCESS  on successful exit 
PASTIX_ERR_BADPARAMETER  if one parameter is incorrect. 
Definition at line 125 of file graph.c.
References PASTIX_ERR_BADPARAMETER.
Referenced by graphIsolateRange().
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.
[in,out]  graph  The destination graph. 
[in]  graphsrc  The source Sparse Matrix. 
PASTIX_SUCCESS  on successful exit 
PASTIX_ERR_BADPARAMETER  if one parameter is incorrect. 
Definition at line 271 of file graph.c.
References PASTIX_ERR_BADPARAMETER, and PASTIX_SUCCESS.
Referenced by graphPrepare().
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.
[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 174 of file graph.c.
Referenced by graphPrepare().
void graphNoDiag  (  pastix_graph_t *  graph  ) 
This routine removes the diagonal edges from a centralized graph.
[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().
int graphSymmetrize  (  pastix_graph_t *  graph  ) 
Symmetrize a given graph.
[in,out]  graph  The initialized graph structure that will be symmetrized. 
PASTIX_SUCCESS  on success, 
PASTIX_ERR_BADPARAMETER  if incorrect parameters are given. 
Definition at line 199 of file graph.c.
References PASTIX_ERR_BADPARAMETER.
Referenced by graphPrepare().
int graphUpdateComputedFields  (  pastix_graph_t *  graph  ) 
Update dofs, nnz, nnzexp, gnnz, n, nexp, gN of a given graph.
[in,out]  graph  The initialized graph structure that will be updated. 
PASTIX_SUCCESS  on success, 
PASTIX_ERR_BADPARAMETER  if incorrect parameters are given. 
Definition at line 230 of file graph.c.
References PASTIX_ERR_BADPARAMETER.
Referenced by graphIsolateRange(), and graphNoDiag().
int graphIsolate  (  pastix_int_t  n, 
const pastix_int_t *  colptr,  
const pastix_int_t *  rowptr,  
pastix_int_t  isolate_n,  
pastix_int_t *  isolate_list,  
pastix_int_t **  new_colptr,  
pastix_int_t **  new_rowptr,  
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.
[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 nisolate_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 nisolate_n. Contains permutation generated to isolate the columns at the end of the graph that is 0based. If new_perm == NULL, nothing is returned, otherwise the pointer to the allocated structure. 
[out]  new_invp  Array of size nisolate_n. Contains the inverse permutation generated to isolate the columns at the end of the graph that is 0based. If new_invp == NULL, nothing is returned, otherwise the pointer to the allocated structure. 
PASTIX_SUCCESS  on success, 
PASTIX_ERR_ALLOC  if allocation went wrong, 
PASTIX_ERR_BADPARAMETER  if incorrect parameters are given. 
Definition at line 262 of file graph_isolate.c.
References graph_isolate_assign_ptr(), graph_isolate_everything(), graph_isolate_init_newcol(), graph_isolate_init_newrow(), graph_isolate_permutations(), PASTIX_ERR_BADPARAMETER, and PASTIX_SUCCESS.
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.
[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[lnode1]. 
[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. 
PASTIX_SUCCESS  on success. 
PASTIX_ERR_ALLOC  if allocation went wrong. 
PASTIX_ERR_BADPARAMETER  if incorrect parameters are given. 
Definition at line 455 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().
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 Kway partition of a given set of unknowns.
Take a graph with its own associated ordering, and generates a kway partition of the graph.
[in]  graph  The pointer to the graph structure on wich to apply the Kway 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 Kway 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 Kway partitioning. 
[in,out]  comp_nbr  On entry the number of components in the graph. On exit, the new number of components after Kway 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 kway 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 Kway paritioning. 
[in]  nbpart  The number of part wanted in the kway partitioning. 
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.