От матрицы к списку

В прошлом уроке мы хранили граф в матрице V x V и тратили память пропорционально |V|^2 — даже когда рёбер было всего |V|. Это плохо для sparse-графов. Sparse — это норма в DE: dbt-проект из 800 моделей с 2400 ребрами имеет плотность 0.4%; lineage десятков тысяч таблиц — ещё разреженнее.

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (1,2), (2,3)}    (directed)

adj = {
    0: [1, 2],   # из 0 идут рёбра в 1 и 2
    1: [2],
    2: [3],
    3: [],
}

Размер этой структуры — V записей в dict + сумма длин всех списков, то есть |E| записей. В сумме O(V + E). Для нашего графа из 800 моделей с 2400 рёбрами это 3200 элементов — копейки. Сравните с матрицей 800x800 = 640 000 ячеек.

Код: dict + list

Базовая реализация на словаре:

adj: dict[int, list[int]] = {}

def add_edge(u: int, v: int) -> None:
    adj.setdefault(u, []).append(v)
    adj.setdefault(v, [])   # чтобы и вершина-приёмник имела запись (опционально)

add_edge(0, 1)
add_edge(0, 2)
add_edge(1, 2)
add_edge(2, 3)

print(adj)
# {0: [1, 2], 1: [2], 2: [3], 3: []}

Чище — через collections.defaultdict:

from collections import defaultdict

adj: dict[int, list[int]] = defaultdict(list)
adj[0].append(1)
adj[0].append(2)
adj[1].append(2)
adj[2].append(3)

defaultdict(list) сам создаёт пустой список при первом обращении к новому ключу — это убирает ручной setdefault.

Базовые операции:

def has_edge(u: int, v: int) -> bool:
    return v in adj[u]    # O(degree(u))

def neighbors(u: int) -> list[int]:
    return adj[u]          # O(1) — просто отдаём ссылку

def add_edge(u: int, v: int) -> None:
    adj[u].append(v)       # O(1) amortized

def remove_edge(u: int, v: int) -> None:
    adj[u].remove(v)       # O(degree(u))

Для неориентированного графа добавление ребра требует двух append-ов:

def add_undirected(u: int, v: int) -> None:
    adj[u].append(v)
    adj[v].append(u)

Сложность операций

Сравнение с матрицей:

• has_edge стал медленнее: O(degree) против O(1).
• neighbors стал быстрее: O(1)+O(degree) против O(V).
• DFS/BFS — O(V+E) против O(V^2). Это гигантская разница для sparse графов: на 100k вершин и 300k рёбер это O(400k) против O(10 млрд).
• Память — O(V+E) против O(V^2). Главный выигрыш.

Trade-off has_edge: список vs set

v in adj[u] — это O(degree). Если у вершины 1000 соседей и вы часто делаете edge-queries — медленно. Решение: хранить соседей не в list, а в set:

adj: dict[int, set[int]] = defaultdict(set)
adj[0].add(1)
adj[0].add(2)

def has_edge(u: int, v: int) -> bool:
    return v in adj[u]     # теперь O(1) для set

Trade-off: set занимает больше памяти, чем list (примерно в 4 раза для int) и медленнее итерируется. Если has_edge не критична, держите list. Если критична — set.

В некоторых задачах используют dict внутри dict для весов:

adj: dict[int, dict[int, float]] = defaultdict(dict)
adj[0][1] = 5.0       # ребро 0->1 с весом 5
adj[0][2] = 2.5

# has_edge O(1)
1 in adj[0]            # True
# weight O(1)
adj[0][1]              # 5.0

Это удобно для weighted графов: вес ребра доступен по ключу за O(1), плюс has_edge тоже O(1).

DE-кейс 1: lineage как dict[str, list[str]]

Самое естественное место для adjacency list — lineage. Каждая модель — ключ. Список — её прямые источники (или обратное направление, в зависимости от ориентации):

from collections import defaultdict

# adj[parent] = children   (стрелка от parent к child)
deps: dict[str, list[str]] = defaultdict(list)

# регистрируем зависимости из dbt manifest.json (упрощённо)
dbt_refs = [
    ("stg_users", "int_user_orders"),
    ("stg_orders", "int_user_orders"),
    ("stg_orders", "int_order_items"),
    ("stg_products", "int_order_items"),
    ("int_user_orders", "mart_user_revenue"),
    ("int_order_items", "mart_user_revenue"),
    ("int_order_items", "mart_top_products"),
]

for parent, child in dbt_refs:
    deps[parent].append(child)

# найти всё, что напрямую зависит от stg_orders
print(deps["stg_orders"])
# ['int_user_orders', 'int_order_items']

Хотите обратный индекс — «от каких моделей зависит данная»? Постройте второй dict:

parents: dict[str, list[str]] = defaultdict(list)
for parent, child in dbt_refs:
    parents[child].append(parent)

print(parents["mart_user_revenue"])
# ['int_user_orders', 'int_order_items']

Два словаря — для прямого и обратного обхода. Это и есть стандартный приём в lineage-сервисах.

DE-кейс 2: foreign-key схема Postgres

Берём information_schema.referential_constraints Postgres, получаем (parent_table, child_table). Строим adjacency list:

from collections import defaultdict
import psycopg

fk_graph: dict[str, list[str]] = defaultdict(list)

with psycopg.connect("dbname=app") as conn:
    rows = conn.execute("""
        SELECT
            kcu.table_name AS child,
            ccu.table_name AS parent
        FROM information_schema.referential_constraints rc
        JOIN information_schema.key_column_usage kcu
            ON kcu.constraint_name = rc.constraint_name
        JOIN information_schema.constraint_column_usage ccu
            ON ccu.constraint_name = rc.unique_constraint_name
    """).fetchall()

for child, parent in rows:
    fk_graph[parent].append(child)

print(fk_graph["users"])
# ['orders', 'sessions', 'logins', ...]

Из 300 таблиц с 800 FK получите словарь на 300 ключей и суммарно 800 значений. Все запросы «кто зависит от users» — O(degree) = в среднем 2-3 элемента.

NetworkX и зачем не писать свой adjacency list

В Python есть готовая библиотека networkx, в которой adjacency list уже реализован, плюс десятки алгоритмов:

import networkx as nx

G = nx.DiGraph()
G.add_edge("stg_users", "int_user_orders")
G.add_edge("stg_orders", "int_user_orders")
G.add_edge("stg_orders", "int_order_items")
G.add_edge("int_user_orders", "mart_user_revenue")

# соседи
print(list(G.successors("stg_orders")))
# ['int_user_orders', 'int_order_items']

# степени
print(G.in_degree("int_user_orders"))   # 2
print(G.out_degree("stg_orders"))       # 2

# проверка DAG
print(nx.is_directed_acyclic_graph(G))  # True

# topological sort — порядок исполнения
print(list(nx.topological_sort(G)))
# ['stg_users', 'stg_orders', 'int_user_orders', 'int_order_items', 'mart_user_revenue']

NetworkX внутри использует словарь словарей — dict[node][neighbor] = {attributes}. Это O(1) has_edge плюс место под атрибуты ребра.

Когда писать свой adjacency list:

• учебная задача, нужно понимать каждый шаг;
• большой граф, нужны нестандартные операции, недоступные в networkx;
• хочется минимизировать память (numpy + CSR, см. урок 04).

Когда брать networkx:

• продакшен-задача;
• стандартные алгоритмы;
• граф меньше миллиона вершин (выше — нужно что-то посерьёзнее, например graph-tool или igraph).

Pointer chasing и cache miss

В отличие от матрицы (один непрерывный блок), adjacency list — это много мелких объектов. dict хранит ссылки. Каждый список — отдельный объект в куче. Каждый int внутри списка (если хранятся Python int, не numpy.int) — тоже отдельный объект.

adj — dict (один объект)
adj[0] — list (отдельный объект)
adj[0][0] — int (отдельный объект)
adj[0][1] — int (отдельный объект)

Когда вы итерируете for v in adj[0], процессор читает один указатель за другим, прыгая по разным адресам в RAM. Это

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

Это противоречие: list экономит память (что важно для sparse), но теряет в скорости итерации (что важно для алгоритмов). В уроке 04 покажем, как CSR-формат решает это противоречие.

Попробуй сам

Постройте adjacency list для следующего графа и реализуйте функцию transitive_dependencies(model), которая возвращает всех предков модели — прямых и косвенных.

deps_raw = [
    ("stg_users",      "int_user_orders"),
    ("stg_orders",     "int_user_orders"),
    ("stg_orders",     "int_order_items"),
    ("stg_products",   "int_order_items"),
    ("int_user_orders","mart_user_revenue"),
    ("int_order_items","mart_user_revenue"),
    ("int_order_items","mart_top_products"),
]

Задачи:

1. Постройте parents = defaultdict(list), где parents[child] — список прямых предков.
2. Реализуйте transitive_dependencies(model) (рекурсивно или BFS — на ваш выбор).
3. Для mart_user_revenue ответ — {stg_users, stg_orders, stg_products, int_user_orders, int_order_items} (5 элементов в любом порядке).
4. Какая сложность вашего алгоритма в терминах V и E?

Ожидаемый ответ для пункта 4: O(V + E). Каждую вершину открыли максимум раз, каждое ребро прошли максимум раз. Это типичная сложность DFS/BFS на adjacency list — мы их разберём подробнее в модуле 13.

В следующем уроке сравним матрицу и список бок о бок: память, кэш, реальные числа и компромиссы.