有向无环图节点垂直排序优化：减少边交叉、拉近父子节点间距方案咨询

我在开发有向图节点排序功能时遇到布局优化问题，具体情况如下：
我已经实现了一套基于二维数组的节点排序算法：外层数组A的元素对应列坐标，内层数组B的元素位置对应行坐标，节点会根据其在A、B数组中的位置渲染到网格对应位置（例如节点在A数组下标为2的B数组中、且在该B数组下标为3的位置，则渲染到第2列第3行）。其中列坐标是通过迭代移除已识别根节点的方式确定的。
由于行排序为随机逻辑，渲染出的图整洁度较差。我们处理的图本身无环，结构类似树但支持一个子节点绑定多个父节点。
我和队友想要优化行排序逻辑，让图的布局尽可能整洁，尝试找过相关的开源库但未找到适配项，因此打算自行实现相关逻辑。
我们最初的思路是根据父节点的行坐标确定子节点的行坐标，但在父节点多子、子节点多父的复杂连接场景下，会出现很多难以处理的边界问题。
我们的代码输入为节点数组和边数组，已经可以根据节点的父节点归属和树层级完成列划分，现在仅需要优化垂直方向的排序，尽可能避免边交叉。

nodeData.test.js #

it('gets root node array and puts it in a grouped array, simpler test', () => {
    expect(
        getSortedNodes(
            // nodes:
            [{ id: 1 }, { id: 2 }, { id: 3 }],
            // edges:
            [
                { target: 3, source: 2 },
                { target: 3, source: 1 },
            ]
        )
    ).toStrictEqual([[{ id: 1 }, { id: 2 }], [{ id: 3 }]]) // resulting matrix
})

nodeData.js #

//调用时的参数说明：accumulated是空数组，rootIds需要传入根节点ID组成的数组（调用该函数前需要先从节点列表中提取根节点ID）
//edges是边数组，每个元素包含source（源节点ID）和target（目标节点ID）
//该函数是私有函数，仅应在getSortedNodes()内部调用
function sortNodes(accumulated, nodes, nodeIds, edges) {
    if (!nodeIds.length) {
        return accumulated
    }
    const targetList = edges.map(({ target }) => target)
    const rootIdLayer = difference(nodeIds, targetList, true)
    const rootNodes = nodes.filter(node => rootIdLayer.includes(node.id))
    const accumulatedList = [...accumulated]
    accumulatedList.push(rootNodes)
    const remainingNodeIds = difference(nodeIds, rootIdLayer, true)
    const remainingEdges = edges.filter(edge => !rootIdLayer.includes(edge.source))
    return sortNodes(accumulatedList, nodes, remainingNodeIds, remainingEdges)
}

// 参数为节点数组和边数组
// 返回排序后的节点数组，可直接用于网格定位
export function getSortedNodes(nodes, edges) {
    const nodeIds = nodes.map(({ id }) => id)
    return sortNodes([], nodes, nodeIds, edges)
}

我们不想要单元测试中展示的随机对齐矩阵，而是希望生成的矩阵中子节点距离父节点更近。以下是伪代码示例：3是2的子节点，4是3的子节点。

nodes: 

[1,2,3,4]

edges:

[
    {source: 2, target: 3},
    {source: 3, target: 4}
]

expected result:

[
    [1, 2],
    [null, 3],
    [null, 4]
]

当前渲染的混乱效果：

预期的父子节点邻近的渲染效果：

该场景在边交叉较多时复杂度会大幅提升。

更新 #

我们已经决定尝试使用Sugiyama方法，后续会同步实现结果，若调试成功也会输出对应的解决方案。
如果您有其他可行的方案建议或者适配的工具库推荐，欢迎留言解答，非常感谢！

内容的提问来源于stack exchange，提问作者RubbelDieKatz