Деревья и графы

Деревья и графы относятся к базовым структурам данных, которые часто встречаются при моделировании и обработке иерархических и сетевых связей. В контексте JavaScript их представление требует аккуратного описания схемы данных, особенно когда структура может быть рекурсивной и заранее неизвестной по глубине. Библиотека Superstruct предоставляет декларативный способ описания таких структур и их валидации, включая сложные случаи с вложенностью и взаимными ссылками.

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

Типичная форма дерева в Jav * aScript:

const tree = {
  value: "root",
  children: [
    {
      value: "child1",
      children: []
    },
    {
      value: "child2",
      children: [
        {
          value: "child2.1",
          children: []
        }
      ]
    }
  ]
}

Граф обычно представляется либо списком смежности, либо списком рёбер:

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A"],
  D: ["B"]
}

или:

const edges = [
  ["A", "B"],
  ["A", "C"],
  ["B", "D"]
]

Основная сложность при работе с такими структурами заключается в том, что они часто являются рекурсивными или потенциально бесконечными, что требует от валидатора поддержки самоссылок.

Рекурсивные структуры в Superstruct

Ключевой механизм для описания деревьев и графов в Superstruct — функция lazy, позволяющая отложить вычисление схемы до момента выполнения.

Базовые элементы:

  • object — объект
  • array — массив
  • string, number — примитивы
  • lazy — рекурсивные определения

Описание дерева через Superstruct

Простейшая структура дерева:

import { object, array, string, lazy } from "superstruct"

const Tree = object({
  value: string(),
  children: array(lazy(() => Tree))
})

Здесь ключевой момент заключается в использовании lazy, без которого рекурсивная ссылка была бы невозможна.

Валидация дерева

import { create } from "superstruct"

const data = {
  value: "root",
  children: [
    { value: "leaf", children: [] }
  ]
}

create(data, Tree)

Если структура нарушена (например, children не массив или отсутствует value), Superstruct выдаст ошибку валидации.

Граф через список смежности

Граф часто удобнее описывать как словарь, где ключ — вершина, а значение — массив соседей.

import { record, array, string } from "superstruct"

const Graph = record(string(), array(string()))

Такая схема означает:

  • ключи объекта — строки (вершины)
  • значения — массив строк (соседние вершины)

Пример валидации графа

const graph = {
  A: ["B", "C"],
  B: ["A"],
  C: ["A"]
}

create(graph, Graph)

Граф через список рёбер

Альтернативное представление — массив пар:

import { tuple, array, string } from "superstruct"

const Edge = tuple([string(), string()])
const EdgeList = array(Edge)

Пример

const edges = [
  ["A", "B"],
  ["B", "C"],
  ["C", "A"]
]

create(edges, EdgeList)

Такой подход часто используется в алгоритмах поиска кратчайших путей и построения графов из внешних источников данных.

Направленные и ненаправленные графы

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

Ненаправленный граф обычно требует симметричных связей:

A -> B
B -> A

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

import { refine } from "superstruct"

const SymmetricGraph = refine(Graph, "SymmetricGraph", (value) => {
  for (const node in value) {
    for (const neighbor of value[node]) {
      if (!value[neighbor]?.includes(node)) {
        return false
      }
    }
  }
  return true
})

Ограничения Superstruct при работе с графами

Superstruct проверяет структурную корректность, но не выполняет:

  • поиск циклов
  • проверку связности
  • обнаружение дублей рёбер
  • анализ топологии графа

Эти задачи относятся к алгоритмическому уровню и должны решаться отдельно.

Деревья с дополнительными полями узлов

На практике узлы дерева часто содержат метаданные:

import { object, string, number, array, lazy, optional } from "superstruct"

const Node = object({
  id: string(),
  weight: number(),
  children: array(lazy(() => Node)),
  meta: optional(object({
    createdAt: string(),
    updatedAt: string()
  }))
})

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

const fileTree = {
  id: "root",
  weight: 0,
  children: [
    {
      id: "src",
      weight: 10,
      children: [
        {
          id: "index.js",
          weight: 2,
          children: []
        }
      ]
    }
  ]
}

Типизация графов через discriminated unions

Если граф содержит разные типы узлов, используется объединение структур:

import { union, object, string, array, lazy } from "superstruct"

const UserNode = object({
  type: string(),
  name: string(),
  friends: array(lazy(() => Node))
})

const GroupNode = object({
  type: string(),
  title: string(),
  members: array(lazy(() => Node))
})

const Node = union([UserNode, GroupNode])

Такой подход позволяет моделировать социальные графы с различными сущностями.

Представление больших графов

При работе с большими структурами часто используется нормализованная форма:

const NormalizedGraph = object({
  nodes: record(string(), object({
    id: string(),
    value: string()
  })),
  edges: array(object({
    from: string(),
    to: string()
  }))
})

Это позволяет отделить данные узлов от связей и упростить обработку.

Рекурсивные структуры и производительность

Использование lazy добавляет накладные расходы, поскольку каждое обращение к структуре требует разрешения функции. При глубокой вложенности это может влиять на производительность валидации.

В таких случаях применяются ограничения:

  • ограничение глубины дерева через refine
  • предварительная нормализация данных
  • разбиение графа на компоненты

Практический пример: файловая система

import { object, string, array, lazy } from "superstruct"

const FSNode = object({
  name: string(),
  type: string(),
  children: array(lazy(() => FSNode))
})

Пример структуры:

const fs = {
  name: "root",
  type: "dir",
  children: [
    {
      name: "home",
      type: "dir",
      children: [
        {
          name: "file.txt",
          type: "file",
          children: []
        }
      ]
    }
  ]
}

Практический пример: социальный граф

import { object, string, array, lazy } from "superstruct"

const Person = object({
  id: string(),
  name: string(),
  friends: array(lazy(() => Person))
})

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

Композиция структур для сложных графов

Superstruct позволяет комбинировать базовые примитивы в более сложные схемы:

import { object, record, array, string } from "superstruct"

const WeightedGraph = object({
  nodes: record(string(), object({
    label: string()
  })),
  edges: array(object({
    from: string(),
    to: string(),
    weight: string()
  }))
})

Такой подход используется в системах маршрутизации и анализе сетей.

Обобщённые паттерны описания графов

При проектировании схем часто выделяются три основных паттерна:

  • Иерархический (дерево) — строгая вложенность
  • Списочный (edge list) — явные связи
  • Словарный (adjacency map) — быстрый доступ к соседям

Superstruct позволяет описать каждый из них без привязки к конкретной предметной области, сохраняя единый подход к валидации.

Работа с частично неизвестными структурами

В реальных приложениях графы могут приходить неполными. Для этого используются:

  • optional
  • defaulted
  • union
import { optional, defaulted, string } from "superstruct"

const Node = object({
  id: string(),
  label: defaulted(string(), "unknown"),
  parent: optional(string())
})

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

Оглавление