算法挑战。从树状结构生成新的结构

Question

下面是我当前的代码并且可以运行。然而这个

console.log(JSON.stringify(results2) == JSON.stringify(payloadTasks))

失败了。我需要通过这个通行证

const payloadTasks = [
    {
        name: "a",
        parallel: {
            tasks: [
                {name: "a1", parallel: {tasks: [{name: "a1a"}]}},
                {name: "a2"}
            ]
        }
    },
    {name: "b"},
    {
        name: "c",
        parallel: {
            tasks: [{name: "c1"}]
        }
    }
]
 
const edges = [
    {source: "a", target: "a1"},
    {source: "a", target: "a2"},
    {source: "a1", target: "a1a"},
    {source: "a1a", target: "b"},
    {source: "a2", target: "b"},
    {source: "b", target: "c"},
    {source: "c", target: "c1"}
]
 
const nodes = [
    {name: "a", data: {type: "parallelNode", isRoot: true}},
    {name: "b", data: {isRoot: true}},
    {name: "c", data: {type: "parallelNode", isRoot: true}},
    {name: "a1", data: {type: "parallelNode"}},
    {name: "a1a", type: ""},
    {name: "a2"},
    {name: "c1"}
]
const nodesWithoutIsRoot = [
    {name: "a", data: {type: "parallelNode"}},
    {name: "b", data: {}},
    {name: "c", data: {type: "parallelNode"}},
    {name: "a1", data: {type: "parallelNode"}},
    {name: "a1a", type: ""},
    {name: "a2"},
    {name: "c1"}
]
 
 
function convertToPayloadTasks(nodes, edges) {
    const taskMap = nodes.reduce((acc, node) => {
        acc[node.name] = {
            name: node.name,
            ...(node.data?.type === 'parallelNode' && {parallel: {tasks: []}}),
        };
        return acc;
    }, {});
 
    edges.forEach(edge => {
        const parentTask = taskMap[edge.source];
        const childTask = taskMap[edge.target];
 
        if (parentTask.parallel) {
            parentTask.parallel.tasks.push(childTask);
        } else {
            console.error(`Attempting to add child to non-parallel parent: ${parentTask.name}`);
        }
    });
 
    // Extract root tasks based on the isRoot flag
    const rootTasks = nodes.filter(node => node.data?.isRoot).map(node => taskMap[node.name]);
 
    // Optionally, if a non-root task is not a child in any edge, it could also be considered a root task
    // This depends on your specific requirements and how you define a root task in the absence of an isRoot flag
    const additionalRootTasks = Object.values(taskMap).filter(task =>
        !rootTasks.includes(task) && !edges.some(edge => edge.target === task.name)
    );
 
    return [...rootTasks, ...additionalRootTasks];
}
 
 
const results = convertToPayloadTasks(nodes, edges);
const results2 = convertToPayloadTasks(nodesWithoutIsRoot, edges);
console.log(JSON.stringify(results) == JSON.stringify(payloadTasks))
console.log(JSON.stringify(results2) == JSON.stringify(payloadTasks))

我需要让这个通过成为现实。但我无法这样做。它目前适用于字段

isRoot

，但一旦我删除它，它就不起作用了。 我想知道是否可以生成与 PayloadTasks 相同的结构，但删除该字段

isRoot

感谢您的帮助。

Answer 1

您可以为所有相互引用使用一个辅助对象。

顺便说一句，您的数据包含一些边缘

{ source: "a1a", target: "b" },
{ source: "a2", target: "b" },
{ source: "b", target: "c" }

这没有反映想要的结果。

const
    edges = [{ source: "a", target: "a1" }, { source: "a", target: "a2" }, { source: "a1", target: "a1a" }, /* { source: "a1a", target: "b" }, { source: "a2", target: "b" }, { source: "b", target: "c" }, */ { source: "c", target: "c1" }],
    nodes = [{ name: "a", data: { type: "parallelNode", isRoot: true } }, { name: "b", data: { isRoot: true } }, { name: "c", data: { type: "parallelNode", isRoot: true } }, { name: "a1", data: { type: "parallelNode" } }, { name: "a1a", type: "" }, { name: "a2" }, { name: "c1" }],
    parents = Object.fromEntries(edges.map(({ source, target }) => [target, source])),
    tree = function (edges, parents, root) {
        const t = {};
        nodes.forEach(({ name }) => {
            const parent = parents[name];
            Object.assign(t[name] = t[name] || {}, { name });
            t[parent] ??= { name: undefined };
            t[parent].parallel ??= {};
            t[parent].parallel.tasks ??= [];
            t[parent].parallel.tasks.push(t[name]);
        });
        return t[root].parallel.tasks;
    }(edges, parents, undefined);

console.log(tree);

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