使用 javascript / 节点对相互依赖的对象（内联过程）进行排序

Question

我为此苦思良久，希望能在这里得到一些支持。我有一个包含多个对象的数组。

每个对象都代表一个由输入和输出组成的子过程组成的生产过程。这些过程运行一致。意思是，一个过程的输出将成为另一个过程的输入。但是，我不知道顺序是什么。

我正在尝试找出主要进程需要运行的顺序。我们的系统无法告诉我，现在我有 5000 个相互依赖的进程需要排序。

这里是数组格式化的示例。如您所见，输入有一个原始标志。至少我们知道输入是从仓库中取出还是在上游某处生产。如果我手动对此进行排序，顺序将是 Process3，然后是 Process 2，然后是 Process 1。Process 1 需要 material with the id="ID3" 作为输入，它是在 process 2 中生成的（在 subprocess 2 下).虽然流程 2 需要流程 3 中生成的 material“ID5”。有人知道如何解决这个噩梦吗？

非常感谢！！！

[
  {
    processID: "1",
    subprocesses: [
      {
        subprocessID: "1",
        outputs: [
          {
            id: "ID1",
            name: "alpha",
            ratio: "1",
          },
        ],
        inputs: [
          {
            type: "rawMaterial",
            id: "ID2",
            ratio: "0.7623",
          },
          {
            type: "processOutput",
            id: "ID3",
            ratio: "0.6552",
          },
        ],
      },
    ],
  },
  {
    processID: "2",
    subprocesses: [
      {
        subprocessID: "1",
        outputs: [
          {
            id: "ID22",
            name: "beta)",
            ratio: "1",
          },
        ],
        inputs: [
          {
            type: "processOutput",
            id: "ID5",
            ratio: "0.0034",
          },
        ],
      },
      {
        subprocessID: "2",
        outputs: [
          {
            id: "ID3",
            name: "gamma",
            ratio: "1",
          },
        ],
        inputs: [
          {
            type: "rawMaterial",
            id: "ID10",
            ratio: "0.0034",
          },
        ],
      },
    ],
  },
  {
    processID: "3",
    subprocesses: [
      {
        subprocessID: "1",
        outputs: [
          {
            id: "ID5",
            name: "omega",
            ratio: "1",
          },
        ],
        inputs: [
          {
            type: "rawMaterial",
            id: "ID111",
            ratio: "0.3018",
          },
        ],
      },
    ],
  },
]

Answer 1

正如我在评论中所说，你似乎遇到的是一个图论问题:-)

整个 thingamabob 是一个有向无环图——或者在这种情况下，基本上是一个依赖树。
每个子流程作为图中的一个节点。
边从输出资源的进程指向需要这些资源的进程。
图的拓扑顺序是流程需要完成的顺序。

此解决方案需要 toposort 包来进行繁重的图形提升。

const processes = require("./processes"); // Data from original post
const toposort = require("toposort");

const processInputs = {}; // Inputs required per subprocess
const outputIdToProcessIds = {}; // Map output IDs to processes that create them
const predecessorMap = {}; // Map process IDs to the node(s) that need to run immediately before

// Step 1: massaging the input data.

// Loop over top-level processes...
processes.forEach((proc) => {
  // and each subprocess within.
  proc.subprocesses.forEach((subproc) => {
    // Compute an unique ID for the process-subprocess.
    const procId = `${proc.processID}/${subproc.subprocessID}`;
    // Add it to our map of predecessors; this way each process, whether it's needed or not,
    // is in the predecessor map.
    // This also adds a "virtual" "start" predecessor for each node; it's not strictly necessary.
    predecessorMap[procId] = ["start"];

    // Gather the required inputs for each process.
    subproc.inputs.forEach((input) => {
      (processInputs[procId] = processInputs[procId] || []).push(input);
    });

    // Gather an inverse mapping of output ids to processes that create them.
    subproc.outputs.forEach((output) => {
      (outputIdToProcessIds[output.id] = outputIdToProcessIds[output.id] || []).push(procId);
    });
  });
});

// Step 2: massaging the processed data.

// Loop over the processes that actually do need inputs.
Object.entries(processInputs).forEach(([pid, inputs]) => {
  // For each input...
  inputs.forEach((input) => {
    // ... find the process IDs that can create these outputs.
    const pidsForInput = outputIdToProcessIds[input.id] ?? [];
    if (!pidsForInput.length) {
      console.warn(`There is no process that would output ${input.id} required by ${pid}`);
    } else {
      // Push the first one of them into the predecessors list for this process.
      // This might need special handling if it's possible for a resource to be output
      // by multiple processes.
      predecessorMap[pid].push(pidsForInput[0]);
    }
  });
});

// Step 3: creating graph data.
const allEdges = []; // All edges in from-to order
// Walk over the predecessor map...
Object.entries(predecessorMap).forEach(([to, froms]) => {
  // and each predecessor of each node, and push them into the full list of edges
  froms.forEach((from) => allEdges.push([from, to]));
});

console.log(allEdges);

// Step 4: sort!
// Run the toposort and print the order!
toposort(allEdges).forEach((node) => {
  console.log(node);
});

由于原始 post 中的数据不完整，程序会就此警告您，但不会完全失败。

当然，解决方案也不完整。

输出为：

There is no process that would output ID2 required by 1/1
There is no process that would output ID10 required by 2/2
There is no process that would output ID111 required by 3/1

接着是图的边

[
  [ 'start', '1/1' ],
  [ '2/2', '1/1' ],
  [ 'start', '2/1' ],
  [ '3/1', '2/1' ],
  [ 'start', '2/2' ],
  [ 'start', '3/1' ]
]

最后是所需的“执行顺序”（带有虚拟“开始”节点）：

start
2/2
1/1
3/1
2/1

所以，顺序是：

进程 2 子进程 2 完成
进程 1 子进程 1 完成
进程 3 子进程 1 完成
进程 2 子进程 1 完成

使用 javascript / 节点对相互依赖的对象（内联过程）进行排序

Sorting interdependant objects (in-line process) with javascript / node

arrays

sorting

nested

sequence