Трансформация stratify и treelinks

Vega и Vega-Lite используют систему трансформаций данных, в которой stratify и treelinks формируют основу построения и визуализации иерархий. Эти трансформации решают две взаимосвязанные задачи: преобразование плоских данных в древовидную структуру и последующее извлечение связей между узлами для рендеринга рёбер графа.

stratify предназначена для преобразования плоского списка объектов в иерархическую структуру на основе связей «родитель — потомок». Это ключевой шаг при построении деревьев, оргструктур, файловых систем и любых данных с явной иерархией.

Принцип работы

Каждая запись исходного массива должна содержать:

  • уникальный идентификатор узла (key)
  • ссылку на родителя (parentKey)

На основе этих полей строится дерево, где:

  • узлы без родителя становятся корнями
  • связи формируют уровни вложенности
  • создаётся вложенная структура children

Структура входных данных

[
  { "id": "A", "parent": null },
  { "id": "B", "parent": "A" },
  { "id": "C", "parent": "A" },
  { "id": "D", "parent": "B" }
]

Конфигурация трансформации

В Vega-спецификации:

{
  "type": "stratify",
  "key": "id",
  "parentKey": "parent"
}

Результат преобразования

После выполнения формируется дерево:

  • A

    • B

      • D

    • C

Внутри структуры каждый узел получает:

  • массив children
  • ссылку на родителя
  • вычисленную глубину (в зависимости от последующих трансформаций)

Особенности поведения

Несколько корневых узлов

Если несколько записей имеют parent: null, формируется лес (forest), то есть набор деревьев.

Отсутствие родителя

Если parentKey указывает на несуществующий узел, поведение зависит от конфигурации пайплайна: узел может быть отброшен или интерпретирован как корневой.

Циклы

Циклические зависимости (A → B → A) приводят к некорректной иерархии и обычно ломают построение дерева, так как структура должна быть ацикличной.

Использование stratify в Vega

В Vega трансформация включается в блок transform:

{
  "data": {
    "values": [
      { "id": "root", "parent": null },
      { "id": "n1", "parent": "root" },
      { "id": "n2", "parent": "root" }
    ]
  },
  "transform": [
    {
      "type": "stratify",
      "key": "id",
      "parentKey": "parent"
    }
  ]
}

После выполнения становится доступна иерархическая структура, которую можно передавать в layout-трансформации (tree, cluster) или использовать для вычисления связей.

Иерархические данные и последующая обработка

После stratify данные обычно проходят через дополнительные трансформации:

  • tree — вычисление координат узлов
  • cluster — компактная компоновка дерева
  • partition — радиальная иерархия
  • treemap — прямоугольная упаковка

Однако сами эти трансформации не создают связи между узлами в виде рёбер. Для этого используется treelinks.

treelinks извлекает связи между узлами уже из иерархической структуры, создавая набор рёбер (links), пригодных для визуализации графов и деревьев.

Назначение

Основная функция:

  • преобразовать дерево в список связей source → target
  • подготовить данные для рендеринга линий между узлами
  • обеспечить совместимость с mark типа path или line

Входные данные

treelinks требует уже иерархическую структуру, например результат stratify.

Конфигурация

{
  "type": "treelinks"
}

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

На выходе формируется массив рёбер:

[
  { "source": {...}, "target": {...} },
  { "source": {...}, "target": {...} }
]

Где:

  • source — родительский узел
  • target — дочерний узел

Эти объекты содержат ссылки на оригинальные узлы дерева.

treelinks применяется для построения:

  • деревьев с линиями (node-link diagrams)
  • edge bundling графов
  • зависимостей
  • оргструктур

Типичный сценарий — параллельное использование двух потоков данных:

  • узлы (nodes)
  • рёбра (links через treelinks)

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

{
  "transform": [
    {
      "type": "stratify",
      "key": "id",
      "parentKey": "parent"
    },
    {
      "type": "tree",
      "method": "tidy",
      "size": [800, 400]
    },
    {
      "type": "treelinks"
    }
  ]
}

Логика пайплайна

  1. stratify формирует дерево
  2. tree вычисляет координаты узлов
  3. treelinks создаёт связи для рёбер

Пример полной спецификации

{
  "data": {
    "values": [
      { "id": "A", "parent": null },
      { "id": "B", "parent": "A" },
      { "id": "C", "parent": "A" },
      { "id": "D", "parent": "B" }
    ]
  },
  "transform": [
    {
      "type": "stratify",
      "key": "id",
      "parentKey": "parent"
    },
    {
      "type": "tree",
      "method": "tidy",
      "size": [600, 300]
    }
  ],
  "marks": [
    {
      "type": "link",
      "from": { "data": "tree" },
      "transform": [
        {
          "type": "treelinks"
        }
      ]
    }
  ]
}

1. Разделение ответственности

  • stratify отвечает за структуру
  • treelinks отвечает за связи

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

2. Ссылочная модель

treelinks не копирует данные узлов, а создаёт ссылки на существующие объекты. Это снижает накладные расходы при больших графах.

3. Зависимость от иерархии

Если вход не является деревом (например, отсутствует stratify), treelinks не может корректно построить связи.

Типичные ошибки и ограничения

Некорректные ключи

Если key не уникален, дерево формируется некорректно, возможны потери узлов.

Несогласованность parentKey

Ссылки на несуществующие parent приводят к «висячим» узлам.

Большие графы

При тысячах узлов:

  • stratify становится затратным по памяти
  • treelinks создаёт большое число рёбер, влияя на рендеринг

Поведение в сложных структурах

Лес (forest)

Несколько независимых корней приводят к множеству деревьев. treelinks в этом случае создаёт рёбра внутри каждого дерева отдельно.

Глубокие иерархии

Чем больше глубина:

  • тем больше вложенность в children
  • тем больше длина цепочек source → target

Связь с layout-трансформациями

stratify и treelinks часто используются вместе с:

  • tree (ортогональная компоновка)
  • cluster (иерархическая группировка)
  • radialTree (радиальная компоновка)

Layout определяет координаты, а treelinks использует их для построения линий.

Оглавление