Click here to Skip to main content
15,358,692 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
As a sidenote, this question targets JavaScript but I know some other languages like C#, so solutions providing pseudo code will be fine for me :)

---

I have a client application consuming data from an external API based on a configuration during startup.

Since calculating the necessary data is not easy for me, I tried to fake the implementation and calculate it locally for now.

There are many WorkItems linked to each other and the configuration only knows about the relations to consider.

---

Some explanations:

Workitem

A workitem has a unique id and a type

e.g.

JavaScript
{
    id: 1,
    type: "person"
}


so you know that Workitem 1 is of type person

Linkrole

A linkrole is a composite key of three keys

- The parrent workitem type
- The child workitem type
- The name of the role

e.g.

JavaScript
{
    parentWorkItemType: "person",
    childWorkItemType: "house",
    name: "owns",
}


which represents Person owns House

Links

The backend knows about the relations, a link between workitems might look like

JavaScript
{
    /* each link is unique */
    linkRole: {
        parentWorkItemType: "person",
        childWorkItemType: "house",
        name: "owns",
    },
    parentId: 1,
    childId: 2
}


so you know that Person 1 owns House 2

---

Fake prerequisites:

Fake backend

I created some fake data for my calculations. The file backend.js represents the backend / database

JavaScript
// backend.js

export const workItems = [{
    id: 1,
    type: "car"
}, {
    id: 2,
    type: "car"
}, {
    id: 3,
    type: "bird"
}, {
    id: 4,
    type: "bird"
}, {
    id: 5,
    type: "bird"
}, {
    id: 6,
    type: "invalid"
}, {
    id: 7,
    type: "house"
}, {
    id: 8,
    type: "house"
}, {
    id: 9,
    type: "house",
}, {
    id: 10,
    type: "person",
}];

export const workItemLinks = [{
    linkRole: {
        parentWorkItemType: "car",
        childWorkItemType: "bird",
        name: "isChildOf",
    },
    parentId: 1,
    childId: 3
}, {
    linkRole: {
        parentWorkItemType: "car",
        childWorkItemType: "bird",
        name: "isChildOf",
    },
    parentId: 1,
    childId: 4
}, {
    linkRole: {
        parentWorkItemType: "bird",
        childWorkItemType: "house",
        name: "with",
    },
    parentId: 3,
    childId: 7
}, {
    linkRole: {
        parentWorkItemType: "bird",
        childWorkItemType: "house",
        name: "with",
    },
    parentId: 3,
    childId: 8
}, {
    linkRole: {
        parentWorkItemType: "person",
        childWorkItemType: "car",
        name: "owns",
    },
    parentId: 10,
    childId: 1
}, {
    linkRole: {
        parentWorkItemType: "car",
        childWorkItemType: "car",
        name: "references",
    },
    parentId: 1,
    childId: 2
}];


Fake API

I created some methods inside the file api.js to fake an API asking the backend for data.

Important sidenote: These methods just help me to find the data I need. I can add more "helpers" if needed (In the real world I can ask to add more API endpoints) so everything can be queried. Please feel free to modify the "Fake API".

JavaScript
// api.js

import { workItems, workItemLinks } from "./backend.js";

export function getWorkItemsByType(workItemType) {
    return workItems.filter(workItem => workItem.type === workItemType);
}

export function getWorkItemsByIds(workItemIds) {
    return workItems.filter(workItem => workItemIds.some(workItemId => workItemId === workItem.id));
}

export function getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideIds, leftSideIsParentSide) {
    return workItemLinks.filter(workItemLink => {
        
        // Pseudo equality check
        
        if (workItemLink.linkRole.parentWorkItemType === linkRole.parentWorkItemType &&
            workItemLink.linkRole.childWorkItemType === linkRole.childWorkItemType &&
            workItemLink.linkRole.name === linkRole.name) {
            const leftSideIdInLink = leftSideIsParentSide ? workItemLink.parentId : workItemLink.childId;

            // Return this link if it matches with the left side id ( you're looking for the right side id )

            return leftSideIds.some(leftSideId => leftSideId === leftSideIdInLink);
        }
        
        return false;
    });
}


Fake configuration

I created definitions inside configuration.js to start the calculations based on those

JavaScript
// configuration.js

export const definitions = [
    {                                           // fetch linked birds from every root car
        linkRole: {                             
            parentWorkItemType: "car",
            childWorkItemType: "bird",
            name: "isChildOf",
        }
    },
    {                                           // !! Root Element !! Fetch work items based on type
        workItemType: "car",
        isRootWorkItem: true
    },
    {                                            // fetch linked houses from every bird ( car - bird - house )
        linkRole: {                            
            parentWorkItemType: "bird",
            childWorkItemType: "house",
            name: "with",
        }
    },
    {                                             // fetch every person from every car ( person - car )
        linkRole: {
            parentWorkItemType: "person",
            childWorkItemType: "car",
            name: "owns",
        }
    },
    {                                          // Self reference, fetch linked cars from every root car
        linkRole: {
            parentWorkItemType: "car",
            childWorkItemType: "car",
            name: "references",
        }
    },
];


---

Problem to solve:

I am looking for a performant way to fetch every related link and workitem from the backend based on the chain of relations starting with each root item.

Expected output based on the configuration:

JavaScript
export const workItems = [{
    id: 1,
    type: "car"
}, {
    id: 2,
    type: "car"
}, {
    id: 3,
    type: "bird"
}, {
    id: 4,
    type: "bird"
}, /* no car is linked to bird 5, no links for invalid 6 */ {
    id: 7,
    type: "house"
}, {
    id: 8,
    type: "house"
}, /* no bird is linked to house 9 */ {
    id: 10,
    type: "person",
}];

/* based on the configuration every workItemLink from the backend got fetched */


What I have tried:

JavaScript
import { inspect } from "util";

import { getWorkItemsByType, getWorkItemsByIds, getWorkItemLinksByLinkRoleAndLeftSideIds } from "./api.js";
import { definitions } from "./configuration.js";

// Find the root definition

const { workItemType: rootWorkItemType } = definitions.find(definition => definition.isRootWorkItem);

// Fetch all the root workitems and initialize the store holding unique workitems

const workItems = getWorkItemsByType(rootWorkItemType); // will hold car 1 and car 2

const initialWorkItemIds = workItems.map(workItem => workItem.id);

const workItemIdsToLoad = []; // try to read all missing ids from fetched links and fetch all the workitems at once later on

const workItemLinks = []; // global store for links



const definitionsToTraverse = definitions.filter(definition => definition.linkRole !== undefined); // do not consider the root definition



run(initialWorkItemIds, rootWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks);




const missingWorkItemIdsToLoad = workItemIdsToLoad.filter(workItemIdToLoad => !rootWorkItemIds.some(rootWorkItemId => rootWorkItemId === workItemIdToLoad)); // filter out all the existing root item ids

const workItemsToAdd = getWorkItemsByIds(missingWorkItemIdsToLoad); // fetch all the missing workitems at once

workItems.push(...workItemsToAdd); // add them to the global store








console.log(inspect({
    workItems,
    workItemLinks
}, false, null, true))









function run(leftSideWorkItemIds, leftSideWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks) {
    /* 
    
        consider all the defitions from "definitionsToTraverse" directly related to "leftSideWorkItemType"
        remove them from "definitionsToTraverse" to prevent endless loops
        loop backwards so splice won't struggle with the indices

    */

    for (let definitionIndex = definitionsToTraverse.length - 1; definitionIndex >= 0; definitionIndex--) { 
        const currentDefinition = definitionsToTraverse[definitionIndex];
        const { linkRole } = currentDefinition;
        const { parentWorkItemType, childWorkItemType } = linkRole;

        const leftSideWorkItemTypeIsParent = parentWorkItemType === leftSideWorkItemType;
        const leftSideWorkItemTypeIsChild = childWorkItemType === leftSideWorkItemType;

        // Check the direct relation

        if (leftSideWorkItemTypeIsParent || leftSideWorkItemTypeIsChild) {
            // Remove the inspected definition

            definitionsToTraverse.splice(definitionIndex, 1);

            const relatedWorkItemLinks = getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideWorkItemIds, leftSideWorkItemTypeIsParent);

            // store all the right side workitem IDs for the next run

            const rightSideWorkItemIds = [];

            for (let relatedWorkItemLinkIndex = 0; relatedWorkItemLinkIndex < relatedWorkItemLinks.length; relatedWorkItemLinkIndex++) {
                const relatedWorkItemLink = relatedWorkItemLinks[relatedWorkItemLinkIndex];
                
                // Process the link if not processed yet
    
                if (!workItemLinks.some(workItemLink => /* !!! pseudo equality check !!! */
                        workItemLink.linkRole.parentWorkItemType === relatedWorkItemLink.linkRole.parentWorkItemType &&
                        workItemLink.linkRole.childWorkItemType === relatedWorkItemLink.linkRole.childWorkItemType &&
                        workItemLink.linkRole.name === relatedWorkItemLink.linkRole.name &&
                        workItemLink.parentId === relatedWorkItemLink.parentId &&
                        workItemLink.childId === relatedWorkItemLink.childId)) {
                    
                    // Push the link to the store
            
                    workItemLinks.push(relatedWorkItemLink);
    
                    // Get the right side id from the link

                    const rightSideWorkItemId = leftSideWorkItemTypeIsParent ? relatedWorkItemLink.childId : relatedWorkItemLink.parentId;
    
                    rightSideWorkItemIds.push(rightSideWorkItemId);

                    // Push the id to the store if it doesn't exist

                    if (!workItemIdsToLoad.some(workItemIdToLoad => workItemIdToLoad === rightSideWorkItemId)) {
                        workItemIdsToLoad.push(rightSideWorkItemId);
                    }
                }
            }

            // Find the opposite workitem type of the current definition

            const rightSideWorkItemType = leftSideWorkItemTypeIsParent ? childWorkItemType : parentWorkItemType;

            // Run again but use this definition as the previous one

            run(rightSideWorkItemIds, rightSideWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks);
        }
    }
}


The problem is that my approach crashes because the backwards loop even runs if definitionsToTraverse is empty. And I'm mutating the arrays from the parameters directly, I think I shouldn't do that.

So any help would be appreciated a lot!
Posted
Comments
BillWoodruff 11-Feb-22 18:13pm
   
a node can have only one child node ? that's a linked list ?

what is the reason you need to traverse up and down at the same time ?
Oliver Bleckmann 12-Mar-22 6:33am
   
I think he/she is trying to reassemble a graph-database that was serialized to a hierarchy with additional rules. The problem is that reference cycles can occur. So, two problems here restoring a graph is hard e.g. Newtonsoft Json reports on self referencing loops. Second, implementing a rule engine is hard, because a practical approach heavily depends on the rules to consider AND a mathematically DETERMINISTIC description of the information to be restored. It may be impossible to restore due to conceptional mistakes. A person 'has' a house AND a person 'has' a car AND the car 'isin' the house. Loop! Person->house->car->person, but a car can also be in the house of another person, no loop, go on traversing... So, it heavily depends on the implementation. No general answer how to resolve this. I can see one way here, as the work items have a unique id, traversing should stop as soon as a work item has been FULLY processed. So you need to 'await' on each work item till its descendants have a back reference to the item OR the whole list of items has been processed. Possibly inefficent. This could be a perfect example that SHOULD NOT be solved recursivly! The problem is, depending on the rules you may have what I would call 'path dependencies'. As soon has there are 'hasMany' relations, all possiple paths of a matrix of all workItems can be related to (maybe) all other matrices by the specific path taken by the applied rules. If these rules introduce bidirectional interdependencies or complex rules like a person can only have a car if there is a garage. GAME OVER! A deterministic approach: process each item just one level of depth applying each rule THEN repeat with the next depth and just STOP at a certain depth.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900