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

Через несколько дней (говно)кода стало много — вменяемого сервиса не получилось.

Один BFS принимал map[string][]string. DFS жил на другом типе графа. В одной реализации направленность задавалась на уровне графа, в другой вытекала из того, как было записано ребро. Опции существовали, но их комбинации не образовывали понятной политики. Result types возвращали срезы и числа, однако я не мог внятно ответить, что именно они гарантируют.

Проблема была не в том, что LLM «не умеет BFS». Я попросил реализации раньше, чем сформулировал общий контракт данных. Генератор заполнил пустые места правдоподобными допущениями — которые, очевидно, не совпали в разных кусках кода.

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

Минимальная модель проблемы

Ниже не исходный сгенерированный код, а короткая реконструкция одного из классов ошибок.

package naive

type Graph map[string]map[string]struct{}

func (g Graph) AddUndirected(a, b string) {
	if g[a] == nil {
		g[a] = make(map[string]struct{})
	}
	if g[b] == nil {
		g[b] = make(map[string]struct{})
	}

	g[a][b] = struct{}{}
	g[b][a] = struct{}{}
}

func (g Graph) Neighbors(id string) []string {
	out := make([]string, 0, len(g[id]))
	for neighbor := range g[id] {
		out = append(out, neighbor)
	}
	return out
}

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

Спецификация Go не задаёт порядок итерации по map и прямо разрешает ему меняться от одной итерации к другой. Не нужно знать внутреннее устройство runtime, чтобы увидеть последствие: Neighbors публикует порядок, которым сам не владеет.

Поверх этого графа можно написать обычный BFS.

package naive

func BFS(g Graph, start string) []string {
	seen := map[string]bool{start: true}
	queue := []string{start}
	order := make([]string, 0, len(g))

	for head := 0; head < len(queue); head++ {
		current := queue[head]
		order = append(order, current)

		for _, next := range g.Neighbors(current) {
			if seen[next] {
				continue
			}
			seen[next] = true
			queue = append(queue, next)
		}
	}

	return order
}

Возьмём граф:

api -> auth
api -> cache
auth -> db
cache -> worker

Пусть api связан с auth и cache, а оба узла находятся на глубине один. Последовательности:

[api auth cache db worker]
[api cache auth worker db]

— могут быть допустимыми BFS‑обходами: расстояния по числу рёбер не сломаны (не изменились). Но программный контракт зависит от того, куда попадает order.Если это отладочная информация, порядок можно объявить неопределённым.

Если это публичное поле результата, golden output, журнал, ключ кэша, parent tree или выбранный среди равных кратчайший путь, tie‑break должен кому‑то принадлежать. В наивной модели он случайно принадлежит представлению данных.

Контракт начинается ниже алгоритма

После этого я перестал воспринимать граф как пару контейнеров vertices + edges. Для библиотеки граф задаёт множество допустимых состояний и правила их публикации.

Нужно заранее решить:

• направленные рёбра или ненаправленные;

• разрешены ли ненулевые веса;

• можно ли смешивать ориентацию рёбер;

• допустимы ли петли и параллельные рёбра;

• кто создаёт отсутствующие вершины;

• чем идентифицируется ребро;

• возвращает query копию или ссылку на живую запись;

• какой порядок видит вызывающий код.

Часть этих решений в lvlath/core задаётся на конструировании.

package main

import (
	"fmt"
	"log"

	"github.com/lvlath/go/core"
)

func main() {
	g, err := core.NewGraph(
		core.WithDirected(false),
		core.WithWeighted(),
	)
	if err != nil {
		log.Fatal(err)
	}

	_, err = g.AddEdge("api", "db", 3, core.WithID("edge-api-db"))
	if err != nil {
		log.Fatal(err)
	}
	_, err = g.AddEdge("api", "cache", 1, core.WithID("edge-api-cache"))
	if err != nil {
		log.Fatal(err)
	}
	_, err = g.AddEdge("api", "auth", 2, core.WithID("edge-api-auth"))
	if err != nil {
		log.Fatal(err)
	}

	ids, err := g.NeighborIDs("api")
	if err != nil {
		log.Fatal(err)
	}

	fmt.Println(ids) // [auth cache db]
}

Из call site видно, что граф ненаправленный и допускает веса. У рёбер есть явные идентификаторы. NeighborIDs возвращает уникальные соседние ID в лексикографическом порядке. Порядок вставки в этот контракт не входит.

Да, такое решение не бесплатно: метод собирает набор соседей и сортирует результат. Зато вызывающая сторона не зависит от текущего вида внутреннего индекса и не получает разные tie‑breaks после замены одной структуры хранения на другую.

0, +Inf и отсутствующее ребро

Та же проблема появляется в матрицах, только уже без участия map.

В классической матрице смежности 0 часто обозначает отсутствие ребра. В weighted graph ноль может быть настоящим весом. Если обе ситуации кодируются одинаково, различие теряется до запуска Dijkstra или Floyd‑Warshall.

В lvlath/matrix числовая политика зависит от назначения матрицы.

Для обычной структурной матрици смежности допустима схема, где ноль означает отсутствие. Для zero‑preserving weighted adjacency конечный 0 остаётся весом ребра, а отсутствие кодируется через +Inf. В distance matrix диагональ равна нулю, +Inf означает недостижимость, а остальные конечные значения уже являются вычисленными расстояниями.

Последний случай особенно неприятен при обратном преобразовании. Metric closure содержит производные данные: ячейка D[A][C] = 7 может означать кратчайший путь через несколько промежуточных вершин, а не исходное ребро A -> C. Поэтому пакет не экспортирует metric‑closure matrix обратно в граф как будто это исходная topology.

Никакой алгоритм кратчайших путей не восстановит информацию, которую representation удалил заранее.

Ошибки тоже являются протоколом

Первым прототипам было достаточно вернуть error. Затем выяснилось, что текст ошибки быстро становится скрытым API.

package main

import (
	"errors"
	"fmt"
	"log"

	"github.com/lvlath/go/core"
)

func main() {
	g, err := core.NewGraph() // unweighted by default
	if err != nil {
		log.Fatal(err)
	}

	_, err = g.AddEdge("A", "B", 3)
	fmt.Println(errors.Is(err, core.ErrBadWeight)) // true
}

Вызов нарушает capability графа: для ненулевого веса нужен WithWeighted. Вызывающий код проверяет категорию через errors.Is, а не сопоставляет строку.

Выше по стеку категорий становится больше. Неизвестная вершина и недостижимая вершина требуют разных действий. Отмена контекста не равна исчерпанию лимита алгоритма. Timeout exact solver с готовым incumbent не равен завершённому доказательству оптимальности. Если все эти состояния свести к failed, вызывающий код начнёт угадывать смысл по тексту или по нулевым полям результата. |

Почему первая структура не выдержала

Первая публичная версия была устроена компактно:

graph/
├── algorithms/
├── core/
└── matrix/

В общей директории лежали BFS, DFS, Dijkstra, Prim и Kruskal. В IDE это выглядело аккуратно. Публичные контракты начали конфликтовать почти сразу же.

BFS нужен dequeue order, depth, parent tree, discovery set и частичный результат при остановке. DFS публикует finish order, строит другой parent relation и отдельно работает с cycle witnesses. Dijkstra должен различать unknown target, unreachable target и режим, в котором path tracking отключён. MST обязан договориться, возвращает ли он только дерево или допускает forest на несвязном графе.

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

Вторую проблему я создал сам: отложил документацию «до момента, когда код заработает». Когда начал описывать options, errors, ownership, numeric policy и partial results единым форматом, обнаружил, что уже реализовал несколько несовместимых версий одних и тех же понятий.

Пришлось остановить исходный сервис углублённого анализа и перестроить библиотеку. Вместо раннего плана с SAX, HMM, ARIMA, GBM и GJR‑GARCH я оставил последовательность, в которую можно войти без прыжков: core, matrix, BFS, DFS, Dijkstra, MST, flow, TSP и DTW.

v0.0.1 я выпустил как устанавливаемую точку отсчёта. Версия была слабой, но публичный tag заставил смотреть на структуру как пользователь(увидеть, где структура трещит в естественной среде), а не как автор внутри IDE.

Потом пришло первое письмо...

Первое письмо

После v0.0.1 написал другой Go‑разработчик. Он делал систему запуска бинарников и shell scripts; аргументы могли зависеть друг от друга или конфликтовать. Ему нужен был способ моделировать эти связи и быстро проверять корректность комбинации.

Это был не академический запрос на «пример BFS». Человек собирался положить собственное поведение поверх graph API.

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

Осознание, что твой API положат в основу чужой системы, мгновенно отрезвляет. Необходимо ужесточить требования к результату и поднять планку ожидаемого качества выше стандартных 80%, выше 90% и 95%... Покрытие показывает лишь то, какие строки код зацепил при выполнении, но ничего не говорит о его выживаемости. Можно обвешаться зелеными галочками и все равно пропустить скрытый aliasing срезов, отмену контекста в середине обхода или сломанный witness.

Погоню за цифрами покрытия вытеснила нормальная инженерная паранойя.В репозитории появились жесткие тесты на вырожденные входы, контроль владения возвращаемыми матрицами, проверки под -race и валидация частичных результатов. Даже example_test.go и документация стали обязаны компилироваться при каждой сборке, доказывая, что примеры не врут.

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

Одна алгоритмическая задача — один пакет

В v0.1.0 алгоритмы получили отдельные пакеты внутри одного Go module. У зависимостей появилось понятное направление:

                ┌── bfs
                ├── dfs
core ───────────├── dijkstra
   │            ├── mst
   │            └── flow
   │
   └── matrix ──┬── tsp
                └── dtw

Диаграмма упрощённая: у matrix есть адаптеры из core, а tsp предоставляет и graph facade. Смысл в другом — алгоритмический пакет не читает внутренние map графа и не знает, как устроен его индекс. Он получает только публичный контракт нижнего слоя. Go дополнительно запрещает циклические imports, поэтому нарушение направления быстро превращается в ошибку сборки, а не в архитектурную договорённость «на словах».

Такое деление не гарантирует хорошую архитектуру. Но оно хотя бы вынуждает каждый пакет отвечать за собственные options, result type, errors, complexity и набор отказов.

Все пакеты живут в одном Go module github.com/lvlath/go. Пользователь импортирует только нужную поверхность — например, github.com/lvlath/go/bfs — но не согласовывает версии десяти независимых модулей. Общий tag фиксирует совместимые версии core, matrix и алгоритмических пакетов. Для библиотеки на этой стадии это полезнее, чем отдельный go.mod в каждой директории.

Главная выгода проявилась в типах результатов. Универсальный TraversalResult выглядел удобно только до первого вопроса о значении поля Order. В BFS это порядок извлечения из очереди и обработки. В DFS — порядок завершения, то есть post‑order. Одно поле с одним комментарием не может честно означать оба варианта.

Поэтому BFS возвращает собственный Result: StartID, Order, Depth, Parent, Visited, Skipped. На ранней остановке Visited может содержать уже поставленные в очередь вершины, которых ещё нет в Order; это зафиксированная семантика частичного результата. DFS публикует finish order и отдельно имеет результат обнаружения циклов с каноническими witness cycles.

Dijkstra хранит карту расстояний и опциональную карту предшественников. Известная, но недостижимая вершина имеет расстояние +Inf; неизвестная цель возвращает другую ошибку; Prev == nil означает, что отслеживание пути было отключено. Эти состояния нельзя безопасно упаковать в одно поле Path []string с nil на все случаи.

В mst результат сообщает не только рёбра и общий вес, но и выбранный алгоритм, режим strict_tree или forest, количество компонент и их корни. Пакет не переключается молча с дерева на лес, если граф оказался несвязным.

flow возвращает Value, выбранный алгоритм, остаточную сеть, стороны минимального разреза, число дополнений и флаг частичного результата. При отмене значение уже протолкнутого потока может быть полезно, но без финальной residual network оно не выдаётся за полный сертификат max‑flow/min‑cut.

В tsp разница между полями Exact и Optimal принципиальна. Branch‑and‑Bound остаётся exact algorithm, но после timeout найденный incumbent не становится доказанным optimum. Christofides публикует формальный коэффициент 1.5 только при точном Blossom matching; greedy matching возвращает допустимый tour без этой гарантии. Поэтому в результате есть Algorithm, Exact, Optimal, TimedOut, ApproximationRatio, Iterations и NodesExpanded, а не только Tour и Cost.

DTW разделяет Distance, Reachable, PathTracked, сам путь, оконную политику и режим памяти. Дистанцию можно посчитать на двух rolling rows. Для восстановления alignment path нужна полная накопленная матрица. Если путь не отслеживался, это не то же самое, что «допустимого выравнивания нет».

По устройству это ближе всего к package‑by‑feature, а не к раскладке по техническим слоям. Публичная функция играет роль тонкого facade и передаёт работу внутреннему kernel. Опции задают политику до запуска, а не меняют скрытое глобальное состояние. Полноценный {algorithm}.Result хранит не только итоговый scalar, но и сведения, без которых его нельзя правильно интерпретировать. Sentinel errors становятся машинно‑проверяемым протоколом. Срезы, матрицы и графы в результатах либо принадлежат вызывающему коду, либо имеют явно описанное aliasing‑поведение.

Такое разделение не делает архитектуру хорошей автоматически. Оно делает стоимость ошибки локальнее. Изменение очереди BFS не должно менять семантику DFS. Новый lower bound в TSP не требует расширять core. Оптимизация хранения матрицы не даёт права поменять значение +Inf. Внутренний kernel можно переписать, пока facade, result и errors сохраняют опубликованный контракт.

Для каждого пакета я свёл четыре поверхности:

• GoDoc с публичным контрактом;

• docs/*.md с математикой, ограничениями и operational cases;

• {algorith}/example_test.go с запускаемыми сценариями;

• всевозможные тесты, которые проверяют опубликованные обещания.

Если source, GoDoc, examples и длинная документация расходятся, пакет фактически имеет несколько API одновременно.

Тест не должен закреплять случайность

Наивный happy‑path test легко превращает текущую реализацию в скрытый контракт. Например, тест может добавить рёбра в одном порядке, получить один Order и объявить его единственно правильным, хотя API порядок не определял.

Для NeighborIDs важнее другое свойство: разные допустимые истории построения должны давать одну и ту же документированную поверхность.

package core_test

import (
	"slices"
	"testing"

	"github.com/lvlath/go/core"
)

func TestNeighborIDsIgnoreInsertionOrder(t *testing.T) {
	orders := [][]string{
		{"db", "cache", "auth"},
		{"auth", "db", "cache"},
		{"cache", "auth", "db"},
	}
	want := []string{"auth", "cache", "db"}

	for _, order := range orders {
		g, err := core.NewGraph(core.WithDirected(false))
		if err != nil {
			t.Fatal(err)
		}

		for _, target := range order {
			if _, err = g.AddEdge("api", target, 0); err != nil {
				t.Fatal(err)
			}
		}

		got, err := g.NeighborIDs("api")
		if err != nil {
			t.Fatal(err)
		}

		if !slices.Equal(got, want) {
			t.Fatalf("insertion %v: got %v, want %v", order, got, want)
		}
	}
}

Тест не знает, хранится adjacency в map, sorted slice или другой структуре. Он проверяет только то, что наблюдает вызывающий код.

Для других алгоритмов нужны свои независимые проверки. У shortest path пересчитывается стоимость опубликованного пути. У MST проверяются связность, отсутствие циклов и сумма выбранных рёбер. У max flow — conservation, capacity constraints и согласованность с cut. У TSP — замкнутость тура, однократное посещение вершин и отдельно пересчитанная стоимость. Один scalar почти никогда не достаточен.

Детерминизм имеет цену. Я решил её измерять

После первых рефакторингов возник ожидаемый вопрос: сколько стоит вся эта строгость?

NeighborIDs не может просто вернуть содержимое map. Он собирает уникальные ID и сортирует их. BFS хранит не только очередь, но и Visited, Depth, Parent, Order. На отмене он возвращает частичный результат вместо того, чтобы выбросить накопленное состояние. Всё это требует времени и памяти.

Ответ «асимптотика та же» меня не устраивает. O(V+E) не показывает цену сортировки соседей, аллокаций result maps или callback hooks в конкретной Go‑реализации.

Поэтому в пакетах появились bench_test.go с несколькими формами нагрузки. Для core сейчас измеряются добавление обычных и взвешенных рёбер, параллельные рёбра, получение соседей у вершины степени 1000 и клонирование графа с тысячей рёбер. Для bfs есть цепочка из 10 001 вершины, бинарное дерево, сетка 100×100, связный sparse‑граф на 5000 вершинах и отдельное сравнение обхода с callback и без него.

Setup строится до b.ResetTimer(). Генераторы используют фиксированные параметры. Ошибка при построении топологии завершает benchmark, а не превращает его в измерение неизвестного графа. b.ReportAllocs() включён в горячих сценариях.

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

go test ./core ./bfs -run '^$' -bench 'Benchmark(AddEdge|Neighbors|BFS_)' -benchmem -cpu=1 -count=10 > graph-bench.txt
benchstat graph-bench.txt

Получаем следующие цифры:

benchstat graph-bench.txt
goos: darwin
goarch: amd64
pkg: github.com/lvlath/go/bfs
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
                                │ graph-bench.txt │
                                │     sec/op      │
BFS_Chain                             12.14m ± 1%
BFS_BinaryTree                        1.106m ± 1%
BFS_Grid                              19.08m ± 1%
BFS_RandomSparse                      16.06m ± 1%
BFS_HookOverhead/NoHook               1.137m ± 0%
BFS_HookOverhead/HeavyVisitHook       1.194m ± 0%
geomean                               4.212m

                                │ graph-bench.txt │
                                │      B/op       │
BFS_Chain                            2.177Mi ± 0%
BFS_BinaryTree                       280.2Ki ± 0%
BFS_Grid                             2.775Mi ± 0%
BFS_RandomSparse                     1.795Mi ± 0%
BFS_HookOverhead/NoHook              271.2Ki ± 0%
BFS_HookOverhead/HeavyVisitHook      271.2Ki ± 0%
geomean                              788.3Ki

                                │ graph-bench.txt │
                                │    allocs/op    │
BFS_Chain                             30.01k ± 0%
BFS_BinaryTree                        2.568k ± 0%
BFS_Grid                              49.61k ± 0%
BFS_RandomSparse                      30.97k ± 0%
BFS_HookOverhead/NoHook               3.013k ± 0%
BFS_HookOverhead/HeavyVisitHook       3.013k ± 0%
geomean                               10.12k

                                │ graph-bench.txt │
                                │       B/s       │
BFS_Chain                            1.574Mi ± 1%
BFS_BinaryTree                       1.764Mi ± 1%
BFS_Grid                             1.488Mi ± 1%
BFS_RandomSparse                     913.1Ki ± 2%
BFS_HookOverhead/NoHook              1.678Mi ± 1%
BFS_HookOverhead/HeavyVisitHook      1.602Mi ± 1%
geomean                              1.465Mi

pkg: github.com/lvlath/go/core
                   │ graph-bench.txt │
                   │     sec/op      │
AddEdge_Unweighted      5.114µ ± 11%
AddEdge_Weighted        4.728µ ± 11%
AddEdge_MultiEdges      1.843µ ± 11%
Neighbors               401.7µ ±  2%
geomean                 11.57µ

                   │ graph-bench.txt │
                   │      B/op       │
AddEdge_Unweighted     1.256Ki ± 13%
AddEdge_Weighted       1.252Ki ± 12%
AddEdge_MultiEdges       331.0 ±  0%
Neighbors              17.17Ki ±  0%
geomean                1.719Ki

                   │ graph-bench.txt │
                   │    allocs/op    │
AddEdge_Unweighted        10.00 ± 0%
AddEdge_Weighted          10.00 ± 0%
AddEdge_MultiEdges        2.000 ± 0%
Neighbors                 13.00 ± 0%
geomean                   7.141

Результаты не все приятные. Цепочка на 10 тысяч рёбер выделяет около 2,28 MB и делает примерно 30 тысяч аллокаций; сетка — почти 2,91 MB и около 49,6 тысячи аллокаций. Эти числа не объясняют источник затрат без профилирования, но и не дают ему исчезнуть за O(V+E). Разница между NoHook и HeavyVisit в одном прогоне около 3,4% при одинаковом числе аллокаций; утверждать больше без повторов и benchstat было бы преждевременно.

А вот колонка B/s (байт в секунду) в отчете выше — это место, где я поймал собственную ошибку оформления метрик. В нескольких сценариях я использовал:

b.SetBytes(int64(V + E))

Но V+E — количество сущностей, а не обработанные байты. Автоматический MB/s после такого вызова выглядит научно, но ничего честного не сообщает. Для статьи и следующих версий benchmarks это нужно заменить на явные метрики:

b.ReportMetric(float64(V), "vertices/op")
b.ReportMetric(float64(E), "edges/op")
b.ReportMetric(float64(V+E), "items/op")

Сама ошибка небольшая. Её смысл неприятнее: даже benchmark может публиковать правдоподобную цифру с неверной семантикой. Ровно от этого я пытался защитить библиотеку.

Я не собираюсь делать из одной машины таблицу «lvlath быстрее всех». Честный benchmark фиксирует commit, Go version, CPU, GOOS/GOARCH, GOMAXPROCS, workload, seed, timed region и число повторов. Сравнивать нужно один и тот же scenario между версиями либо несколько реализаций на одном входе. Цифра без протокола — такой же голый результат, как distance без path. Benchmarks здесь защищают не моё тщеславие как автора — они дают ещё один публичный контракт: после улучшения API стоимость не должна незаметно уехать в десять раз.

Что сейчас обещает библиотека

В начале текущей документации стоит жёсткая фраза:

Same graph, same options, same algorithm — same result surface, same witness semantics, same failure class.

Поддерживать её тяжелее, чем написать BFS.

Она описывает не только математическое ядро. Конструкторы должны одинаково проверять capabilities; query methods — сохранять порядок и владение; результаты — различать значение, свидетельство и частичное состояние; ошибки — оставаться проверяемыми через errors.Is. Оптимизация внутренней структуры не должна незаметно менять ни один из этих пунктов.

Все эти детали и есть библиотека — алгоритм находится в центре, но не заменяет систему вокруг него.

Сейчас в проекте остаются спорные границы. Exact Blossom и greedy matching пока находятся внутри tsp; если matching понадобится другим пакетам, появится основание вынести его отдельно. Список запланированных алгоритмов шире текущего релиза. Один module с несколькими packages выбран сознательно: пользователь получает одну версионированную поверхность зависимостей, а каждая алгоритмическая задача владеет своим API.

Модуль открыт. Если в core, matrix или алгоритмическом пакете находится неявное поведение, полезный issue должен содержать минимальный вход, фактический результат и ожидаемый контракт. Для математического возражения нужен контрпример; для API — воспроизводимый call site.

Код и материалы

• Репозиторий github.com/lvlath/go

• Пакет core: github.com/lvlath/go/tree/main/core

• Go Reference: pkg.go.dev/github.com/lvlath/go/core

• Issues и предложения API: github.com/lvlath/go/issues/new/choose

• Спецификация Go о порядке итерации map: go.dev/ref/spec#For_statements