使用 DAG 对象将一维数组转换为二维数组

Question

我们正在构建一个应用程序，客户可以在其中构建工作流，表示为 DAG。当在屏幕上输出时，它将如下所示：

上面的图是用二维数组输出到屏幕上的，模型长这样：

const dag = [
  [
    { id: 1, parentId: 0 }
  ],
  [
    { id: 2, parentId: 1 },
    { id: 3, parentId: 1 }
  ],
  [
    { id: 6, parentId: 2 },
    { id: 4, parentId: 3 },
    { id: 5, parentId: 3 }
  ],
]

二维数组模型允许我对其进行循环并在屏幕上输出每一行；所以 dag 模型中的第一项是具有一个节点的第一行，dag 模型中的第二项是具有两个节点的第二行，依此类推。

那部分有效，我什至想出了如何动态地将节点动态添加到图形中。我运行遇到问题的部分是从一维数组创建二维数组。图形的数据将发送到服务器并作为一维数组从服务器返回，如下所示：

const items = [
  { id: 1, parentId: 0 },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 1 },
  { id: 4, parentId: 3 },
  { id: 5, parentId: 3 },
  { id: 6, parentId: 2 },
]

我需要把这个items数组转换成上面的dag多维数组

这是我目前的情况：

// this is the end array, (two dimensions [][]), that will be used to draw the graph
const dag = [];

// this will create the first row of the array, with all the items that have a parentId of 0
const newRow = items
  .filter((item) => item.parentId === 0)
  .reduce((arr, item) => {
    arr.push(item);
    return arr;
  }, []);
dag.push(newRow);

// Now I'm trying to move down the graph from top to bottom
dag.forEach((row) => {
  // get the list of item IDs that are in this row
  const itemIdsInRow = row.reduce((prev, row) => {
    prev.push(row.id);
    return prev;
  }, []);

  // use the itemIdsInRow to get the items from the single dimensional array that will go in the next row
  const itemsForNextRow = itemIdsInRow.reduce((itemsArr, id) => {
    const nextItems = items.filter((item) => item.parentId === id);
    itemsArr.push(...nextItems);
    return itemsArr;
  }, []);

  // push the new row onto the two dimension array
  dag.push(itemsForNextRow);
});

这适用于 dag 的前两行。这说得通;当我推进到 dag 模型时，forEach 不允许我继续通过循环构建第三行。如果我在前两行的 forEach 之前启动 dag 数组，我可以正确构建第三行，因此构建 dag 的算法非常接近那里。

如果您对如何解决此问题有任何意见或想法，我将不胜感激。谢谢！

编辑

我们现在还需要每个项目的 parentId 是一个 parentId 的数组。这是因为两个分支可以在一个点上组合回去，所以一个节点可能有两个（或更多）父节点。假设在上图中，节点 4 和 5 在它们下方有一个子节点，它们每个都连接到该子节点。这是代码中的起始数组和结果数组：

const start = [
  { isYesPath: undefined, name: 'Step 1', parentIds: [0], stepId: 1, type: DagBranchType.Normal },
  { isYesPath: undefined, name: 'Step 2', parentIds: [1], stepId: 2, type: DagBranchType.IfElse },
  { isYesPath: true, name: 'Step 3', parentIds: [2], stepId: 3, type: DagBranchType.Normal },
  { isYesPath: false, name: 'Step 4', parentIds: [2], stepId: 4, type: DagBranchType.Normal },
  { isYesPath: undefined, name: 'Step 5', parentIds: [3, 4], stepId: 5, type: DagBranchType.Normal },
]

const result = [
  [{ isYesPath: undefined, name: 'Step 1', parentIds: [0], stepId: 1, type: DagBranchType.Normal }],
  [{ isYesPath: undefined, name: 'Step 2', parentIds: [1], stepId: 2, type: DagBranchType.IfElse }],
  [
    { isYesPath: true, name: 'Step 3', parentIds: [2], stepId: 3, type: DagBranchType.Normal },
    { isYesPath: false, name: 'Step 4', parentIds: [2], stepId: 4, type: DagBranchType.Normal }
  ],
  [{ isYesPath: undefined, name: 'Step 5', parentIds: [3, 4], stepId: 5, type: DagBranchType.Normal }]
]

Answer 1

一种可能的解决方案如下。我不确定这是最好的方法，还是最有效的方法，但它确实有效。基本上，我跟踪使用了 items 数组中的哪些对象，以及何时将它们推送到 usedItems 数组。我遍历将新行添加到 dag 模型的代码，同时 usedItems.length !== items.length.

const items = [
  { id: 1, parentId: 0 },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 1 },
  { id: 4, parentId: 3 },
  { id: 5, parentId: 3 },
  { id: 6, parentId: 2 },
];
// As items are used, push them on this array
const usedItems = [];

// this is the end array, (two dimensions [][]), that will be used to draw the graph
const dag = [];

// this will create the first row of the array, with all the items that have a parentId of 0
const newRow = items
  .filter((item) => item.parentId === 0)
  .reduce((arr, item) => {
    arr.push(item);
    return arr;
  }, []);
dag.push(newRow);
usedItems.push(...newRow);

// go until the usedItems array is the same length as the original items array
while (usedItems.length !== items.length) {
  // get the list of item IDs that are in this row
  const row = dag[dag.length - 1];
  const itemIdsInRow = row.reduce((prev, row) => {
    prev.push(row.id);
    return prev;
  }, []);

  // use the itemIdsInRow to get the items from the single dimensional array that will go in the next row
  const itemsForNextRow = itemIdsInRow.reduce((itemsArr, id) => {
    const nextItems = items.filter((item) => item.parentId === id);
    itemsArr.push(...nextItems);
    return itemsArr;
  }, []);

  // push the new row onto the two dimension array
  dag.push(itemsForNextRow);
  usedItems.push(...itemsForNextRow);
}

Answer 2

您可以通过使用 forEach 和 filter 方法创建一个递归函数并传递父 ID 和当前级别来获得所需的结果。然后，您可以使用级别按索引添加到结果数组。

const items = [{"id":1,"parentId":0},{"id":2,"parentId":1},{"id":3,"parentId":1},{"id":4,"parentId":3},{"id":5,"parentId":3},{"id":6,"parentId":2}]

const result = []

const modify = (data, pid = 0, level = 0) => data
  .filter(({ parentId }) => parentId === pid)
  .forEach(e => {
    if (!result[level]) result[level] = [e]
    else result[level].push(e);

    modify(data, e.id, level + 1)
  })


modify(items)

console.log(result);

Answer 3

但是已经有几个解决方案，我想推荐一个没有突变的解决方案。

const items = [
  { id: 1, parentId: 0 },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 1 },
  { id: 4, parentId: 3 },
  { id: 5, parentId: 3 },
  { id: 6, parentId: 2 },
];

const partition = predicate => list => [
  list.filter (predicate),
  list.filter (x => !predicate (x)),
];

const inLevel = nth => original => item => {
  if (nth < 0) return false;
  const parent = original.find (({id}) => id === item.parentId);
  return !parent ? nth === 0 : inLevel (nth - 1) (original) (parent);
};

const buildTree = (original) => (list, nth = 0) => {
  const [currentLevel, rest] = partition (inLevel (nth) (original)) (list);
  return rest.length > 0
    ? [ currentLevel, ...buildTree (original) (rest, nth + 1) ]
    : [ currentLevel ];
}

console.log (buildTree (items) (items));

使用 DAG 对象将一维数组转换为二维数组

Convert a Single Dimension Array to Two Dimensional Array with DAG Objects

javascript

arrays

directed-acyclic-graphs

编辑