Procedure

Input: A set S of relations of the form EQ(A,B), EC(A,B), TPP(A,B), 
NTPP(A,B), OV(A,B), DC(A,B) (the RCC-8 relations) and also DS(A,B), 
O(A,B), PP(A,B).


Output: A diagram of disconnected regions that satisfy S.

main (START : set of constraints)
   {  eliminateEQs(S);
      OLD := emptyset;
      S := START;
      for (CONSTRAINT in START) propagate(CONSTRAINT);
      generateSupplementaries();
      diagram();
    }


procedure assert(R(A,B))
    { add R(A,B) to OLD;
      if (R(A,B) not in S) add R(A,B) to S;
    }

procedure eliminateEQs(S)
for (every relation EQ(A,B) in S)
    { replace B by A throughout S;
      delete this relation from S.
      (Be sure, however, that in the eventual diagram the region is 
         labelled both A and B.);
    }

propagate(CONSTRAINT)
  let CONSTRAINT=R(A,B);
  case (R)
    { NTPP : propagateNTPP(A,B);
      TPP:   propagateTPP(A,B)
      OV:    propagateOV(A,B)
      EC:    propagateEC(A,B)
      DC:    propagateDC(A,B)
      PP:    propagatePP(A,B)
      O:     propagateO(A,B)
      DS:    propagateDS(A,B)
   }

procedure propagateNTPP(A,B)
{  if (NTPP(A,B) in OLD) return;
   if ((A==B) or (TPP(A,B) in S)) fail;
   assert(NTPP(A,B));
   propagatePP(A,B);
   for (every region C)
     { if (DC(B,C) or EC(B,C) or DS(B,C) in S) assert DC(A,C);
       if (EC(A,C) in S) propagateO(B,C);
       if (PP(B,C) in S) propagateNTPP(A,C));
     }
}

procedure propagateTPP(A,B)
{ if (TPP(A,B) in OLD) return;
  if ((A==B) or (NTPP(A,B) in S)) fail;
  assert(TPP(A,B));
  propagatePP(A,B);
}
  
procedure propagatePP(A,B)
{ if (PP(A,B) in OLD) return;
  assert(PP(A,B));
  if ((A==B) or (PP(B,A) or OV(A,B) or in S) fail;
  propagateO(A,B);
  for (every region C)
   { if (NTPP(B,C) in S) propagateNTPP(A,C);
     if (TPP(B,C) or PP(B,C) in S) propagatePP(A,C);
     if (DC(B,C) in S) propagateDC(A,C);
     if (EC(B,C) or DS(B,C) in S) propagateDS(A,C);
     if (PP(A,C) in S) propagateO(B,C);
   }
}
  
procedure propagateOV(A,B)
{ if (OV(A,B)  in OLD) return;
  assert(OV(A,B));
  assert(OV(B,A));
  if ((A==B) or (PP(A,B) or PP(B,A) in S) fail;
  propagateO(A,B);
}
  
procedure propagateO(A,B)
{ if (O(A,B) in OLD) return;
  assert(O(A,B));
  assert(O(B,A));
  if ((A==B) or DS(A,B) in S) fail;
  for (each region C)
    if (PP(B,C) in S) propagateO(A,C);
    if (PP(A,C) in S) propagateO(B,C);
}

propagateEC(A,B)
{ if (EC(A,B) in OLD) return;
  assert(EC(A,B));
  assert(EC(B,A));
  if (A==B or DC(A,B) in S) fail;
  propagateDS(A,B);
}
  
propagateDC(A,B)
{ if (DC(A,B) in OLD) return;
  assert(DC(A,B));
  assert(DC(B,A));
  if (A==B or EC(A,B) in S) fail;
  propagateDS(A,B);
}

propagateDS(A,B)
{ if (DS(A,B) in OLD) return;
  if (A==B or O(A,B) in S) fail;
  assert(DS(A,B));
  assert(DS(B,A));
} 

procedure generateSupplementaries()
{ generateOV();
  generatePP();
  generateContacts();
} 


procedure generateO()
{ for (all regions A,B such that O(A,B))
   { if ((PP(A,B) is not in S) and (PP (B,A) is not in S) and
        there is no region R such that PP(R,A) and PP(R,B))
        then { create a new region R;
               propagatePP(R,A);
               propagatePP(R,B);
             }
     if (OV(A,B)) {
       if (there is no region R such that PP(R,A) and DS(R,B))
          then { create a new region R;
                 propagatePP(R,A);
                 propagateDS(R,B);
               }
       if (there is no region R such that PP(R,B) and DS(R,A))
          then { create a new region R;
                 propagatePP(R,B);
                 propagateDS(R,A);
               }
      }
     }
}

/* Note: if NTPP(A,B) then the existence of B-A is taken care of
in diagram generation */

procedure generatePP() 
{ for (all regions A,B such that PP(A,B) and not NTPP(A,B))
    if (there is no region R such that PP(R,B) and DS(R,A))
     then { create a new region R;
            propagatePP(R,B);
            propagateDS(R,A);
          }
}

procedure generateContacts ()
{ mark all constraints EC(A,B) or TPP(A,B) as "unsatisfied";
  repeat (until all constraints are satisfied)
     { let R(A,B) be an unsatisfied constraint;
       mark R(A,B) as satisfied;
       Q := { A,B } /* Q is a set of regions */
       for (every unsatisfied constraint R1(C,D))
        { if (C is in Q and D is not in Q and
              (there is no (E in Q) for which DC(E,D) or NTPP(E,D) in S)
           then { add D to Q;
                  mark R1(C,D) as satisfied;
                } 
        }
       generate a new point P;
       for (C in Q) add BdPt(P,C)
     }
}