Как найти элемент в графе?

Question

У меня есть следующие объекты:

1. Форма
2. Блок
3. Строка
4. Ячейка
5. Поле

Root элемент Form.

Внутри From помещен Block.

Block содержит немного Rows и каждый Row может содержать несколько Cell с различным содержанием внутри: Field или Block, где Block это снова вложенная структура Block -> Rows -> Cells -> Field/Block.

Это ориентированный конечный граф из root Form и fini sh vertex Field или Block.

Только Block и Field сущностей имеют метод getId(), который возвращает идентификатор вершины. Исходя из этого, я строю путь от root к конкретной вершине (Blcok, Field).

Я пытался проверить, представлена ​​ли конкретная вершина объекта (Block) в графе по пути, поэтому мое решение:

1. Установить текущую вершину (Блок), с которой мы начинаем, установить путь дохода вершин
2. Получить в l oop все строки текущей вершины (Блок)
3. Затем внутри сначала l oop получить все ячейки из каждой строки, используя l oop
4. Затем получить содержимое из каждой ячейки (поле, блок)
5. Проверить, является ли он блоком, затем получить id и сравнить с входящим путем (id)
6. Если он не равен, тогда установить найденный блок как текущий (для l oop)
7. Продолжается, пока я не могу найти путь

Код:

function getBlockFieldByPath(block: Block, path: string) {
   let currentBlock = block;
   let irows = 0;
   let jcells = 0;

   while(irows < currentblock.getRows().length) {
       let cells = rows[irows].getCells();
       while(jcells < cells.length) {
           let content = cells[jcells].getContent(); // it is should be Block or Field,

           if (content.getId() == path) {
               return content;
           }

           if (content == Block) {
              currentblock = content; // Because content is Block
           }

          jcells++;
       }
     irows++;
   }   

}

Где моя ошибка?

Answer 1

Немного абстрагируясь, у вас есть график, в котором узлы являются блоками.

Некоторые из них тривиальны.

Вы просто хотите использовать свой граф, пока не найдете блок которая соответствует вашей строке пути

function dfs(block, path) {
  if (block.getId() === path) return block
  let found = null
  block.getRows().find(r => r.getCells().find(bContent => {
    let b = bContent.getContent()
    found = dfs(b, path)
    return found
  }))
  return found
}

---

Вариант со стеком

function dfs(block, path) {
  const stack = [block]
  while (stack.length) {
    const b = stack.pop()
    if (b.getId() === path) return block
    b.getRows().forEach(r => r.getCells().forEach(bContent => {
      let b = bContent.getContent()
      stack.push(b)
    })
  }
  return null
}