Actual source code: plexorient.c

      1: #include <petsc/private/dmpleximpl.h>
      2: #include <petscsf.h>

      4: /*@
      5:   DMPlexOrientPoint - Act with the given orientation on the cone points of this mesh point, and update its use in the mesh.

      7:   Not Collective

      9:   Input Parameters:
     10: + dm - The `DM`
     11: . p  - The mesh point
     12: - o  - The orientation

     14:   Level: intermediate

     16: .seealso: [](ch_unstructured), `DM`, `DMPLEX`, `DMPlexOrient()`, `DMPlexGetCone()`, `DMPlexGetConeOrientation()`, `DMPlexInterpolate()`, `DMPlexGetChart()`
     17: @*/
     18: PetscErrorCode DMPlexOrientPoint(DM dm, PetscInt p, PetscInt o)
     19: {
     20:   DMPolytopeType  ct;
     21:   const PetscInt *arr, *cone, *ornt, *support;
     22:   PetscInt       *newcone, *newornt;
     23:   PetscInt        coneSize, c, supportSize, s;

     25:   PetscFunctionBegin;
     27:   PetscCall(DMPlexGetCellType(dm, p, &ct));
     28:   arr = DMPolytopeTypeGetArrangement(ct, o);
     29:   if (!arr) PetscFunctionReturn(PETSC_SUCCESS);
     30:   PetscCall(DMPlexGetConeSize(dm, p, &coneSize));
     31:   PetscCall(DMPlexGetCone(dm, p, &cone));
     32:   PetscCall(DMPlexGetConeOrientation(dm, p, &ornt));
     33:   PetscCall(DMGetWorkArray(dm, coneSize, MPIU_INT, &newcone));
     34:   PetscCall(DMGetWorkArray(dm, coneSize, MPIU_INT, &newornt));
     35:   for (c = 0; c < coneSize; ++c) {
     36:     DMPolytopeType ft;
     37:     PetscInt       nO;

     39:     PetscCall(DMPlexGetCellType(dm, cone[c], &ft));
     40:     nO         = DMPolytopeTypeGetNumArrangements(ft) / 2;
     41:     newcone[c] = cone[arr[c * 2 + 0]];
     42:     newornt[c] = DMPolytopeTypeComposeOrientation(ft, arr[c * 2 + 1], ornt[arr[c * 2 + 0]]);
     43:     PetscCheck(!newornt[c] || !(newornt[c] >= nO || newornt[c] < -nO), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Invalid orientation %" PetscInt_FMT " not in [%" PetscInt_FMT ",%" PetscInt_FMT ") for %s %" PetscInt_FMT, newornt[c], -nO, nO, DMPolytopeTypes[ft], cone[c]);
     44:   }
     45:   PetscCall(DMPlexSetCone(dm, p, newcone));
     46:   PetscCall(DMPlexSetConeOrientation(dm, p, newornt));
     47:   PetscCall(DMRestoreWorkArray(dm, coneSize, MPIU_INT, &newcone));
     48:   PetscCall(DMRestoreWorkArray(dm, coneSize, MPIU_INT, &newornt));
     49:   /* Update orientation of this point in the support points */
     50:   PetscCall(DMPlexGetSupportSize(dm, p, &supportSize));
     51:   PetscCall(DMPlexGetSupport(dm, p, &support));
     52:   for (s = 0; s < supportSize; ++s) {
     53:     PetscCall(DMPlexGetConeSize(dm, support[s], &coneSize));
     54:     PetscCall(DMPlexGetCone(dm, support[s], &cone));
     55:     PetscCall(DMPlexGetConeOrientation(dm, support[s], &ornt));
     56:     for (c = 0; c < coneSize; ++c) {
     57:       PetscInt po;

     59:       if (cone[c] != p) continue;
     60:       /* ornt[c] * 0 = target = po * o so that po = ornt[c] * o^{-1} */
     61:       po = DMPolytopeTypeComposeOrientationInv(ct, ornt[c], o);
     62:       PetscCall(DMPlexInsertConeOrientation(dm, support[s], c, po));
     63:     }
     64:   }
     65:   PetscFunctionReturn(PETSC_SUCCESS);
     66: }

     68: static PetscInt GetPointIndex(PetscInt point, PetscInt pStart, PetscInt pEnd, const PetscInt points[])
     69: {
     70:   if (points) {
     71:     PetscInt loc;

     73:     PetscCallAbort(PETSC_COMM_SELF, PetscFindInt(point, pEnd - pStart, points, &loc));
     74:     if (loc >= 0) return loc;
     75:   } else {
     76:     if (point >= pStart && point < pEnd) return point - pStart;
     77:   }
     78:   return -1;
     79: }

     81: /*
     82:   - Checks face match
     83:     - Flips non-matching
     84:   - Inserts faces of support cells in FIFO
     85: */
     86: static PetscErrorCode DMPlexCheckFace_Internal(DM dm, PetscInt *faceFIFO, PetscInt *fTop, PetscInt *fBottom, IS cellIS, IS faceIS, PetscBT seenCells, PetscBT flippedCells, PetscBT seenFaces)
     87: {
     88:   const PetscInt *supp, *coneA, *coneB, *coneOA, *coneOB;
     89:   PetscInt        suppSize, Ns = 0, coneSizeA, coneSizeB, posA = -1, posB = -1;
     90:   PetscInt        face, dim, indC[3], indS[3], seenA, flippedA, seenB, flippedB, mismatch;
     91:   const PetscInt *cells, *faces;
     92:   PetscInt        cStart, cEnd, fStart, fEnd;

     94:   PetscFunctionBegin;
     95:   face = faceFIFO[(*fTop)++];
     96:   PetscCall(ISGetPointRange(cellIS, &cStart, &cEnd, &cells));
     97:   PetscCall(ISGetPointRange(faceIS, &fStart, &fEnd, &faces));
     98:   PetscCall(DMPlexGetPointDepth(dm, cells ? cells[cStart] : cStart, &dim));
     99:   PetscCall(DMPlexGetSupportSize(dm, face, &suppSize));
    100:   PetscCall(DMPlexGetSupport(dm, face, &supp));
    101:   // Filter the support
    102:   for (PetscInt s = 0; s < suppSize; ++s) {
    103:     // Filter support
    104:     indC[Ns] = GetPointIndex(supp[s], cStart, cEnd, cells);
    105:     indS[Ns] = s;
    106:     if (indC[Ns] >= 0) ++Ns;
    107:   }
    108:   if (Ns < 2) PetscFunctionReturn(PETSC_SUCCESS);
    109:   PetscCheck(Ns == 2, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Faces should separate only two cells, not %" PetscInt_FMT, Ns);
    110:   PetscCheck(indC[0] >= 0 && indC[1] >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Support cells %" PetscInt_FMT " (%" PetscInt_FMT ") and %" PetscInt_FMT " (%" PetscInt_FMT ") are not both valid", supp[0], indC[0], supp[1], indC[1]);
    111:   seenA    = PetscBTLookup(seenCells, indC[0]);
    112:   flippedA = PetscBTLookup(flippedCells, indC[0]) ? 1 : 0;
    113:   seenB    = PetscBTLookup(seenCells, indC[1]);
    114:   flippedB = PetscBTLookup(flippedCells, indC[1]) ? 1 : 0;

    116:   PetscCall(DMPlexGetConeSize(dm, supp[indS[0]], &coneSizeA));
    117:   PetscCall(DMPlexGetConeSize(dm, supp[indS[1]], &coneSizeB));
    118:   PetscCall(DMPlexGetCone(dm, supp[indS[0]], &coneA));
    119:   PetscCall(DMPlexGetCone(dm, supp[indS[1]], &coneB));
    120:   PetscCall(DMPlexGetConeOrientation(dm, supp[indS[0]], &coneOA));
    121:   PetscCall(DMPlexGetConeOrientation(dm, supp[indS[1]], &coneOB));
    122:   for (PetscInt c = 0; c < coneSizeA; ++c) {
    123:     const PetscInt indF = GetPointIndex(coneA[c], fStart, fEnd, faces);

    125:     // Filter cone
    126:     if (indF < 0) continue;
    127:     if (!PetscBTLookup(seenFaces, indF)) {
    128:       faceFIFO[(*fBottom)++] = coneA[c];
    129:       PetscCall(PetscBTSet(seenFaces, indF));
    130:     }
    131:     if (coneA[c] == face) posA = c;
    132:     PetscCheck(*fBottom <= fEnd - fStart, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Face %" PetscInt_FMT " was pushed exceeding capacity %" PetscInt_FMT " > %" PetscInt_FMT, coneA[c], *fBottom, fEnd - fStart);
    133:   }
    134:   PetscCheck(posA >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %" PetscInt_FMT " could not be located in cell %" PetscInt_FMT, face, supp[indS[0]]);
    135:   for (PetscInt c = 0; c < coneSizeB; ++c) {
    136:     const PetscInt indF = GetPointIndex(coneB[c], fStart, fEnd, faces);

    138:     // Filter cone
    139:     if (indF < 0) continue;
    140:     if (!PetscBTLookup(seenFaces, indF)) {
    141:       faceFIFO[(*fBottom)++] = coneB[c];
    142:       PetscCall(PetscBTSet(seenFaces, indF));
    143:     }
    144:     if (coneB[c] == face) posB = c;
    145:     PetscCheck(*fBottom <= fEnd - fStart, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Face %" PetscInt_FMT " was pushed exceeding capacity %" PetscInt_FMT " > %" PetscInt_FMT, coneA[c], *fBottom, fEnd - fStart);
    146:   }
    147:   PetscCheck(posB >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %" PetscInt_FMT " could not be located in cell %" PetscInt_FMT, face, supp[indS[1]]);

    149:   if (dim == 1) {
    150:     mismatch = posA == posB;
    151:   } else {
    152:     mismatch = coneOA[posA] == coneOB[posB];
    153:   }

    155:   if (mismatch ^ (flippedA ^ flippedB)) {
    156:     PetscCheck(!seenA || !seenB, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Previously seen cells %" PetscInt_FMT " and %" PetscInt_FMT " do not match: Fault mesh is non-orientable", supp[indS[0]], supp[indS[1]]);
    157:     if (!seenA && !flippedA) {
    158:       PetscCall(PetscBTSet(flippedCells, indC[0]));
    159:     } else if (!seenB && !flippedB) {
    160:       PetscCall(PetscBTSet(flippedCells, indC[1]));
    161:     } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Inconsistent mesh orientation: Fault mesh is non-orientable");
    162:   } else PetscCheck(!mismatch || !flippedA || !flippedB, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempt to flip already flipped cell: Fault mesh is non-orientable");
    163:   PetscCall(PetscBTSet(seenCells, indC[0]));
    164:   PetscCall(PetscBTSet(seenCells, indC[1]));
    165:   PetscFunctionReturn(PETSC_SUCCESS);
    166: }

    168: static PetscErrorCode DMPlexCheckFace_Old_Internal(DM dm, PetscInt *faceFIFO, PetscInt *fTop, PetscInt *fBottom, PetscInt cStart, PetscInt fStart, PetscInt fEnd, PetscBT seenCells, PetscBT flippedCells, PetscBT seenFaces)
    169: {
    170:   const PetscInt *support, *coneA, *coneB, *coneOA, *coneOB;
    171:   PetscInt        supportSize, coneSizeA, coneSizeB, posA = -1, posB = -1;
    172:   PetscInt        face, dim, seenA, flippedA, seenB, flippedB, mismatch, c;

    174:   PetscFunctionBegin;
    175:   face = faceFIFO[(*fTop)++];
    176:   PetscCall(DMGetDimension(dm, &dim));
    177:   PetscCall(DMPlexGetSupportSize(dm, face, &supportSize));
    178:   PetscCall(DMPlexGetSupport(dm, face, &support));
    179:   if (supportSize < 2) PetscFunctionReturn(PETSC_SUCCESS);
    180:   PetscCheck(supportSize == 2, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Faces should separate only two cells, not %" PetscInt_FMT, supportSize);
    181:   seenA    = PetscBTLookup(seenCells, support[0] - cStart);
    182:   flippedA = PetscBTLookup(flippedCells, support[0] - cStart) ? 1 : 0;
    183:   seenB    = PetscBTLookup(seenCells, support[1] - cStart);
    184:   flippedB = PetscBTLookup(flippedCells, support[1] - cStart) ? 1 : 0;

    186:   PetscCall(DMPlexGetConeSize(dm, support[0], &coneSizeA));
    187:   PetscCall(DMPlexGetConeSize(dm, support[1], &coneSizeB));
    188:   PetscCall(DMPlexGetCone(dm, support[0], &coneA));
    189:   PetscCall(DMPlexGetCone(dm, support[1], &coneB));
    190:   PetscCall(DMPlexGetConeOrientation(dm, support[0], &coneOA));
    191:   PetscCall(DMPlexGetConeOrientation(dm, support[1], &coneOB));
    192:   for (c = 0; c < coneSizeA; ++c) {
    193:     if (!PetscBTLookup(seenFaces, coneA[c] - fStart)) {
    194:       faceFIFO[(*fBottom)++] = coneA[c];
    195:       PetscCall(PetscBTSet(seenFaces, coneA[c] - fStart));
    196:     }
    197:     if (coneA[c] == face) posA = c;
    198:     PetscCheck(*fBottom <= fEnd - fStart, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Face %" PetscInt_FMT " was pushed exceeding capacity %" PetscInt_FMT " > %" PetscInt_FMT, coneA[c], *fBottom, fEnd - fStart);
    199:   }
    200:   PetscCheck(posA >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %" PetscInt_FMT " could not be located in cell %" PetscInt_FMT, face, support[0]);
    201:   for (c = 0; c < coneSizeB; ++c) {
    202:     if (!PetscBTLookup(seenFaces, coneB[c] - fStart)) {
    203:       faceFIFO[(*fBottom)++] = coneB[c];
    204:       PetscCall(PetscBTSet(seenFaces, coneB[c] - fStart));
    205:     }
    206:     if (coneB[c] == face) posB = c;
    207:     PetscCheck(*fBottom <= fEnd - fStart, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Face %" PetscInt_FMT " was pushed exceeding capacity %" PetscInt_FMT " > %" PetscInt_FMT, coneA[c], *fBottom, fEnd - fStart);
    208:   }
    209:   PetscCheck(posB >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %" PetscInt_FMT " could not be located in cell %" PetscInt_FMT, face, support[1]);

    211:   if (dim == 1) {
    212:     mismatch = posA == posB;
    213:   } else {
    214:     mismatch = coneOA[posA] == coneOB[posB];
    215:   }

    217:   if (mismatch ^ (flippedA ^ flippedB)) {
    218:     PetscCheck(!seenA || !seenB, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Previously seen cells %" PetscInt_FMT " and %" PetscInt_FMT " do not match: Fault mesh is non-orientable", support[0], support[1]);
    219:     if (!seenA && !flippedA) {
    220:       PetscCall(PetscBTSet(flippedCells, support[0] - cStart));
    221:     } else if (!seenB && !flippedB) {
    222:       PetscCall(PetscBTSet(flippedCells, support[1] - cStart));
    223:     } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Inconsistent mesh orientation: Fault mesh is non-orientable");
    224:   } else PetscCheck(!mismatch || !flippedA || !flippedB, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempt to flip already flipped cell: Fault mesh is non-orientable");
    225:   PetscCall(PetscBTSet(seenCells, support[0] - cStart));
    226:   PetscCall(PetscBTSet(seenCells, support[1] - cStart));
    227:   PetscFunctionReturn(PETSC_SUCCESS);
    228: }

    230: /*
    231:   DMPlexOrient_Serial - Compute valid orientation for local connected components

    233:   Not collective

    235:   Input Parameters:
    236:   + dm         - The `DM`
    237:   - cellHeight - The height of k-cells to be oriented

    239:   Output Parameters:
    240:   + Ncomp        - The number of connected component
    241:   . cellComp     - The connected component for each local cell
    242:   . faceComp     - The connected component for each local face
    243:   - flippedCells - Marked cells should be inverted

    245:   Level: developer

    247: .seealso: `DMPlexOrient()`
    248: */
    249: static PetscErrorCode DMPlexOrient_Serial(DM dm, IS cellIS, IS faceIS, PetscInt *Ncomp, PetscInt cellComp[], PetscInt faceComp[], PetscBT flippedCells)
    250: {
    251:   PetscBT         seenCells, seenFaces;
    252:   PetscInt       *faceFIFO;
    253:   const PetscInt *cells = NULL, *faces = NULL;
    254:   PetscInt        cStart = 0, cEnd = 0, fStart = 0, fEnd = 0;

    256:   PetscFunctionBegin;
    257:   if (cellIS) PetscCall(ISGetPointRange(cellIS, &cStart, &cEnd, &cells));
    258:   if (faceIS) PetscCall(ISGetPointRange(faceIS, &fStart, &fEnd, &faces));
    259:   PetscCall(PetscBTCreate(cEnd - cStart, &seenCells));
    260:   PetscCall(PetscBTMemzero(cEnd - cStart, seenCells));
    261:   PetscCall(PetscBTCreate(fEnd - fStart, &seenFaces));
    262:   PetscCall(PetscBTMemzero(fEnd - fStart, seenFaces));
    263:   PetscCall(PetscMalloc1(fEnd - fStart, &faceFIFO));
    264:   *Ncomp = 0;
    265:   for (PetscInt c = 0; c < cEnd - cStart; ++c) cellComp[c] = -1;
    266:   do {
    267:     PetscInt cc, fTop, fBottom;

    269:     // Look for first unmarked cell
    270:     for (cc = cStart; cc < cEnd; ++cc)
    271:       if (cellComp[cc - cStart] < 0) break;
    272:     if (cc >= cEnd) break;
    273:     // Initialize FIFO with first cell in component
    274:     {
    275:       const PetscInt  cell = cells ? cells[cc] : cc;
    276:       const PetscInt *cone;
    277:       PetscInt        coneSize;

    279:       fTop = fBottom = 0;
    280:       PetscCall(DMPlexGetConeSize(dm, cell, &coneSize));
    281:       PetscCall(DMPlexGetCone(dm, cell, &cone));
    282:       for (PetscInt c = 0; c < coneSize; ++c) {
    283:         // Cell faces are guaranteed to be in the face set
    284:         faceFIFO[fBottom++] = cone[c];
    285:         PetscCall(PetscBTSet(seenFaces, GetPointIndex(cone[c], fStart, fEnd, faces)));
    286:       }
    287:       PetscCall(PetscBTSet(seenCells, cc - cStart));
    288:     }
    289:     // Consider each face in FIFO
    290:     while (fTop < fBottom) PetscCall(DMPlexCheckFace_Internal(dm, faceFIFO, &fTop, &fBottom, cellIS, faceIS, seenCells, flippedCells, seenFaces));
    291:     // Set component for cells and faces
    292:     for (PetscInt c = 0; c < cEnd - cStart; ++c) {
    293:       if (PetscBTLookup(seenCells, c)) cellComp[c] = *Ncomp;
    294:     }
    295:     for (PetscInt f = 0; f < fEnd - fStart; ++f) {
    296:       if (PetscBTLookup(seenFaces, f)) faceComp[f] = *Ncomp;
    297:     }
    298:     // Wipe seenCells and seenFaces for next component
    299:     PetscCall(PetscBTMemzero(fEnd - fStart, seenFaces));
    300:     PetscCall(PetscBTMemzero(cEnd - cStart, seenCells));
    301:     ++(*Ncomp);
    302:   } while (1);
    303:   PetscCall(PetscBTDestroy(&seenCells));
    304:   PetscCall(PetscBTDestroy(&seenFaces));
    305:   PetscCall(PetscFree(faceFIFO));
    306:   PetscFunctionReturn(PETSC_SUCCESS);
    307: }

    309: /*@
    310:   DMPlexOrient - Give a consistent orientation to the input mesh

    312:   Input Parameter:
    313: . dm - The `DM`

    315:   Note:
    316:   The orientation data for the `DM` are change in-place.

    318:   This routine will fail for non-orientable surfaces, such as the Moebius strip.

    320:   Level: advanced

    322: .seealso: [](ch_unstructured), `DM`, `DMPLEX`, `DMCreate()`
    323: @*/
    324: PetscErrorCode DMPlexOrient(DM dm)
    325: {
    326: #if 0
    327:   IS cellIS, faceIS;

    329:   PetscFunctionBegin;
    330:   PetscCall(DMPlexGetAllCells_Internal(dm, &cellIS));
    331:   PetscCall(DMPlexGetAllFaces_Internal(dm, &faceIS));
    332:   PetscCall(DMPlexOrientCells_Internal(dm, cellIS, faceIS));
    333:   PetscCall(ISDestroy(&cellIS));
    334:   PetscCall(ISDestroy(&faceIS));
    335:   PetscFunctionReturn(PETSC_SUCCESS);
    336: #else
    337:   MPI_Comm           comm;
    338:   PetscSF            sf;
    339:   const PetscInt    *lpoints;
    340:   const PetscSFNode *rpoints;
    341:   PetscSFNode       *rorntComp = NULL, *lorntComp = NULL;
    342:   PetscInt          *numNeighbors, **neighbors, *locSupport = NULL;
    343:   PetscSFNode       *nrankComp;
    344:   PetscBool         *match, *flipped;
    345:   PetscBT            seenCells, flippedCells, seenFaces;
    346:   PetscInt          *faceFIFO, fTop, fBottom, *cellComp, *faceComp;
    347:   PetscInt           numLeaves, numRoots, dim, h, cStart, cEnd, c, cell, fStart, fEnd, face, off, totNeighbors = 0;
    348:   PetscMPIInt        rank, size, numComponents, comp = 0;
    349:   PetscBool          flg, flg2;
    350:   PetscViewer        viewer = NULL, selfviewer = NULL;

    352:   PetscFunctionBegin;
    353:   PetscCall(PetscObjectGetComm((PetscObject)dm, &comm));
    354:   PetscCallMPI(MPI_Comm_rank(comm, &rank));
    355:   PetscCallMPI(MPI_Comm_size(comm, &size));
    356:   PetscCall(PetscOptionsHasName(((PetscObject)dm)->options, ((PetscObject)dm)->prefix, "-orientation_view", &flg));
    357:   PetscCall(PetscOptionsHasName(((PetscObject)dm)->options, ((PetscObject)dm)->prefix, "-orientation_view_synchronized", &flg2));
    358:   PetscCall(DMGetPointSF(dm, &sf));
    359:   PetscCall(PetscSFGetGraph(sf, &numRoots, &numLeaves, &lpoints, &rpoints));
    360:   /* Truth Table
    361:      mismatch    flips   do action   mismatch   flipA ^ flipB   action
    362:          F       0 flips     no         F             F           F
    363:          F       1 flip      yes        F             T           T
    364:          F       2 flips     no         T             F           T
    365:          T       0 flips     yes        T             T           F
    366:          T       1 flip      no
    367:          T       2 flips     yes
    368:   */
    369:   PetscCall(DMGetDimension(dm, &dim));
    370:   PetscCall(DMPlexGetVTKCellHeight(dm, &h));
    371:   PetscCall(DMPlexGetHeightStratum(dm, h, &cStart, &cEnd));
    372:   PetscCall(DMPlexGetHeightStratum(dm, h + 1, &fStart, &fEnd));
    373:   PetscCall(PetscBTCreate(cEnd - cStart, &seenCells));
    374:   PetscCall(PetscBTMemzero(cEnd - cStart, seenCells));
    375:   PetscCall(PetscBTCreate(cEnd - cStart, &flippedCells));
    376:   PetscCall(PetscBTMemzero(cEnd - cStart, flippedCells));
    377:   PetscCall(PetscBTCreate(fEnd - fStart, &seenFaces));
    378:   PetscCall(PetscBTMemzero(fEnd - fStart, seenFaces));
    379:   PetscCall(PetscCalloc3(fEnd - fStart, &faceFIFO, cEnd - cStart, &cellComp, fEnd - fStart, &faceComp));
    380:   /*
    381:    OLD STYLE
    382:    - Add an integer array over cells and faces (component) for connected component number
    383:    Foreach component
    384:      - Mark the initial cell as seen
    385:      - Process component as usual
    386:      - Set component for all seenCells
    387:      - Wipe seenCells and seenFaces (flippedCells can stay)
    388:    - Generate parallel adjacency for component using SF and seenFaces
    389:    - Collect numComponents adj data from each proc to 0
    390:    - Build same serial graph
    391:    - Use same solver
    392:    - Use Scatterv to send back flipped flags for each component
    393:    - Negate flippedCells by component

    395:    NEW STYLE
    396:    - Create the adj on each process
    397:    - Bootstrap to complete graph on proc 0
    398:   */
    399:   /* Loop over components */
    400:   for (cell = cStart; cell < cEnd; ++cell) cellComp[cell - cStart] = -1;
    401:   do {
    402:     /* Look for first unmarked cell */
    403:     for (cell = cStart; cell < cEnd; ++cell)
    404:       if (cellComp[cell - cStart] < 0) break;
    405:     if (cell >= cEnd) break;
    406:     /* Initialize FIFO with first cell in component */
    407:     {
    408:       const PetscInt *cone;
    409:       PetscInt        coneSize;

    411:       fTop = fBottom = 0;
    412:       PetscCall(DMPlexGetConeSize(dm, cell, &coneSize));
    413:       PetscCall(DMPlexGetCone(dm, cell, &cone));
    414:       for (c = 0; c < coneSize; ++c) {
    415:         faceFIFO[fBottom++] = cone[c];
    416:         PetscCall(PetscBTSet(seenFaces, cone[c] - fStart));
    417:       }
    418:       PetscCall(PetscBTSet(seenCells, cell - cStart));
    419:     }
    420:     /* Consider each face in FIFO */
    421:     while (fTop < fBottom) PetscCall(DMPlexCheckFace_Old_Internal(dm, faceFIFO, &fTop, &fBottom, cStart, fStart, fEnd, seenCells, flippedCells, seenFaces));
    422:     /* Set component for cells and faces */
    423:     for (cell = 0; cell < cEnd - cStart; ++cell) {
    424:       if (PetscBTLookup(seenCells, cell)) cellComp[cell] = comp;
    425:     }
    426:     for (face = 0; face < fEnd - fStart; ++face) {
    427:       if (PetscBTLookup(seenFaces, face)) faceComp[face] = comp;
    428:     }
    429:     /* Wipe seenCells and seenFaces for next component */
    430:     PetscCall(PetscBTMemzero(fEnd - fStart, seenFaces));
    431:     PetscCall(PetscBTMemzero(cEnd - cStart, seenCells));
    432:     ++comp;
    433:   } while (1);
    434:   numComponents = comp;
    435:   if (flg) {
    436:     PetscViewer v;

    438:     PetscCall(PetscViewerASCIIGetStdout(comm, &v));
    439:     PetscCall(PetscViewerASCIIPushSynchronized(v));
    440:     PetscCall(PetscViewerASCIISynchronizedPrintf(v, "[%d]BT for serial flipped cells:\n", rank));
    441:     PetscCall(PetscBTView(cEnd - cStart, flippedCells, v));
    442:     PetscCall(PetscViewerFlush(v));
    443:     PetscCall(PetscViewerASCIIPopSynchronized(v));
    444:   }
    445:   /* Now all subdomains are oriented, but we need a consistent parallel orientation */
    446:   if (numLeaves >= 0) {
    447:     PetscInt maxSupportSize, neighbor;

    449:     /* Store orientations of boundary faces*/
    450:     PetscCall(DMPlexGetMaxSizes(dm, NULL, &maxSupportSize));
    451:     PetscCall(PetscCalloc3(numRoots, &rorntComp, numRoots, &lorntComp, maxSupportSize, &locSupport));
    452:     for (face = fStart; face < fEnd; ++face) {
    453:       const PetscInt *cone, *support, *ornt;
    454:       PetscInt        coneSize, supportSize, Ns = 0, s, l;

    456:       PetscCall(DMPlexGetSupportSize(dm, face, &supportSize));
    457:       /* Ignore overlapping cells */
    458:       PetscCall(DMPlexGetSupport(dm, face, &support));
    459:       for (s = 0; s < supportSize; ++s) {
    460:         PetscCall(PetscFindInt(support[s], numLeaves, lpoints, &l));
    461:         if (l >= 0) continue;
    462:         locSupport[Ns++] = support[s];
    463:       }
    464:       if (Ns != 1) continue;
    465:       neighbor = locSupport[0];
    466:       PetscCall(DMPlexGetCone(dm, neighbor, &cone));
    467:       PetscCall(DMPlexGetConeSize(dm, neighbor, &coneSize));
    468:       PetscCall(DMPlexGetConeOrientation(dm, neighbor, &ornt));
    469:       for (c = 0; c < coneSize; ++c)
    470:         if (cone[c] == face) break;
    471:       if (dim == 1) {
    472:         /* Use cone position instead, shifted to -1 or 1 */
    473:         if (PetscBTLookup(flippedCells, neighbor - cStart)) rorntComp[face].rank = (PetscMPIInt)(1 - c * 2);
    474:         else rorntComp[face].rank = (PetscMPIInt)(c * 2 - 1);
    475:       } else {
    476:         if (PetscBTLookup(flippedCells, neighbor - cStart)) rorntComp[face].rank = ornt[c] < 0 ? -1 : 1;
    477:         else rorntComp[face].rank = ornt[c] < 0 ? 1 : -1;
    478:       }
    479:       rorntComp[face].index = faceComp[face - fStart];
    480:     }
    481:     /* Communicate boundary edge orientations */
    482:     PetscCall(PetscSFBcastBegin(sf, MPIU_SF_NODE, rorntComp, lorntComp, MPI_REPLACE));
    483:     PetscCall(PetscSFBcastEnd(sf, MPIU_SF_NODE, rorntComp, lorntComp, MPI_REPLACE));
    484:   }
    485:   /* Get process adjacency */
    486:   PetscCall(PetscMalloc2(numComponents, &numNeighbors, numComponents, &neighbors));
    487:   viewer = PETSC_VIEWER_STDOUT_(PetscObjectComm((PetscObject)dm));
    488:   if (flg2) PetscCall(PetscViewerASCIIPushSynchronized(viewer));
    489:   PetscCall(PetscViewerGetSubViewer(viewer, PETSC_COMM_SELF, &selfviewer));
    490:   for (comp = 0; comp < numComponents; ++comp) {
    491:     PetscInt l, n;

    493:     numNeighbors[comp] = 0;
    494:     PetscCall(PetscMalloc1(PetscMax(numLeaves, 0), &neighbors[comp]));
    495:     /* I know this is p^2 time in general, but for bounded degree its alright */
    496:     for (l = 0; l < numLeaves; ++l) {
    497:       const PetscInt face = lpoints[l];

    499:       /* Find a representative face (edge) separating pairs of procs */
    500:       if ((face >= fStart) && (face < fEnd) && (faceComp[face - fStart] == comp) && rorntComp[face].rank) {
    501:         const PetscMPIInt rrank = (PetscMPIInt)rpoints[l].rank;
    502:         const PetscInt    rcomp = lorntComp[face].index;

    504:         for (n = 0; n < numNeighbors[comp]; ++n)
    505:           if ((rrank == rpoints[neighbors[comp][n]].rank) && (rcomp == lorntComp[lpoints[neighbors[comp][n]]].index)) break;
    506:         if (n >= numNeighbors[comp]) {
    507:           PetscInt supportSize;

    509:           PetscCall(DMPlexGetSupportSize(dm, face, &supportSize));
    510:           PetscCheck(supportSize == 1, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Boundary faces should see one cell, not %" PetscInt_FMT, supportSize);
    511:           if (flg)
    512:             PetscCall(PetscViewerASCIIPrintf(selfviewer, "[%d]: component %d, Found representative leaf %" PetscInt_FMT " (face %" PetscInt_FMT ") connecting to face %" PetscInt_FMT " on (%d, %" PetscInt_FMT ") with orientation %d\n", rank, comp, l, face,
    513:                                              rpoints[l].index, rrank, rcomp, (PetscMPIInt)lorntComp[face].rank));
    514:           neighbors[comp][numNeighbors[comp]++] = l;
    515:         }
    516:       }
    517:     }
    518:     totNeighbors += numNeighbors[comp];
    519:   }
    520:   PetscCall(PetscViewerRestoreSubViewer(viewer, PETSC_COMM_SELF, &selfviewer));
    521:   if (flg2) PetscCall(PetscViewerASCIIPopSynchronized(viewer));
    522:   PetscCall(PetscMalloc2(totNeighbors, &nrankComp, totNeighbors, &match));
    523:   for (comp = 0, off = 0; comp < numComponents; ++comp) {
    524:     PetscInt n;

    526:     for (n = 0; n < numNeighbors[comp]; ++n, ++off) {
    527:       const PetscInt face = lpoints[neighbors[comp][n]];
    528:       const PetscInt o    = rorntComp[face].rank * lorntComp[face].rank;

    530:       if (o < 0) match[off] = PETSC_TRUE;
    531:       else if (o > 0) match[off] = PETSC_FALSE;
    532:       else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Invalid face %" PetscInt_FMT " (%d, %d) neighbor: %" PetscInt_FMT " comp: %d", face, (PetscMPIInt)rorntComp[face].rank, (PetscMPIInt)lorntComp[face].rank, neighbors[comp][n], comp);
    533:       nrankComp[off].rank  = rpoints[neighbors[comp][n]].rank;
    534:       nrankComp[off].index = lorntComp[lpoints[neighbors[comp][n]]].index;
    535:     }
    536:     PetscCall(PetscFree(neighbors[comp]));
    537:   }
    538:   /* Collect the graph on 0 */
    539:   if (numLeaves >= 0) {
    540:     Mat          G;
    541:     PetscBT      seenProcs, flippedProcs;
    542:     PetscInt    *procFIFO, pTop, pBottom;
    543:     PetscInt    *N          = NULL, *Noff;
    544:     PetscSFNode *adj        = NULL;
    545:     PetscBool   *val        = NULL;
    546:     PetscMPIInt *recvcounts = NULL, *displs = NULL, *Nc, p, o, itotNeighbors;
    547:     PetscMPIInt  size = 0;

    549:     PetscCall(PetscCalloc1(numComponents, &flipped));
    550:     if (rank == 0) PetscCallMPI(MPI_Comm_size(comm, &size));
    551:     PetscCall(PetscCalloc4(size, &recvcounts, size + 1, &displs, size, &Nc, size + 1, &Noff));
    552:     PetscCallMPI(MPI_Gather(&numComponents, 1, MPI_INT, Nc, 1, MPI_INT, 0, comm));
    553:     for (p = 0; p < size; ++p) displs[p + 1] = displs[p] + Nc[p];
    554:     if (rank == 0) PetscCall(PetscMalloc1(displs[size], &N));
    555:     PetscCallMPI(MPI_Gatherv(numNeighbors, numComponents, MPIU_INT, N, Nc, displs, MPIU_INT, 0, comm));
    556:     for (p = 0, o = 0; p < size; ++p) {
    557:       recvcounts[p] = 0;
    558:       for (c = 0; c < Nc[p]; ++c, ++o) recvcounts[p] += N[o];
    559:       displs[p + 1] = displs[p] + recvcounts[p];
    560:     }
    561:     if (rank == 0) PetscCall(PetscMalloc2(displs[size], &adj, displs[size], &val));
    562:     PetscCall(PetscMPIIntCast(totNeighbors, &itotNeighbors));
    563:     PetscCallMPI(MPI_Gatherv(nrankComp, itotNeighbors, MPIU_SF_NODE, adj, recvcounts, displs, MPIU_SF_NODE, 0, comm));
    564:     PetscCallMPI(MPI_Gatherv(match, itotNeighbors, MPIU_BOOL, val, recvcounts, displs, MPIU_BOOL, 0, comm));
    565:     PetscCall(PetscFree2(numNeighbors, neighbors));
    566:     if (rank == 0) {
    567:       for (p = 1; p <= size; ++p) Noff[p] = Noff[p - 1] + Nc[p - 1];
    568:       if (flg) {
    569:         PetscInt n;

    571:         for (p = 0, off = 0; p < size; ++p) {
    572:           for (c = 0; c < Nc[p]; ++c) {
    573:             PetscCall(PetscPrintf(PETSC_COMM_SELF, "Proc %d Comp %" PetscInt_FMT ":\n", p, c));
    574:             for (n = 0; n < N[Noff[p] + c]; ++n, ++off) PetscCall(PetscPrintf(PETSC_COMM_SELF, "  edge (%d, %" PetscInt_FMT ") (%s):\n", (PetscMPIInt)adj[off].rank, adj[off].index, PetscBools[val[off]]));
    575:           }
    576:         }
    577:       }
    578:       /* Symmetrize the graph */
    579:       PetscCall(MatCreate(PETSC_COMM_SELF, &G));
    580:       PetscCall(MatSetSizes(G, Noff[size], Noff[size], Noff[size], Noff[size]));
    581:       PetscCall(MatSetUp(G));
    582:       for (p = 0, off = 0; p < size; ++p) {
    583:         for (c = 0; c < Nc[p]; ++c) {
    584:           const PetscInt r = Noff[p] + c;
    585:           PetscInt       n;

    587:           for (n = 0; n < N[r]; ++n, ++off) {
    588:             const PetscInt    q = Noff[adj[off].rank] + adj[off].index;
    589:             const PetscScalar o = val[off] ? 1.0 : 0.0;

    591:             PetscCall(MatSetValues(G, 1, &r, 1, &q, &o, INSERT_VALUES));
    592:             PetscCall(MatSetValues(G, 1, &q, 1, &r, &o, INSERT_VALUES));
    593:           }
    594:         }
    595:       }
    596:       PetscCall(MatAssemblyBegin(G, MAT_FINAL_ASSEMBLY));
    597:       PetscCall(MatAssemblyEnd(G, MAT_FINAL_ASSEMBLY));

    599:       PetscCall(PetscBTCreate(Noff[size], &seenProcs));
    600:       PetscCall(PetscBTMemzero(Noff[size], seenProcs));
    601:       PetscCall(PetscBTCreate(Noff[size], &flippedProcs));
    602:       PetscCall(PetscBTMemzero(Noff[size], flippedProcs));
    603:       PetscCall(PetscMalloc1(Noff[size], &procFIFO));
    604:       pTop = pBottom = 0;
    605:       for (p = 0; p < Noff[size]; ++p) {
    606:         if (PetscBTLookup(seenProcs, p)) continue;
    607:         /* Initialize FIFO with next proc */
    608:         procFIFO[pBottom++] = p;
    609:         PetscCall(PetscBTSet(seenProcs, p));
    610:         /* Consider each proc in FIFO */
    611:         while (pTop < pBottom) {
    612:           const PetscScalar *ornt;
    613:           const PetscInt    *neighbors;
    614:           PetscInt           proc, nproc, seen, flippedA, flippedB, mismatch, numNeighbors, n;

    616:           proc     = procFIFO[pTop++];
    617:           flippedA = PetscBTLookup(flippedProcs, proc) ? 1 : 0;
    618:           PetscCall(MatGetRow(G, proc, &numNeighbors, &neighbors, &ornt));
    619:           /* Loop over neighboring procs */
    620:           for (n = 0; n < numNeighbors; ++n) {
    621:             nproc    = neighbors[n];
    622:             mismatch = PetscRealPart(ornt[n]) > 0.5 ? 0 : 1;
    623:             seen     = PetscBTLookup(seenProcs, nproc);
    624:             flippedB = PetscBTLookup(flippedProcs, nproc) ? 1 : 0;

    626:             if (mismatch ^ (flippedA ^ flippedB)) {
    627:               PetscCheck(!seen, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Previously seen procs %" PetscInt_FMT " and %" PetscInt_FMT " do not match: Fault mesh is non-orientable", proc, nproc);
    628:               if (!flippedB) {
    629:                 PetscCall(PetscBTSet(flippedProcs, nproc));
    630:               } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Inconsistent mesh orientation: Fault mesh is non-orientable");
    631:             } else PetscCheck(!mismatch || !flippedA || !flippedB, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempt to flip already flipped cell: Fault mesh is non-orientable");
    632:             if (!seen) {
    633:               procFIFO[pBottom++] = nproc;
    634:               PetscCall(PetscBTSet(seenProcs, nproc));
    635:             }
    636:           }
    637:         }
    638:       }
    639:       PetscCall(PetscFree(procFIFO));
    640:       PetscCall(MatDestroy(&G));
    641:       PetscCall(PetscFree2(adj, val));
    642:       PetscCall(PetscBTDestroy(&seenProcs));
    643:     }
    644:     /* Scatter flip flags */
    645:     {
    646:       PetscBool *flips = NULL;

    648:       if (rank == 0) {
    649:         PetscCall(PetscMalloc1(Noff[size], &flips));
    650:         for (p = 0; p < Noff[size]; ++p) {
    651:           flips[p] = PetscBTLookup(flippedProcs, p) ? PETSC_TRUE : PETSC_FALSE;
    652:           if (flg && flips[p]) PetscCall(PetscPrintf(comm, "Flipping Proc+Comp %d:\n", p));
    653:         }
    654:         for (p = 0; p < size; ++p) displs[p + 1] = displs[p] + Nc[p];
    655:       }
    656:       PetscCallMPI(MPI_Scatterv(flips, Nc, displs, MPIU_BOOL, flipped, numComponents, MPIU_BOOL, 0, comm));
    657:       PetscCall(PetscFree(flips));
    658:     }
    659:     if (rank == 0) PetscCall(PetscBTDestroy(&flippedProcs));
    660:     PetscCall(PetscFree(N));
    661:     PetscCall(PetscFree4(recvcounts, displs, Nc, Noff));
    662:     PetscCall(PetscFree2(nrankComp, match));

    664:     /* Decide whether to flip cells in each component */
    665:     for (c = 0; c < cEnd - cStart; ++c) {
    666:       if (flipped[cellComp[c]]) PetscCall(PetscBTNegate(flippedCells, c));
    667:     }
    668:     PetscCall(PetscFree(flipped));
    669:   }
    670:   if (flg) {
    671:     PetscViewer v;

    673:     PetscCall(PetscViewerASCIIGetStdout(comm, &v));
    674:     PetscCall(PetscViewerASCIIPushSynchronized(v));
    675:     PetscCall(PetscViewerASCIISynchronizedPrintf(v, "[%d]BT for parallel flipped cells:\n", rank));
    676:     PetscCall(PetscBTView(cEnd - cStart, flippedCells, v));
    677:     PetscCall(PetscViewerFlush(v));
    678:     PetscCall(PetscViewerASCIIPopSynchronized(v));
    679:   }
    680:   /* Reverse flipped cells in the mesh */
    681:   for (c = cStart; c < cEnd; ++c) {
    682:     if (PetscBTLookup(flippedCells, c - cStart)) PetscCall(DMPlexOrientPoint(dm, c, -1));
    683:   }
    684:   PetscCall(PetscBTDestroy(&seenCells));
    685:   PetscCall(PetscBTDestroy(&flippedCells));
    686:   PetscCall(PetscBTDestroy(&seenFaces));
    687:   PetscCall(PetscFree2(numNeighbors, neighbors));
    688:   PetscCall(PetscFree3(rorntComp, lorntComp, locSupport));
    689:   PetscCall(PetscFree3(faceFIFO, cellComp, faceComp));
    690:   PetscFunctionReturn(PETSC_SUCCESS);
    691: #endif
    692: }

    694: static PetscErrorCode CreateCellAndFaceIS_Private(DM dm, DMLabel label, IS *cellIS, IS *faceIS)
    695: {
    696:   IS              valueIS;
    697:   const PetscInt *values;
    698:   PetscInt        Nv, depth = 0;

    700:   PetscFunctionBegin;
    701:   PetscCall(DMLabelGetValueIS(label, &valueIS));
    702:   PetscCall(ISGetLocalSize(valueIS, &Nv));
    703:   PetscCall(ISGetIndices(valueIS, &values));
    704:   for (PetscInt v = 0; v < Nv; ++v) {
    705:     const PetscInt val = values[v] < 0 || values[v] >= 100 ? 0 : values[v];
    706:     PetscInt       n;

    708:     PetscCall(DMLabelGetStratumSize(label, val, &n));
    709:     if (!n) continue;
    710:     depth = PetscMax(val, depth);
    711:   }
    712:   PetscCall(ISDestroy(&valueIS));
    713:   PetscCheck(depth >= 1 || !Nv, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Depth for interface must be at least 1, not %" PetscInt_FMT, depth);
    714:   PetscCall(DMLabelGetStratumIS(label, depth, cellIS));
    715:   PetscCall(DMLabelGetStratumIS(label, depth - 1, faceIS));
    716:   if (!*cellIS) PetscCall(ISCreateStride(PETSC_COMM_SELF, 0, 0, 1, cellIS));
    717:   if (!*faceIS) PetscCall(ISCreateStride(PETSC_COMM_SELF, 0, 0, 1, faceIS));
    718:   PetscFunctionReturn(PETSC_SUCCESS);
    719: }

    721: PetscErrorCode DMPlexOrientLabel(DM dm, DMLabel label)
    722: {
    723:   IS cellIS, faceIS;

    725:   PetscFunctionBegin;
    726:   PetscCall(CreateCellAndFaceIS_Private(dm, label, &cellIS, &faceIS));
    727:   PetscCall(DMPlexOrientCells_Internal(dm, cellIS, faceIS));
    728:   PetscCall(ISDestroy(&cellIS));
    729:   PetscCall(ISDestroy(&faceIS));
    730:   PetscFunctionReturn(PETSC_SUCCESS);
    731: }

    733: PetscErrorCode DMPlexOrientCells_Internal(DM dm, IS cellIS, IS faceIS)
    734: {
    735:   MPI_Comm           comm;
    736:   PetscSF            sf;
    737:   const PetscInt    *lpoints;
    738:   const PetscSFNode *rpoints;
    739:   PetscSFNode       *rorntComp = NULL, *lorntComp = NULL;
    740:   PetscInt          *numNeighbors, **neighbors, *locSupp = NULL;
    741:   PetscSFNode       *nrankComp;
    742:   PetscBool         *match, *flipped;
    743:   PetscBT            flippedCells;
    744:   PetscInt          *cellComp, *faceComp;
    745:   const PetscInt    *cells = NULL, *faces = NULL;
    746:   PetscInt           cStart = 0, cEnd = 0, fStart = 0, fEnd = 0;
    747:   PetscInt           numLeaves, numRoots, dim, Ncomp, totNeighbors = 0;
    748:   PetscMPIInt        rank, size;
    749:   PetscBool          view, viewSync;
    750:   PetscViewer        viewer = NULL, selfviewer = NULL;

    752:   PetscFunctionBegin;
    753:   PetscCall(PetscObjectGetComm((PetscObject)dm, &comm));
    754:   PetscCallMPI(MPI_Comm_rank(comm, &rank));
    755:   PetscCallMPI(MPI_Comm_size(comm, &size));
    756:   PetscCall(PetscOptionsHasName(((PetscObject)dm)->options, ((PetscObject)dm)->prefix, "-orientation_view", &view));
    757:   PetscCall(PetscOptionsHasName(((PetscObject)dm)->options, ((PetscObject)dm)->prefix, "-orientation_view_synchronized", &viewSync));

    759:   if (cellIS) PetscCall(ISGetPointRange(cellIS, &cStart, &cEnd, &cells));
    760:   if (faceIS) PetscCall(ISGetPointRange(faceIS, &fStart, &fEnd, &faces));
    761:   PetscCall(DMGetPointSF(dm, &sf));
    762:   PetscCall(PetscSFGetGraph(sf, &numRoots, &numLeaves, &lpoints, &rpoints));
    763:   /* Truth Table
    764:      mismatch    flips   do action   mismatch   flipA ^ flipB   action
    765:          F       0 flips     no         F             F           F
    766:          F       1 flip      yes        F             T           T
    767:          F       2 flips     no         T             F           T
    768:          T       0 flips     yes        T             T           F
    769:          T       1 flip      no
    770:          T       2 flips     yes
    771:   */
    772:   PetscCall(DMGetDimension(dm, &dim));
    773:   PetscCall(PetscBTCreate(cEnd - cStart, &flippedCells));
    774:   PetscCall(PetscBTMemzero(cEnd - cStart, flippedCells));
    775:   PetscCall(PetscCalloc2(cEnd - cStart, &cellComp, fEnd - fStart, &faceComp));
    776:   /*
    777:    OLD STYLE
    778:    - Add an integer array over cells and faces (component) for connected component number
    779:    Foreach component
    780:      - Mark the initial cell as seen
    781:      - Process component as usual
    782:      - Set component for all seenCells
    783:      - Wipe seenCells and seenFaces (flippedCells can stay)
    784:    - Generate parallel adjacency for component using SF and seenFaces
    785:    - Collect Ncomp adj data from each proc to 0
    786:    - Build same serial graph
    787:    - Use same solver
    788:    - Use Scatterv to send back flipped flags for each component
    789:    - Negate flippedCells by component

    791:    NEW STYLE
    792:    - Create the adj on each process
    793:    - Bootstrap to complete graph on proc 0
    794:   */
    795:   PetscCall(DMPlexOrient_Serial(dm, cellIS, faceIS, &Ncomp, cellComp, faceComp, flippedCells));
    796:   if (view) {
    797:     PetscViewer v;
    798:     PetscInt    cdepth = -1;

    800:     PetscCall(PetscViewerASCIIGetStdout(comm, &v));
    801:     PetscCall(PetscViewerASCIIPushSynchronized(v));
    802:     if (cEnd > cStart) PetscCall(DMPlexGetPointDepth(dm, cells ? cells[cStart] : cStart, &cdepth));
    803:     PetscCall(PetscViewerASCIISynchronizedPrintf(v, "[%d]New Orientation %" PetscInt_FMT " cells (depth %" PetscInt_FMT ") and %" PetscInt_FMT " faces\n", rank, cEnd - cStart, cdepth, fEnd - fStart));
    804:     PetscCall(PetscViewerASCIISynchronizedPrintf(v, "[%d]BT for serial flipped cells:\n", rank));
    805:     PetscCall(PetscBTView(cEnd - cStart, flippedCells, v));
    806:     PetscCall(PetscViewerFlush(v));
    807:     PetscCall(PetscViewerASCIIPopSynchronized(v));
    808:   }
    809:   /* Now all subdomains are oriented, but we need a consistent parallel orientation */
    810:   // TODO: This all has to be rewritten to filter cones/supports to the ISes
    811:   if (numLeaves >= 0) {
    812:     PetscInt maxSuppSize, neighbor;

    814:     // Store orientations of boundary faces
    815:     PetscCall(DMPlexGetMaxSizes(dm, NULL, &maxSuppSize));
    816:     PetscCall(PetscCalloc3(numRoots, &rorntComp, numRoots, &lorntComp, maxSuppSize, &locSupp));
    817:     for (PetscInt f = fStart; f < fEnd; ++f) {
    818:       const PetscInt  face = faces ? faces[f] : f;
    819:       const PetscInt *cone, *supp, *ornt;
    820:       PetscInt        coneSize, suppSize, nind, c, Ns = 0;

    822:       PetscCall(DMPlexGetSupportSize(dm, face, &suppSize));
    823:       PetscCall(DMPlexGetSupport(dm, face, &supp));
    824:       for (PetscInt s = 0; s < suppSize; ++s) {
    825:         PetscInt ind, l;

    827:         // Filter support
    828:         ind = GetPointIndex(supp[s], cStart, cEnd, cells);
    829:         if (ind < 0) continue;
    830:         // Ignore overlapping cells
    831:         PetscCall(PetscFindInt(supp[s], numLeaves, lpoints, &l));
    832:         if (l >= 0) continue;
    833:         locSupp[Ns++] = supp[s];
    834:       }
    835:       PetscCheck(Ns < maxSuppSize, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Index %" PetscInt_FMT " exceeds array size %" PetscInt_FMT, Ns, maxSuppSize);
    836:       if (Ns != 1) continue;
    837:       neighbor = locSupp[0];
    838:       nind     = GetPointIndex(neighbor, cStart, cEnd, cells);
    839:       PetscCall(DMPlexGetCone(dm, neighbor, &cone));
    840:       PetscCall(DMPlexGetConeSize(dm, neighbor, &coneSize));
    841:       PetscCall(DMPlexGetConeOrientation(dm, neighbor, &ornt));
    842:       for (c = 0; c < coneSize; ++c)
    843:         if (cone[c] == face) break;
    844:       if (dim == 1) {
    845:         /* Use cone position instead, shifted to -1 or 1 */
    846:         if (PetscBTLookup(flippedCells, nind)) rorntComp[face].rank = (PetscMPIInt)(1 - c * 2);
    847:         else rorntComp[face].rank = (PetscMPIInt)(c * 2 - 1);
    848:       } else {
    849:         if (PetscBTLookup(flippedCells, nind)) rorntComp[face].rank = ornt[c] < 0 ? -1 : 1;
    850:         else rorntComp[face].rank = ornt[c] < 0 ? 1 : -1;
    851:       }
    852:       rorntComp[face].index = faceComp[GetPointIndex(face, fStart, fEnd, faces)];
    853:     }
    854:     // Communicate boundary edge orientations
    855:     PetscCall(PetscSFBcastBegin(sf, MPIU_SF_NODE, rorntComp, lorntComp, MPI_REPLACE));
    856:     PetscCall(PetscSFBcastEnd(sf, MPIU_SF_NODE, rorntComp, lorntComp, MPI_REPLACE));
    857:   }
    858:   /* Get process adjacency */
    859:   PetscCall(PetscMalloc2(Ncomp, &numNeighbors, Ncomp, &neighbors));
    860:   viewer = PETSC_VIEWER_STDOUT_(PetscObjectComm((PetscObject)dm));
    861:   if (viewSync) PetscCall(PetscViewerASCIIPushSynchronized(viewer));
    862:   PetscCall(PetscViewerGetSubViewer(viewer, PETSC_COMM_SELF, &selfviewer));
    863:   for (PetscInt comp = 0; comp < Ncomp; ++comp) {
    864:     PetscInt n;

    866:     numNeighbors[comp] = 0;
    867:     PetscCall(PetscMalloc1(PetscMax(numLeaves, 0), &neighbors[comp]));
    868:     /* I know this is p^2 time in general, but for bounded degree its alright */
    869:     for (PetscInt l = 0; l < numLeaves; ++l) {
    870:       const PetscInt face = lpoints[l];
    871:       PetscInt       find;

    873:       /* Find a representative face (edge) separating pairs of procs */
    874:       find = GetPointIndex(face, fStart, fEnd, faces);
    875:       if ((find >= 0) && (faceComp[find] == comp) && rorntComp[face].rank) {
    876:         const PetscInt rrank = rpoints[l].rank;
    877:         const PetscInt rcomp = lorntComp[face].index;

    879:         for (n = 0; n < numNeighbors[comp]; ++n)
    880:           if ((rrank == rpoints[neighbors[comp][n]].rank) && (rcomp == lorntComp[lpoints[neighbors[comp][n]]].index)) break;
    881:         if (n >= numNeighbors[comp]) {
    882:           const PetscInt *supp;
    883:           PetscInt        suppSize, Ns = 0;

    885:           PetscCall(DMPlexGetSupport(dm, face, &supp));
    886:           PetscCall(DMPlexGetSupportSize(dm, face, &suppSize));
    887:           for (PetscInt s = 0; s < suppSize; ++s) {
    888:             // Filter support
    889:             if (GetPointIndex(supp[s], cStart, cEnd, cells) >= 0) ++Ns;
    890:           }
    891:           PetscCheck(Ns == 1, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Boundary face %" PetscInt_FMT " should see one cell, not %" PetscInt_FMT, face, Ns);
    892:           if (view)
    893:             PetscCall(PetscViewerASCIIPrintf(selfviewer, "[%d]: component %" PetscInt_FMT ", Found representative leaf %" PetscInt_FMT " (face %" PetscInt_FMT ") connecting to face %" PetscInt_FMT " on (%" PetscInt_FMT ", %" PetscInt_FMT ") with orientation %d\n", rank, comp, l, face,
    894:                                              rpoints[l].index, rrank, rcomp, (PetscMPIInt)lorntComp[face].rank));
    895:           neighbors[comp][numNeighbors[comp]++] = l;
    896:         }
    897:       }
    898:     }
    899:     totNeighbors += numNeighbors[comp];
    900:   }
    901:   PetscCall(PetscViewerRestoreSubViewer(viewer, PETSC_COMM_SELF, &selfviewer));
    902:   if (viewSync) PetscCall(PetscViewerASCIIPopSynchronized(viewer));
    903:   PetscCall(PetscMalloc2(totNeighbors, &nrankComp, totNeighbors, &match));
    904:   for (PetscInt comp = 0, off = 0; comp < Ncomp; ++comp) {
    905:     for (PetscInt n = 0; n < numNeighbors[comp]; ++n, ++off) {
    906:       const PetscInt face = lpoints[neighbors[comp][n]];
    907:       const PetscInt o    = rorntComp[face].rank * lorntComp[face].rank;

    909:       if (o < 0) match[off] = PETSC_TRUE;
    910:       else if (o > 0) match[off] = PETSC_FALSE;
    911:       else
    912:         SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Invalid face %" PetscInt_FMT " (%d, %d) neighbor: %" PetscInt_FMT " comp: %" PetscInt_FMT, face, (PetscMPIInt)rorntComp[face].rank, (PetscMPIInt)lorntComp[face].rank, neighbors[comp][n], comp);
    913:       nrankComp[off].rank  = rpoints[neighbors[comp][n]].rank;
    914:       nrankComp[off].index = lorntComp[lpoints[neighbors[comp][n]]].index;
    915:     }
    916:     PetscCall(PetscFree(neighbors[comp]));
    917:   }
    918:   /* Collect the graph on 0 */
    919:   if (numLeaves >= 0) {
    920:     Mat          G;
    921:     PetscBT      seenProcs, flippedProcs;
    922:     PetscInt    *procFIFO, pTop, pBottom;
    923:     PetscInt    *N          = NULL, *Noff;
    924:     PetscSFNode *adj        = NULL;
    925:     PetscBool   *val        = NULL;
    926:     PetscMPIInt *recvcounts = NULL, *displs = NULL, *Nc;
    927:     PetscMPIInt  size = 0, iNcomp, itotNeighbors;

    929:     PetscCall(PetscCalloc1(Ncomp, &flipped));
    930:     if (rank == 0) PetscCallMPI(MPI_Comm_size(comm, &size));
    931:     PetscCall(PetscCalloc4(size, &recvcounts, size + 1, &displs, size, &Nc, size + 1, &Noff));
    932:     PetscCallMPI(MPI_Gather(&Ncomp, 1, MPI_INT, Nc, 1, MPI_INT, 0, comm));
    933:     for (PetscInt p = 0; p < size; ++p) displs[p + 1] = displs[p] + Nc[p];
    934:     if (rank == 0) PetscCall(PetscMalloc1(displs[size], &N));
    935:     PetscCall(PetscMPIIntCast(Ncomp, &iNcomp));
    936:     PetscCallMPI(MPI_Gatherv(numNeighbors, iNcomp, MPIU_INT, N, Nc, displs, MPIU_INT, 0, comm));
    937:     for (PetscInt p = 0, o = 0; p < size; ++p) {
    938:       recvcounts[p] = 0;
    939:       for (PetscInt c = 0; c < Nc[p]; ++c, ++o) recvcounts[p] += N[o];
    940:       displs[p + 1] = displs[p] + recvcounts[p];
    941:     }
    942:     if (rank == 0) PetscCall(PetscMalloc2(displs[size], &adj, displs[size], &val));
    943:     PetscCall(PetscMPIIntCast(totNeighbors, &itotNeighbors));
    944:     PetscCallMPI(MPI_Gatherv(nrankComp, itotNeighbors, MPIU_SF_NODE, adj, recvcounts, displs, MPIU_SF_NODE, 0, comm));
    945:     PetscCallMPI(MPI_Gatherv(match, itotNeighbors, MPIU_BOOL, val, recvcounts, displs, MPIU_BOOL, 0, comm));
    946:     PetscCall(PetscFree2(numNeighbors, neighbors));
    947:     if (rank == 0) {
    948:       for (PetscInt p = 1; p <= size; ++p) Noff[p] = Noff[p - 1] + Nc[p - 1];
    949:       if (view) {
    950:         for (PetscInt p = 0, off = 0; p < size; ++p) {
    951:           for (PetscInt c = 0; c < Nc[p]; ++c) {
    952:             PetscCall(PetscPrintf(PETSC_COMM_SELF, "Proc %" PetscInt_FMT " Comp %" PetscInt_FMT ":\n", p, c));
    953:             for (PetscInt n = 0; n < N[Noff[p] + c]; ++n, ++off) PetscCall(PetscPrintf(PETSC_COMM_SELF, "  edge (%d, %" PetscInt_FMT ") (%s):\n", (PetscMPIInt)adj[off].rank, adj[off].index, PetscBools[val[off]]));
    954:           }
    955:         }
    956:       }
    957:       /* Symmetrize the graph */
    958:       PetscCall(MatCreate(PETSC_COMM_SELF, &G));
    959:       PetscCall(MatSetSizes(G, Noff[size], Noff[size], Noff[size], Noff[size]));
    960:       PetscCall(MatSetUp(G));
    961:       for (PetscInt p = 0, off = 0; p < size; ++p) {
    962:         for (PetscInt c = 0; c < Nc[p]; ++c) {
    963:           const PetscInt r = Noff[p] + c;

    965:           for (PetscInt n = 0; n < N[r]; ++n, ++off) {
    966:             const PetscInt    q = Noff[adj[off].rank] + adj[off].index;
    967:             const PetscScalar o = val[off] ? 1.0 : 0.0;

    969:             PetscCall(MatSetValues(G, 1, &r, 1, &q, &o, INSERT_VALUES));
    970:             PetscCall(MatSetValues(G, 1, &q, 1, &r, &o, INSERT_VALUES));
    971:           }
    972:         }
    973:       }
    974:       PetscCall(MatAssemblyBegin(G, MAT_FINAL_ASSEMBLY));
    975:       PetscCall(MatAssemblyEnd(G, MAT_FINAL_ASSEMBLY));

    977:       PetscCall(PetscBTCreate(Noff[size], &seenProcs));
    978:       PetscCall(PetscBTMemzero(Noff[size], seenProcs));
    979:       PetscCall(PetscBTCreate(Noff[size], &flippedProcs));
    980:       PetscCall(PetscBTMemzero(Noff[size], flippedProcs));
    981:       PetscCall(PetscMalloc1(Noff[size], &procFIFO));
    982:       pTop = pBottom = 0;
    983:       for (PetscInt p = 0; p < Noff[size]; ++p) {
    984:         if (PetscBTLookup(seenProcs, p)) continue;
    985:         /* Initialize FIFO with next proc */
    986:         procFIFO[pBottom++] = p;
    987:         PetscCall(PetscBTSet(seenProcs, p));
    988:         /* Consider each proc in FIFO */
    989:         while (pTop < pBottom) {
    990:           const PetscScalar *ornt;
    991:           const PetscInt    *neighbors;
    992:           PetscInt           proc, nproc, seen, flippedA, flippedB, mismatch, numNeighbors;

    994:           proc     = procFIFO[pTop++];
    995:           flippedA = PetscBTLookup(flippedProcs, proc) ? 1 : 0;
    996:           PetscCall(MatGetRow(G, proc, &numNeighbors, &neighbors, &ornt));
    997:           /* Loop over neighboring procs */
    998:           for (PetscInt n = 0; n < numNeighbors; ++n) {
    999:             nproc    = neighbors[n];
    1000:             mismatch = PetscRealPart(ornt[n]) > 0.5 ? 0 : 1;
    1001:             seen     = PetscBTLookup(seenProcs, nproc);
    1002:             flippedB = PetscBTLookup(flippedProcs, nproc) ? 1 : 0;

    1004:             if (mismatch ^ (flippedA ^ flippedB)) {
    1005:               PetscCheck(!seen, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Previously seen procs %" PetscInt_FMT " and %" PetscInt_FMT " do not match: Fault mesh is non-orientable", proc, nproc);
    1006:               if (!flippedB) {
    1007:                 PetscCall(PetscBTSet(flippedProcs, nproc));
    1008:               } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Inconsistent mesh orientation: Fault mesh is non-orientable");
    1009:             } else PetscCheck(!mismatch || !flippedA || !flippedB, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempt to flip already flipped cell: Fault mesh is non-orientable");
    1010:             if (!seen) {
    1011:               procFIFO[pBottom++] = nproc;
    1012:               PetscCall(PetscBTSet(seenProcs, nproc));
    1013:             }
    1014:           }
    1015:         }
    1016:       }
    1017:       PetscCall(PetscFree(procFIFO));
    1018:       PetscCall(MatDestroy(&G));
    1019:       PetscCall(PetscFree2(adj, val));
    1020:       PetscCall(PetscBTDestroy(&seenProcs));
    1021:     }
    1022:     /* Scatter flip flags */
    1023:     {
    1024:       PetscBool *flips = NULL;

    1026:       if (rank == 0) {
    1027:         PetscCall(PetscMalloc1(Noff[size], &flips));
    1028:         for (PetscInt p = 0; p < Noff[size]; ++p) {
    1029:           flips[p] = PetscBTLookup(flippedProcs, p) ? PETSC_TRUE : PETSC_FALSE;
    1030:           if (view && flips[p]) PetscCall(PetscPrintf(comm, "Flipping Proc+Comp %" PetscInt_FMT ":\n", p));
    1031:         }
    1032:         for (PetscInt p = 0; p < size; ++p) displs[p + 1] = displs[p] + Nc[p];
    1033:       }
    1034:       PetscCall(PetscMPIIntCast(Ncomp, &iNcomp));
    1035:       PetscCallMPI(MPI_Scatterv(flips, Nc, displs, MPIU_BOOL, flipped, iNcomp, MPIU_BOOL, 0, comm));
    1036:       PetscCall(PetscFree(flips));
    1037:     }
    1038:     if (rank == 0) PetscCall(PetscBTDestroy(&flippedProcs));
    1039:     PetscCall(PetscFree(N));
    1040:     PetscCall(PetscFree4(recvcounts, displs, Nc, Noff));
    1041:     PetscCall(PetscFree2(nrankComp, match));

    1043:     /* Decide whether to flip cells in each component */
    1044:     for (PetscInt c = 0; c < cEnd - cStart; ++c) {
    1045:       if (flipped[cellComp[c]]) PetscCall(PetscBTNegate(flippedCells, c));
    1046:     }
    1047:     PetscCall(PetscFree(flipped));
    1048:   }
    1049:   if (view) {
    1050:     PetscViewer v;

    1052:     PetscCall(PetscViewerASCIIGetStdout(comm, &v));
    1053:     PetscCall(PetscViewerASCIIPushSynchronized(v));
    1054:     PetscCall(PetscViewerASCIISynchronizedPrintf(v, "[%d]BT for parallel flipped cells:\n", rank));
    1055:     PetscCall(PetscBTView(cEnd - cStart, flippedCells, v));
    1056:     PetscCall(PetscViewerFlush(v));
    1057:     PetscCall(PetscViewerASCIIPopSynchronized(v));
    1058:   }
    1059:   // Reverse flipped cells in the mesh
    1060:   PetscViewer     v;
    1061:   const PetscInt *degree = NULL;
    1062:   PetscInt       *points;
    1063:   PetscInt        pStart, pEnd;

    1065:   if (view) {
    1066:     PetscCall(PetscViewerASCIIGetStdout(comm, &v));
    1067:     PetscCall(PetscViewerASCIIPushSynchronized(v));
    1068:   }
    1069:   PetscCall(DMPlexGetChart(dm, &pStart, &pEnd));
    1070:   if (numRoots >= 0) {
    1071:     PetscCall(PetscSFComputeDegreeBegin(sf, &degree));
    1072:     PetscCall(PetscSFComputeDegreeEnd(sf, &degree));
    1073:   }
    1074:   PetscCall(PetscCalloc1(pEnd - pStart, &points));
    1075:   for (PetscInt c = cStart; c < cEnd; ++c) {
    1076:     if (PetscBTLookup(flippedCells, c - cStart)) {
    1077:       const PetscInt cell = cells ? cells[c] : c;

    1079:       PetscCall(DMPlexOrientPoint(dm, cell, -1));
    1080:       if (degree && degree[cell]) points[cell] = 1;
    1081:       if (view) PetscCall(PetscViewerASCIISynchronizedPrintf(v, "[%d]Flipping cell %" PetscInt_FMT "%s\n", rank, cell, degree && degree[cell] ? " and sending to overlap" : ""));
    1082:     }
    1083:   }
    1084:   // Must propagate flips for cells in the overlap
    1085:   if (numRoots >= 0) {
    1086:     PetscCall(PetscSFBcastBegin(sf, MPIU_INT, points, points, MPI_SUM));
    1087:     PetscCall(PetscSFBcastEnd(sf, MPIU_INT, points, points, MPI_SUM));
    1088:   }
    1089:   for (PetscInt c = cStart; c < cEnd; ++c) {
    1090:     const PetscInt cell = cells ? cells[c] : c;

    1092:     if (points[cell] && !PetscBTLookup(flippedCells, c - cStart)) {
    1093:       PetscCall(DMPlexOrientPoint(dm, cell, -1));
    1094:       if (view) PetscCall(PetscViewerASCIISynchronizedPrintf(v, "[%d]Flipping cell %" PetscInt_FMT " through overlap\n", rank, cell));
    1095:     }
    1096:   }
    1097:   if (view) {
    1098:     PetscCall(PetscViewerFlush(v));
    1099:     PetscCall(PetscViewerASCIIPopSynchronized(v));
    1100:   }
    1101:   PetscCall(PetscFree(points));
    1102:   PetscCall(PetscBTDestroy(&flippedCells));
    1103:   PetscCall(PetscFree2(numNeighbors, neighbors));
    1104:   PetscCall(PetscFree3(rorntComp, lorntComp, locSupp));
    1105:   PetscCall(PetscFree2(cellComp, faceComp));
    1106:   PetscFunctionReturn(PETSC_SUCCESS);
    1107: }