1: static char help[] = "Tests MatPartitioning with PT-SCOTCH when a process owns no graph vertices.\n\n";

  3: #include <petscmat.h>

  5: int main(int argc, char **args)
  6: {
  7:   Mat             adj;
  8:   MatPartitioning part;
  9:   IS              is;
 10:   PetscInt        N, npath, start, n, nlocal, nz, v, i;
 11:   PetscInt       *xadj, *adjncy, *vweights = NULL, *eweights = NULL;
 12:   PetscMPIInt     rank, size;
 13:   PetscBool       use_vertex_weights = PETSC_FALSE, use_edge_weights = PETSC_FALSE, isolated = PETSC_FALSE;

 15:   PetscFunctionBeginUser;
 16:   PetscCall(PetscInitialize(&argc, &args, NULL, help));
 17:   PetscCallMPI(MPI_Comm_rank(PETSC_COMM_WORLD, &rank));
 18:   PetscCallMPI(MPI_Comm_size(PETSC_COMM_WORLD, &size));
 19:   PetscCall(PetscOptionsGetBool(NULL, NULL, "-use_vertex_weights", &use_vertex_weights, NULL));
 20:   PetscCall(PetscOptionsGetBool(NULL, NULL, "-use_edge_weights", &use_edge_weights, NULL));
 21:   PetscCall(PetscOptionsGetBool(NULL, NULL, "-isolated_process", &isolated, NULL));

 23:   PetscCheck(size > 2, PETSC_COMM_WORLD, PETSC_ERR_WRONG_MPI_SIZE, "Requires at least three processes");

 25:   /* Spread the vertices of a path graph over every process but the first, which is left owning no
 26:      vertices and no edges. Its weight arrays then come back null from a zero-size allocation while
 27:      the other processes supply real weights, which is the disagreement SCOTCH_dgraphBuild()
 28:      rejects. Two processes must still own vertices, since
 29:      PetscPTSCOTCHPartitionGraph_Private() partitions with the sequential SCOTCH_graphBuild() when
 30:      every vertex lives on one process.
 31:      Each nonempty process owns several vertices to keep the total vertex load well above the
 32:      number of parts: PT-SCOTCH divides by a per-part average load that truncates to zero for a
 33:      graph smaller than the number of parts it is asked for.

 35:      With -isolated_process the vertices of the last process are isolated instead, so that it owns
 36:      vertices but no edges. Its edge weight array is then null from a zero-size allocation even
 37:      though it owns vertices, which the processes that do own edges have to account for. */
 38:   N     = 3 * (size - 1);
 39:   npath = isolated ? N - 3 : N;
 40:   n     = rank ? 3 : 0;
 41:   start = rank ? 3 * (rank - 1) : 0;

 43:   PetscCall(PetscMalloc1(n + 1, &xadj));
 44:   nz      = 0;
 45:   xadj[0] = 0;
 46:   for (i = 0; i < n; i++) {
 47:     v = start + i;
 48:     if (v < npath) {
 49:       if (v > 0) nz++;
 50:       if (v < npath - 1) nz++;
 51:     }
 52:     xadj[i + 1] = nz;
 53:   }
 54:   PetscCall(PetscMalloc1(nz, &adjncy));
 55:   nz = 0;
 56:   for (i = 0; i < n; i++) {
 57:     v = start + i;
 58:     if (v < npath) {
 59:       if (v > 0) adjncy[nz++] = v - 1;
 60:       if (v < npath - 1) adjncy[nz++] = v + 1;
 61:     }
 62:   }
 63:   if (use_edge_weights && nz) {
 64:     PetscCall(PetscMalloc1(nz, &eweights));
 65:     for (i = 0; i < nz; i++) eweights[i] = 2;
 66:   }
 67:   if (use_vertex_weights && n) {
 68:     PetscCall(PetscMalloc1(n, &vweights));
 69:     for (i = 0; i < n; i++) vweights[i] = rank + 1;
 70:   }

 72:   /* MatCreateMPIAdj() takes ownership of xadj, adjncy and eweights, and
 73:      MatPartitioningSetVertexWeights() takes ownership of vweights */
 74:   PetscCall(MatCreateMPIAdj(PETSC_COMM_WORLD, n, N, xadj, adjncy, eweights, &adj));
 75:   PetscCall(MatPartitioningCreate(PETSC_COMM_WORLD, &part));
 76:   if (use_edge_weights) PetscCall(MatPartitioningSetUseEdgeWeights(part, PETSC_TRUE));
 77:   PetscCall(MatPartitioningSetAdjacency(part, adj));
 78:   if (use_vertex_weights) PetscCall(MatPartitioningSetVertexWeights(part, vweights));
 79:   PetscCall(MatPartitioningSetNParts(part, size));
 80:   PetscCall(MatPartitioningSetFromOptions(part));
 81:   PetscCall(MatPartitioningApply(part, &is));

 83:   /* Which part each vertex lands in depends on the partitioner, but every process must be given
 84:      the destination of each of its own vertices */
 85:   PetscCall(ISGetLocalSize(is, &nlocal));
 86:   PetscCheck(nlocal == n, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Partitioning has %" PetscInt_FMT " local indices, expected %" PetscInt_FMT, nlocal, n);

 88:   PetscCall(ISDestroy(&is));
 89:   PetscCall(MatPartitioningDestroy(&part));
 90:   PetscCall(MatDestroy(&adj));
 91:   PetscCall(PetscFinalize());
 92:   return 0;
 93: }

 95: /*TEST

 97:    testset:
 98:       nsize: 3
 99:       requires: ptscotch
100:       args: -mat_partitioning_type ptscotch
101:       output_file: output/empty.out

103:       test:
104:          suffix: vertex_weights
105:          args: -use_vertex_weights 1

107:       test:
108:          suffix: edge_weights
109:          args: -use_edge_weights 1

111:       test:
112:          suffix: both_weights
113:          args: -use_vertex_weights 1 -use_edge_weights 1

115:       test:
116:          suffix: isolated_process
117:          args: -isolated_process 1 -use_edge_weights 1

119: TEST*/