如何通過在兩個方向（父親和孩子）遍歷它們來找到所有節點及其與其他節點的鏈接？-有解無憂

我有一個客戶端應用程式在啟動期間根據配置使用來自外部 API 的資料。

由于計算必要的資料對我來說并不容易，所以我嘗試偽造實作并暫時在本地計算。

有許多相互鏈接的WorkItems，配置只知道要考慮的關系。

一些解釋：

作業專案

作業項具有唯一的 id 和型別

例如

{
    id: 1,
    type: "person"
}

所以你知道Workitem 1 是 person 型別

鏈接角色

鏈接角色是三個鍵的組合鍵

父作業項型別
子作業項型別
角色名稱

例如

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

代表人擁有房子

鏈接

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

{
    /* 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

// 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".

// 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

// 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:

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 */

My first implementation approach:

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!

uj5u.com熱心網友回復：

更新：添加了一個更清晰的代碼版本。之前的實作讓我很困擾。

我可能過于簡化了你需要在這里做的事情。我正在按照我對這個問題的評論中的描述來處理這個問題：

我有這個權利嗎？你（這里）有一個單根型別的汽車。所以你想包括兩輛車，然后你想在鏈接中包括所有以這些車作為父值或子值的節點，然后在鏈接中包括所有具有這些結果的節點，以此類推，將所有結果收集到一個簡單的串列中而不是樹中。

如果這是正確的，那么這似乎是一種合理的方法：

const getLinkedIds = (links, ids, toAdd = links 
  .filter (({childId, parentId}) => ids .includes (childId) || ids .includes (parentId))
  .flatMap (({childId, parentId}) => [childId, parentId])
  .filter (id => !ids .includes (id))
) => toAdd .length == 0 ? ids : getLinkedIds (links, ids .concat (toAdd))


const linkedItems = (defs, items, links, 
  rootTypes = defs.filter (({isRootWorkItem = false}) => isRootWorkItem) 
    .map (({workItemType}) => workItemType),
  roots = items .filter (({type}) => rootTypes .includes (type)),
  ids = getLinkedIds (links, roots.flatMap (({id}) => id))
) => items .filter (({id}) => ids .includes (id))


const definitions = [ /* linkTypes deleted */  {workItemType: "car", isRootWorkItem: true}]
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"}]
const workItemLinks = [ /* linkTypes deleted */ {parentId: 1, childId: 3}, {parentId: 1, childId: 4}, {parentId: 3, childId: 7}, {parentId: 3, childId: 8}, {parentId: 10, childId: 1}, {parentId: 1, childId: 2}]

console .log (
  linkedItems (definitions, workItems, workItemLinks)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

在linkedItems中，我們從定義開始收集根型別，然后使用這些定義收集所有根元素。然后我們呼叫我們的 main 函式，getLinkedIds使用鏈接和這些元素的 id。然后我們過濾專案以找到我們選擇的 id 的專案。

getLinkedIds查找包含我們的任何 id 作為父或子的所有鏈接，并將父和子添加到將包含的 id 串列中，完成后，過濾掉我們串列中已經存在的任何鏈接。如果這個要添加的 id 串列為空，我們就完成并回傳我們當前的串列。否則，我們會重復這兩個串列的組合。雖然這里可能存在一些效率低下的問題，但我認為這些串列必須非常大才能使它們變得重要。

I haven't tried to read your code and understand how it differs from this, but if my guess is correct about your requirements, this is relatively simple.

Old Version

This is not my usual coding style, and it bothers me. I tend to work with direct recursion, and I usually use immutable data structures. I would love to see an approach that handles this using that style, but I didn't come up with one right away.

Update: The comment above applied to this older version of the code. The newer version seems fine to me.

Here is a description of the original implementation of getLinkedIds (the other function has only cosmetic changes):

getLinkedIds保留兩個 id 串列：那些仍然要處理的和我們已經處理的，重復從第一個串列中洗掉一個 id ，將其添加到第二個串列中，然后將所有未處理的 s 排隊parentId，我們有一個childId指向當前值的鏈接然后是childId我們擁有parentId指向當前值的鏈接的所有未處理的 s。當toProcess佇列為空時，我們回傳processed一個。

您可以展開此代碼段以查看該版本（我不推薦：

顯示代碼片段

const getLinkedIds = (links, ids) => {
  const toProcess = [...ids], processed = []
  while (toProcess .length > 0) {
     const id = toProcess .pop ()
     processed .push (id)
     links .filter (({parentId}) => id == parentId) 
       .forEach (({childId}) => {
         if (! processed .includes (childId) && ! toProcess .includes (childId)) {
           toProcess .push (childId)
         }
       })
     links .filter (({childId}) => id == childId) 
       .forEach (({parentId}) => {
         if (! processed .includes (parentId) && ! toProcess .includes (parentId)) {
           toProcess .push (parentId)
         }
       })
  }
  return [...processed] 
}

const linkedItems = (defs, items, links) => {
  const rootTypes = defs .filter (({isRootWorkItem = false}) => isRootWorkItem) 
    .map (({workItemType}) => workItemType)
  const roots = items .filter (({type}) => rootTypes .includes (type))
  const ids = getLinkedIds (links, roots.flatMap (({id}) => id))
  return items .filter (({id}) => ids .includes (id))
}


const definitions = [ /* linkTypes deleted */  {workItemType: "car", isRootWorkItem: true}]
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"}]
const workItemLinks = [ /* linkTypes deleted */ {parentId: 1, childId: 3}, {parentId: 1, childId: 4}, {parentId: 3, childId: 7}, {parentId: 3, childId: 8}, {parentId: 10, childId: 1}, {parentId: 1, childId: 2}]

console .log (
  linkedItems (definitions, workItems, workItemLinks)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

uj5u.com熱心網友回復：

我試圖修改提到的“第一種實作方法”檔案并得到預期的結果。

這段代碼遠非完美，請隨時改進它，但我希望它現在可以閱讀......而且我沒有檢查這是否適用于所有場景

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 rootWorkItemIds = 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(rootWorkItemIds, rootWorkItemType, definitionsToTraverse, [], workItemIdsToLoad, workItemLinks);





function run(leftSideWorkItemIds, leftSideWorkItemType, definitionsToTraverse, traversedDefinitions, workItemIdsToLoad, workItemLinks) {
    // traverse parents and childs
    definitionsToTraverse
        .forEach(definition => {
            const { linkRole } = definition;
            const { parentWorkItemType, childWorkItemType } = linkRole;
            const leftSideIsChild = childWorkItemType === leftSideWorkItemType;
            const leftSideIsParent = parentWorkItemType === leftSideWorkItemType;

            // only if left side is child or parent and definition not blacklisted
            if ((leftSideIsChild || leftSideIsParent) && !definitionAlreadyTraversed(definition, traversedDefinitions)) {
                // blacklist the parent
                traversedDefinitions.push(definition);

                // process right side
                const relatedWorkItemLinks = getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideWorkItemIds, leftSideIsParent);

                // for the next iteration
                const rightSideWorkItemIds = [];

                relatedWorkItemLinks
                    // process the unknown link
                    .forEach(workItemLink => {
                        // add link if not known yet                    
                        if (!workItemLinkAlreadyAdded(workItemLink, workItemLinks)) {
                            workItemLinks.push(workItemLink);
                        }

                        const rightSideWorkItemId = leftSideIsParent ? workItemLink.childId : workItemLink.parentId;

                        rightSideWorkItemIds.push(rightSideWorkItemId);

                        // add the new id if not known yet
                        if (!workItemIdAlreadyAdded(rightSideWorkItemId, workItemIdsToLoad)) {
                            workItemIdsToLoad.push(rightSideWorkItemId);
                        }
                    });

                const rightSideWorkItemType = leftSideIsParent ? childWorkItemType : parentWorkItemType;

                // run again for the parent
                run(rightSideWorkItemIds, rightSideWorkItemType, definitionsToTraverse, traversedDefinitions, workItemIdsToLoad, workItemLinks);   
            }
        });
}

function definitionAlreadyTraversed(defintion, traversedDefinitions) {
    return traversedDefinitions.some(traversedDefintion => 
            traversedDefintion.linkRole.parentWorkItemType === defintion.linkRole.parentWorkItemType &&
            traversedDefintion.linkRole.childWorkItemType === defintion.linkRole.childWorkItemType &&
            traversedDefintion.linkRole.name === defintion.linkRole.name
        );
}

function workItemLinkAlreadyAdded(workItemLink, workItemLinks) {
    return workItemLinks.some(currentWorkItemLink => 
            currentWorkItemLink.linkRole.parentWorkItemType === workItemLink.linkRole.parentWorkItemType &&
            currentWorkItemLink.linkRole.childWorkItemType === workItemLink.linkRole.childWorkItemType &&
            currentWorkItemLink.linkRole.name === workItemLink.linkRole.name &&
            currentWorkItemLink.parentId === workItemLink.parentId &&
            currentWorkItemLink.childId === workItemLink.childId
        );
}

function workItemIdAlreadyAdded(workItemId, workItemIds) {
    return workItemIds.some(currentWorkItemId => currentWorkItemId === workItemId)
}







const missingWorkItemIdsToLoad = workItemIdsToLoad.filter(workItemIdToLoad => !rootWorkItemIds.some(workItemId => workItemId === workItemIdToLoad)); // filter out all the existing 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))

作業樣本

顯示代碼片段

/* 

BACKEND GOES HERE

*/

// duplicate name ...
const backendEndWorkItems = [{
    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",
}];

// duplicate name ...
const backendWorkItemLinks = [{
    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
}];

/* 

API GOES HERE

*/

function getWorkItemsByType(workItemType) {
    // take care for the name
    return backendEndWorkItems.filter(workItem => workItem.type === workItemType);
}

function getWorkItemsByIds(workItemIds) {
    // take care for the name
    return backendEndWorkItems.filter(workItem => workItemIds.some(workItemId => workItemId === workItem.id));
}

function getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideIds, leftSideIsParentSide) {
    // take care for the name
    return backendWorkItemLinks.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;
    });
}

/* 

CONFIGURATION GOES HERE

*/

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",
        }
    },
];

/* 

IMPLEMENTATION GOES HERE

*/

// 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 rootWorkItemIds = 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(rootWorkItemIds, rootWorkItemType, definitionsToTraverse, [], workItemIdsToLoad, workItemLinks);





function run(leftSideWorkItemIds, leftSideWorkItemType, definitionsToTraverse, traversedDefinitions, workItemIdsToLoad, workItemLinks) {
    // traverse parents and childs
    definitionsToTraverse
        .forEach(definition => {
            const { linkRole } = definition;
            const { parentWorkItemType, childWorkItemType } = linkRole;
            const leftSideIsChild = childWorkItemType === leftSideWorkItemType;
            const leftSideIsParent = parentWorkItemType === leftSideWorkItemType;

            // only if left side is child or parent and definition not blacklisted
            if ((leftSideIsChild || leftSideIsParent) && !definitionAlreadyTraversed(definition, traversedDefinitions)) {
                // blacklist the parent
                traversedDefinitions.push(definition);

                // process right side
                const relatedWorkItemLinks = getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideWorkItemIds, leftSideIsParent);

                // for the next iteration
                const rightSideWorkItemIds = [];

                relatedWorkItemLinks
                    // process the unknown link
                    .forEach(workItemLink => {
                        // add link if not known yet                    
                        if (!workItemLinkAlreadyAdded(workItemLink, workItemLinks)) {
                            workItemLinks.push(workItemLink);
                        }

                        const rightSideWorkItemId = leftSideIsParent ? workItemLink.childId : workItemLink.parentId;

                        rightSideWorkItemIds.push(rightSideWorkItemId);

                        // add the new id if not known yet
                        if (!workItemIdAlreadyAdded(rightSideWorkItemId, workItemIdsToLoad)) {
                            workItemIdsToLoad.push(rightSideWorkItemId);
                        }
                    });

                const rightSideWorkItemType = leftSideIsParent ? childWorkItemType : parentWorkItemType;

                // run again for the parent
                run(rightSideWorkItemIds, rightSideWorkItemType, definitionsToTraverse, traversedDefinitions, workItemIdsToLoad, workItemLinks);   
            }
        });
}

function definitionAlreadyTraversed(defintion, traversedDefinitions) {
    return traversedDefinitions.some(traversedDefintion => 
            traversedDefintion.linkRole.parentWorkItemType === defintion.linkRole.parentWorkItemType &&
            traversedDefintion.linkRole.childWorkItemType === defintion.linkRole.childWorkItemType &&
            traversedDefintion.linkRole.name === defintion.linkRole.name
        );
}

function workItemLinkAlreadyAdded(workItemLink, workItemLinks) {
    return workItemLinks.some(currentWorkItemLink => 
            currentWorkItemLink.linkRole.parentWorkItemType === workItemLink.linkRole.parentWorkItemType &&
            currentWorkItemLink.linkRole.childWorkItemType === workItemLink.linkRole.childWorkItemType &&
            currentWorkItemLink.linkRole.name === workItemLink.linkRole.name &&
            currentWorkItemLink.parentId === workItemLink.parentId &&
            currentWorkItemLink.childId === workItemLink.childId
        );
}

function workItemIdAlreadyAdded(workItemId, workItemIds) {
    return workItemIds.some(currentWorkItemId => currentWorkItemId === workItemId)
}







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

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

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







console.log({
    workItems,
    workItemLinks
})

uj5u.com熱心網友回復：

一般注意事項

建議將大部分作業推送到服務器上，因為可能workItems會workItemLinks包含大量記錄。如果遍歷樹的作業workItems留給客戶端進行單獨的 API 呼叫，那么網路延遲就會發揮作用......

資料結構

建議將資料標準化如下：

WorkItems - 沒有變化。
WorkItemLinks - 將屬性簡化為parentId和childId，它本質上是具有 WorkItems 物體的多對多物體。
定義 - 展平為parentWorkItemType、childWorkItemType和name。根條目通過設定parentWorkItemType為 null 來處理。

還要注意，實際上，Definitions在遍歷時可能不需要 for WorkItemLinks，因為在創建時，大概只有在type 和type 之間的關系符合.WorkItemLinks時才允許創建. 如果確實是這種情況，那么建議的代碼可能會進一步簡化......parentIdchildIdDefintions

提議的 API

以下解決方案提出了兩 (2) 個 API：

getDefinitionChain( rootWorkItemType ) - 給定一個 rootWorkItemType（例如，“car”），此 API 遍歷物體的子物體和父Definition物體，并回傳所有相關的workItemTypes.
getWorkItemChain( rootWorkItemType ) - 最初呼叫 getDefinitionChain 來識別相關的workItemTypes，然后workItems從 rootWorkItemType 開始遍歷。

同樣，這些 API 是服務器端的概念，減少了客戶端和服務器之間的閑聊......

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"}];

const workItemLinks = [
  {
    "parentId": 1,
    "childId": 3
  },
  {
    "parentId": 1,
    "childId": 4
  },
  {
    "parentId": 3,
    "childId": 7
  },
  {
    "parentId": 3,
    "childId": 8
  },
  {
    "parentId": 10,
    "childId": 1
  },
  {
    "parentId": 1,
    "childId": 2
  }
];

const definitions = [
  {
    "parentWorkItemType": "car",
    "childWorkItemType": "bird",
    "name": "isChildOf"
  },
  {
    "parentWorkItemType": null,
    "childWorkItemType": "car",
    "name": "root"
  },
  {
    "parentWorkItemType": "bird",
    "childWorkItemType": "house",
    "name": "with"
  },
  {
    "parentWorkItemType": "person",
    "childWorkItemType": "car",
    "name": "owns"
  },
  {
    "parentWorkItemType": "car",
    "childWorkItemType": "car",
    "name": "references"
  }
];


function getDefinitionChain( rootWorkItemType ) {
  
  let alreadyVisitedType = new Set();
  let definitionChain = [];

  function recurse( workItemType ) {

    // Visit the children types...
    let nodeTypeChildList = definitions.filter( def => def.parentWorkItemType === workItemType );
    
    for ( let childType of nodeTypeChildList ) {
      if ( !alreadyVisitedType.has( childType.childWorkItemType ) ) {
        alreadyVisitedType.add( childType.childWorkItemType );
        definitionChain.push( childType.childWorkItemType );
        recurse( childType.childWorkItemType );
      }
    }
    
    // Visit the parent types...
    let nodeTypeParentList = definitions.filter( def => def.childWorkItemType === workItemType );
    
    for ( let parentType of nodeTypeParentList ) {
      // Don't go up the definition chain if parent is null.
      if ( parentType.parentWorkItemType && !alreadyVisitedType.has( parentType.parentWorkItemType ) ) {
        alreadyVisitedType.add( parentType.parentWorkItemType );
        definitionChain.push( parentType.parentWorkItemType );
        recurse( parentType.parentWorkItemType );
      }
    }

  }
  
  recurse( rootWorkItemType )
  if ( !alreadyVisitedType.has( rootWorkItemType ) ) {
    definitionChain.push( rootWorkItemType );
  }
  
  return definitionChain;
  
}


function getWorkItemChain( rootWorkItemType ) {

  // Get the list of allowable definitions...
  let allowableDefinitions = new Set( getDefinitionChain( rootWorkItemType ) );
  
  // Now, traverse the WorkItems tree, ensuring that they are in the WorkItemType list...
  let wim = new Map();
  
  function recurse( workItemCandidates ) {
    
    for ( let workItem of workItemCandidates ) {
      // Is this a workItemType that conforms to our allowable definitions?
      if ( allowableDefinitions.has( workItem.type ) ) {
        // If never having traversed this WorkItem, then let's traverse the children and parents.
        if ( !wim.has( workItem.id ) ) {
          wim.set( workItem.id, workItem );
         
          // Get the list of WorkItems that are children to the workItem.id.
          recurse( workItemLinks.filter( wix => wix.parentId === workItem.id ).map( wil => workItems.find( wif => wif.id === wil.childId )) );
          
          // Get the list of WorkItems that are parents to the workItem.id.
          recurse( workItemLinks.filter( wix => wix.childId === workItem.id ).map( wil => workItems.find( wif => wif.id === wil.parentId )) );
        }
      }
    }
  
  }
  
  // Start with all the workItems that are of type rootWorkItemType.
  recurse( workItems.filter( wi => wi.type === rootWorkItemType ) );
  
  return [...wim.values()];

}

console.log( 'WorkItem Types in Definitions with a root of "car".' );
let definitionChain = getDefinitionChain( 'car' );
console.log( definitionChain );

console.log( 'WorkItems with a root of "car"' );
let workItemChain = getWorkItemChain( 'car' );
console.log( workItemChain );

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424343.html

標籤：javascript node.js algorithm recursion

上一篇：如何在Haskell中根據某些條件拆分串列？

下一篇：檢查非數字值是否在范圍內的最佳方法是什么？