Реализация направленного ациклического иерархического графа

Question

Мне нужно отобразить ациклический ориентированный граф, который выглядит примерно так:

Я создал вложенную иерархическую структуру данных, похожую на эту:

[
 {
  node: 'abs'
  children: [
   {
    node: 'jhg',
    children: [{...}]
   {
    node: 'AAA',
    children: [{...}]
   },
 {
  node: 'fer'
  children: [
   {
    node: 'AAA',
    children: [{...}]
   {
    node: 'xcv',
    children: [{...}]
   },
 {
]

Я не уверен, является ли это лучшим способом для фактического отображения данных, поскольку узлы с несколькими родителями и их дочерними элементами появлялись бы несколько раз, но я пока не представлял, как с этим справиться.

Я просто хочу отобразить эти узлы в воображаемой сетке. Поэтому мне нужно проанализировать мою структуру данных и установить их значения сетки. Проблема в том, что я не знаю, как анализировать структуру данных с помощью логики иерархии.

То, что я сейчас делаю, явно вызывает проблемы для узлов с несколькими родителями:

for (const root of allRoots) {
  currentLevel = 0;
  if (root.node === 'VB8') {
    getChildrenTree(root);
  }
}

function getChildrenTree(node) {
  currentLevel++;
  node._gridX = currentLevel;

  if (node.children.length > 0) {
    for(const nextChild of children ) {
      getChildrenTree(nextChild);
    }
  }

Проблема с этим кодом заключается в том, что он будет проходить только по одному пути и затем остановится, когда нет дочерних элементов.

Мне просто нужен алгоритм, который проходит через дерево и устанавливает уровень иерархии каждого узла.

Я надеюсь, что это не слишком смущает.

Answer 1

Если вы хотите сослаться на один и тот же узел от двух разных родителей, вы не должны определять его более одного раза. Я предлагаю перечислить все узлы в плоском массиве с одним «невидимым» корневым узлом и ссылаться на потомков по идентификатору или индексу массива:

[
 {id: 0, name: "root", children: [1, 2]},
 {id: 1, name: "abs", children: [3, 4]},
 {id: 2, name: "fer", children: [5, 6]},
 {id: 3, name: "jhg", children: [...]},
 {id: 4, name: "AAA", children: [...]},
 ...
]

тогда вы можете рекурсивно установить их глубину дерева следующим образом:

function setDepth(node, depth) {
  if (node._gridX && node._gridX >= depth) {
    // node has been visited already through a path of greater or equal length
    // so tree depths wouldn't change
    return
  }
  node._gridX = depth
  node.children
    .map(idx => nodeArray[idx]) // get the actual objects from indices
    .forEach(child => setDepth(child, depth+1))
}
setDepth(nodeArray[0], 0) // start at root

... осторожно, поскольку этот алгоритм застревает в цикле, если у ваших узлов есть циклы