Finding Shortest Path Between Related Persons (with dbd)

This example stores relationships 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 relationships)
(new 'friend 'relationship)
(new 'father 'relationship)
(new 'mother 'relationship)
(new 'husband 'relationship)
(new 'wife 'relationship)
(new 'son 'relationship)
(new 'daughter 'relationship)
(new 'brother 'relationship)
(new 'sister 'relationship)
(new 'employer 'relationship)
(new 'employee 'relationship)

(; Note: relationships 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 relationship (ie friend, father,
etc).

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

nMax - maximum number of relationships to search.
pP - an array that holds current path from pPer1 to pPer2
pathInx - index at which next relationship 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 relationships
if (nMax <= pathInx){
// Terminate recursions
return NULL;
}

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

// (get perA (get relationship instance *) per2)
int* pA1[128]; int* p1 = (int*)pA1;
int* pRel = AStr_getDefN(_T("relationship"));
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 relationship between pPerS and pPer2 found
// Loop thru all relationships 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;
}

.