Finding Shortest Path Between Related Persons (with dbd)

This example stores relation****ps between persons (see script below)
in a lightweight, memory-resident database. Next, C-code (see further
below) processes the data to find the shortest path between specified
persons. Unlike traditional dbs that store data as values in table-
like structures, dbd stores data as a network of nodes where each node
is equivalent to an AND gate. For more details, see
www.dbfordummies.com/temp/ExPathBetwPersons.asp

(; Create persons)
(new 'john 'person)
(new 'mary 'person)
(new 'mickey  'person)
(new 'sue 'person)
(new 'bob 'person)
(new 'jill 'person)
(new 'jack 'person)

(; Create types of relation****ps)
(new 'friend 'relation****p)
(new 'father 'relation****p)
(new 'mother 'relation****p)
(new 'husband 'relation****p)
(new 'wife 'relation****p)
(new 'son 'relation****p)
(new 'daughter 'relation****p)
(new 'brother 'relation****p)
(new 'sister 'relation****p)
(new 'employer 'relation****p)
(new 'employee 'relation****p)

(; Note: relation****ps between persons
   forms a Y figure with mickey at center)
(set mickey daughter mary)
(set mary father mickey)

(set mary husband john)
(set john wife mary)


(set mickey friend sue)
(set sue friend mickey)

(set sue brother bob)
(set bob sister sue)


(set mickey daughter jill)
(set jill father mickey)

(set jill employer jack)
(set jack employee jill)


/
*****************************************************************************
*****************************************************************************/
#define kMaxDeg 6

int main()
{
  int* pMickey = AStr_getDefN(_T("mickey"));
  int* pJohn = AStr_getDefN(_T("john"));
  PathBetwPersons_get(pMickey, pJohn, kMaxDeg);
}

/
*****************************************************************************
*****************************************************************************/
int* PathBetwPersons_get(int* pPer1, int* pPer2, int nMax)
{
  int* pP[kMaxDeg] = {0, 0, 0, 0, 0, 0};
  int pathInx = 0;
  int* pSP[kMaxDeg] = {0, 0, 0, 0, 0, 0};
  int sPathInx = 999;
  if (PathBetwPersons_getSub(pPer1, pPer2, nMax, pP, pathInx, pSP,
sPathInx)){
    // Create ie
    // "path from john to mary is (john friend matt) (matt sister
mary)"
    // in db
      int* pA1[256]; int* p1 = (int*)pA1;
      int* pPath = AStr_getDefN(_T("path"));
      if (!pPath){
        pPath = N_create();
        N_Name_setWithAStr(pPath, _T("path"));
        N_SVO_set(pDbDb_g, pItem_g, pPath);
      }
      int* pB[13] = {Xp_Node(pPath, p1),
                     Xp_Node(pPrepFrom_g, p1),
                     Xp_Node(pPer1, p1),
                     Xp_Node(pPrepTo_g, p1),
                     Xp_Node(pPer2, p1),
                     Xp_Node(pTenseIs_g, p1)};
      for (int x=0; x < kMaxDeg; ++x){
        if (pSP[x]){
          pB[x+6] = Xp_Node(pSP[x], p1);
        }
        else{
          pB[x+6] = NULL;
        }
      }
      pB[12] = NULL;

      int* eQ2 = Xp_SeqX_getElseCreate((int*)pB, p1);
      return Xp_execute(eQ2);
  }

  return NULL;
}

/
*****************************************************************************
Finds shortest path between persons (pPer1 & pPer2)
and stores it in db as
"path from pPer1 to pPer2 is (pPer1 rel1 pPerX) ... (pPerX rel2
pPer2)"
where rel1, rel2, ... are intances of relation****p (ie friend, father,
etc).

For example:
"path from john to mary is (john friend suzy) (suzy sister mary)"

nMax  - maximum number of relation****ps to search.
pP    - an array that holds current path from pPer1 to pPer2
pathInx  - index at which next relation****p can be stored in pP.
           caller must init to 0.
pSP   - an array that holds shortest path from pPer1 to pPer2.
sPathInx - short path index.
*****************************************************************************/
int* PathBetwPersons_getSub(int* pPer1, int* pPer2, int nMax,
                                       int* pP[kMaxDeg], int &pathInx,
                                       int* pSP[kMaxDeg], int
&sPathInx)
{
  // If no path between pPer1 and pPer2 in nMax relation****ps
    if (nMax <= pathInx){
      // Terminate recursions
        return NULL;
    }

  // Get person that starts current relation****p
    int* pPerS = pPer1;
    if (pathInx){
      pPerS = N_getElem(pP[pathInx-1]);
    }

  // (get perA (get relation****p instance *) per2)
    int* pA1[128]; int* p1 = (int*)pA1;
    int* pRel = AStr_getDefN(_T("relation****p"));
    int* eRel = Xp_Node(pRel, p1);
    int* eInst = Xp_Node(pInst_g, p1);
    int* eQ1 = Xp_SV_getO(eRel, eInst, p1);
    int* ePerA = Xp_Node(pPerS, p1);
    int* ePer2 = Xp_Node(pPer2, p1);
    int* eQ2 = Xp_SVO_get(ePerA, eQ1, ePer2, p1);
    int* pSVO = Xp_execute(eQ2);
    if (pSVO){
      // Path found, store in array
        pP[pathInx++] = pSVO;

      // If new path is shorter
        if (pathInx < sPathInx){
          // Save new shortest path
            for (int x=0; x < kMaxDeg; ++x){
              pSP[x] = pP[x];
            }
            sPathInx = pathInx;
        }

      return pSVO;
    }

  // No relation****p between pPerS and pPer2 found
  // Loop thru all relation****ps between pPerS and pPerX
    int* eQ3 = Xp_SV_getSVO(ePerA, eQ1, p1);
    Xp_Inps_reset(eQ3, FALSE);
    while (int* pPerS_Rel_PerX=Xp_execute(eQ3)){
      // Continue if PerX already in stored path
        int* pPerX = N_getElem(pPerS_Rel_PerX);
        if (pPerX == pPer1){
          continue;
        }
        for (int x=0; x < nMax; ++x){
          if (pP[x]){
            if (pPerX == N_getElem(pP[x])){
              continue;
            }
          }
        }

      // Recurse
        pP[pathInx++] = pPerS_Rel_PerX;
        if (int* pFnd=PathBetwPersons_getSub(pPer1, pPer2, nMax,
                                   pP, pathInx, pSP, sPathInx)){
          return pFnd;
        }
        pP[--pathInx] = NULL;
    }

  return NULL;
}