(Ориентированный) граф — это набор узлов, соединённых стрелками (рёбрами). В узлах и рёбрах могут содержаться данные. Вот примеры графов:
В программной инженерии графы встречаются повсюду:
Зависимости пакетов, равно как и импорты модулей, образуют ориентированные графы.
Интернет – это граф связей между веб-страницами.
Инструменты проверки моделей анализируют софт, исследуя «пространство состояний» всех возможных конфигураций. Узлы — это состояния, а рёбра — допустимые переходы между состояниями.
Реляционные базы данных — это графы, где в качестве узлов выступают записи, а в качестве рёбер — внешние ключи.
В виде графов можно обобщать связные списки, двоичные деревья и хеш-таблицы. Правда, хеш-таблицы — с оговоркой: это двудольные графы. С опорой на этот нюанс была доказана производительность операций кукушкиного хеширования.
Кроме того, графы распространены в бизнес-логике. Научные статьи сопровождаются ссылками, и они образуют графы цитирования. Транспортные сети — это графы маршрутов. Социальные сети — графы связей. Если вы достаточно давно работаете в айти, то где-нибудь вам точно попадались графы.
Я вижу графы повсюду и с их помощью анализирую всевозможные системы. В то же время я очень остерегаюсь задействовать графы в моём коде. В мейнстримовых языках программирования графы практически не поддерживаются. Ни в одном распространённом языке нет встроенного типа для графов, лишь в немногих языках графы присутствуют в стандартной библиотеке, а в экосистеме у многих нет надёжной сторонней библиотеки для поддержки графов. Как правило, графы приходится выкатывать с нуля. Настоящая пропасть зияет между тем, насколько часто инженер-программист мог бы использовать графы, и как слабо они поддерживаются в экосистемах для программирования. Где же все графовые типы?
Чем больше мне доводилось сталкиваться с графами по работе, тем более и более интригующим казался мне этот вопрос. Так что однажды я всё-таки попытался найти на него ответ. Я кинул клич у меня в рассылке, обратившись к тем, кто может обладать релевантным опытом: к разработчикам графовых алгоритмов, членам комитетов по разработке языков, к тем, кто поддерживает графовые библиотеки. Я собирался поговорить с дюжиной человек, но в итоге ограничился четырьмя собеседниками:
Зайнц: бывший разработчик ядра решателя ограничений для инструмента Gecode, «реализовавший все до одного графовые алгоритмы в этом инструменте».
Брэдфорд: автор библиотеки для обеспечения безопасности Nosey Parker и изобретатель нескольких новых графовых алгоритмов.
Николь: в прошлом разрабатывала графовые базы данных
Келли: ответственный за поддержку графовой библиотеки NetworkX для Python и разработчик компилятора.
Все четверо давали схожие ответы, так что я ограничился четырьмя интервью и засел за пост.
При проектировании есть слишком широкий разброс вариантов
До сих пор мы говорили об ориентированных графах. Есть ещё и неориентированные графы, где рёбра не имеют направления. Как ориентированные, так и неориентированные графы могут быть либо простыми графами, где между двумя узлами пролегает максимум одно ребро, либо мультиграфами, где таких рёбер может быть несколько. Затем для каждого из обоих этих типов существуют гиперграфы, где одно ребро может объединять три и более узлов, и сверхграфы, где рёбра могут быть направлены на другие рёбра. При работе с каждым из этих вариантов приходится определиться ещё с некоторыми деталями. Например, будете ли вы присваивать id только узлам, либо ещё и рёбрам? Какие данные могут храниться в узле, а какие — в ребре? Много решений в рамках библиотеки!
Но подождите, а важны ли все эти различия? Ведь простой граф — это всего лишь вырожденный мультиграф, а неориентированное ребро можно без потерь преобразовать в два ориентированных ребра. Поэтому в языке можно было бы предусмотреть «ориентированные гиперсверхмультиграфы», а далее позволить программисту ограничивать их так, как ему потребуется.
При таком подходе возникает две проблемы. Прежде всего, будет меняться интерфейс — в зависимости от того, что именно будут возвращать одиночные операции: отдельные значения или списки. Во-вторых, о чём мы поговорим ниже, у графовых алгоритмов очень важна производительность, поэтому частные случаи очень существенны. Келли привёл пример с максимальным взвешенным соответствием. Если вам известно, что ваш граф «двудольный», то для поиска соответствий можно воспользоваться конкретным быстрым алгоритмом, тогда к��к с другими графами придётся задействовать более медленный алгоритм широкого профиля.
Келли: [здесь] мы возвращаемся к «проблеме распределения алгоритмов». Имея задачу P, граф G и алгоритмы A, B, C для решения P на G… какой из алгоритмов применить? Если мы не уверены, что граф G двудольный, а алгоритм C работает лишь на двудольных графах, то сколько ресурсов мы можем потратить, чтобы определить, является ли граф G двудольным?
Идеальная графовая библиотека должна поддерживать множество различных видов графов. Но на это потребовалось бы потратить силы и время, отвлекаясь от поддержки того, что пользователи хотят делать с графами. Печально известно, насколько сложно наладить корректную работу с графовыми алгоритмами. В этом эссе автор языка Python рассказывает, как реализовал собственный алгоритм find_shortest_path. Его пришлось уточнять и корректировать пять раз!
Все до одной реализации pagerank, которые я брала для сравнения, оказались неправильными. — Николь.
Итак, какие алгоритмы должны войти в состав библиотеки? По мнению Келли, «люди хотят добиться при помощи графов абсурдно многого». Мой опыт это подтверждает, и все мои ��обеседники с Келли тоже согласны. Иногда кажется, что графы слишком мощные, и я не в состоянии понять всех их возможностей. По мнению Келли, «важно определить, где делать талию».
В случае с NetworkX эта «талия» отсекает примерно 500 разных графовых алгоритмов, которые в совокупности содержат почти 60 000 строк кода. Для сравнения: вся стандартная библиотека Python, в которой 300 пакетов, насчитывает чуть менее 600 000 строк кода.
С учётом сказанного, неудивительно, что в стандартных библиотеках вы не встретите графов. Команде по поддержке языка пришлось бы решать, какие типы графов поддерживать, какие топологии вынести в разряд частных случаев и какие алгоритмы включить в библиотеку. Целесообразно делегировать поддержку всех этих возможностей разработчикам сторонних библиотек. Такая тенденция в разработке языков уже стала мейнстримом: даже Python, известный своим подходом «всё включено», избавился от 20 батареек.
Сторонние разработчики могут делать осознанный выбор как при проектировании графов, так и при подборе алгоритмов для включения в библиотеку. Но далее приходится решать следующую проблему: когда у нас уже есть интерфейс графа, как нам его представить?
Слишком широкий выбор вариантов для реализации
Допустим, мы поддерживаем лишь «скелет» из простых ориентированных графов: узлы идентифицируются, рёбра – нет, равно как и любые ассоциированные с ними данные. Как запрограммировать следующий граф?
Вот четыре способа, которыми можно сохранить такую структуру внутри языка программирования:
Список рёбер:
[[a, b], [b, c], [c, a], [c, b]]Список смежности:
[[b], [c], [a, b]]Матрица смежности:
[0 1 0; 0 0 1; 1 1 0]Набор из трёх структур, взаимно связанных ссылками
Различные графовые операции демонстрируют разные характеристики производительности в зависимости от того, как они представлены. Возьмём, к примеру, ориентированный граф со 100 узлами и 200 рёбрами. Если представить его как матрицу смежности, то нам потребуется матрица 100×100, в которой будет 200 единиц и 9 800 нулей. Если же воспользоваться списком рёбер, то нам понадобится всего 200 пар узлов. В зависимости от выбранного языка программирования и степени оптимизации, разница в потреблении памяти может быть двадцатикратной и выше.
А теперь давайте возьмём граф со 100 узлами и 8 000 рёбер и попробуем выяснить, есть ли ребро между узлами 0 и 93. В матричном представлении это поиск со сложностью O(1) на graph[0][93]. Если граф представлен как список рёбер, то нам придётся со сложностью O(|ребро|) перебрать все 8 000 рёбер. Можно решить эту задачу эффективнее, если держать список рёбер в отсортированном виде. Тогда придётся выполнить двоичный поиск со сложностью O(log(|e|)), но в таком случае вставка рёбер будет обходиться дороже.
Графы, в которых мало рёбер, называются разреженными, а графы, в которых почти все узлы соединены рёбрами, называются плотными. Может быть так, что в одной и той же программе потребуется оперировать графами обеих топологий. Если вы собираете графы из внешних данных, то можно начать с разреженного графа, а затем перейти к плотному. Нет «хорошего варианта» для внутреннего представления графа.
Причём все эти беды возникают с самым элементарным ориентированным графом! А как насчёт реализации данных об узлах? Данных о рёбрах? Что делать с разными типами узлов и рёбер? Большинство сторонних библиотек относятся к одной из двух следующих категорий:
1. Предлагают один насыщенный тип данных, который (ценой снижения эффективности) охватывает все варианты использования. В библиотеке NetworkX граф хранится как словарь словарей словарей. В таком случае, как в узлах, так и в рёбрах могут храниться какие угодно данные. В библиотеке NetworkX есть функции, при помощи которых можно преобразовывать графы в другие представления, но эти функции не позволяют напрямую работать с этими представлениями.
2. Предлагают отдельный тип графа для каждого представления, после чего уже пользователь должен позаботиться о том, чтобы данные узлов и рёбер хранились отдельно от типа графа.
Примером из второй категории является Petgraph, самая популярная графовая библиотека для Rust. В Petgraph предусмотрены варианты graph, graphmap и matrix_graph для использования в различных случаях. Брэдфорд использует Petgraph в Nosey Parker — инструмента для обеспечения безопасности, который проверяет секреты за всю историю репозитория в git. Граф бенчмарков он построил на материале CPython, в репозитории которого содержится 250 000 коммитов и 1,3 миллиона объектов, но всего по несколько рёбер на узел каждого коммита. Он решил воспользоваться списком смежности.
При необходимости поддерживать множество представлений возникает серьёзное осложнение: приходится выполнять гораздо больше работы, связанной с добавлением алгоритмов. Если вы пишете отдельную версию алгоритма для каждого представления графа, то бремя поддержки утраивается или учетверяется. Если же, напротив, написать обобщённую абстракцию, охватывающую полиморфные типы, то ваша библиотека получится не слишком производительной. По оценке одного программиста, специально написанный графовый алгоритм может быть в 20 раз производительнее, чем обобщённый.
Это и есть главная жалоба всех моих собеседников.
Производительность чрезвычайно важна
«Обобщённая» реализация графа — это зачастую несерьёзно. — Брэдфорд.
В гранит.
Многие, многие из графовых алгоритмов — NP-полные или сложнее. Так, 14 из 21 канонических NP-полных проблем относятся к графам. Притом, что NP-полнота зачастую приемлема в крупных задачах, задачи с графами бывают колоссальными. Как от специфики реализации алгоритма, так и от того, как вы решили его представить, серьёзно зависит, насколько быстро может быть обработана задача.
У всех моих собеседников нашлось, что рассказать на эту тему. Например, Брэдфорду при работе над Nosey Parker требовалось реконструировать мгновенный снимок файловой системы для каждого коммита, и для этого нужно было обходить граф объектов. Ни один из четырёх имеющихся обходчиков графов не масштабировался настолько, чтобы обслужить этот случай. Пришлось на ходу спроектировать «полуноваторский» алгоритм обхода графов, благодаря которому удалось сократить объём занимаемой памяти в тысячу раз.
При помощи [petgraph] мне довольно быстро удавалось заставить работать демонстрационную модель, но потом… как раз один из тех случаев, в которых из-за ограничений производительности вас ждёт жёсткое столкновение с реальностью. — Брэдфорд.
Зайнц подчеркнул другую проблему: что, если граф слишком велик, чтобы работать с ним? Он привёл пример: найти решение для игры в пятнашки. Для этого во всё пространстве состояний прогоняется A*-поиск. В рассматриваемом пространстве более 20 триллионов состояний.
Если вы генерируете все узлы, то уже проиграли. — Зайнц
Зайнц курировал один исследовательский проект, в рамках которого требовалось добавлять графы в решатель ограничений Gecode. В итоге пришли к выводу, что графовый тип общего назначения просто не выдерживает конкуренции с подходом, когда представление задачи подбирается вручную.
Даже графовые базы данных, спроектированные с единственной целью — обслуживать сложные графовые алгоритмы — с трудом справляются с этой проблемой. Николь, разработчица графовых баз данных, рассказала мне о некоторых вызовах, с которыми приходилось сталкиваться при оптимизации даже элементарных операций над графами.
При выполнении обхода приходится либо ограничить его глубину, либо смириться с тем, что вы посетите не весь граф. Если вы выполняете поиск в глубину по принципу «сделай три шага отсюда и найди путь, если он существует», то вы просто берётесь посетить изрядное количество данных — Николь
Сменив работу, она подвизалась консультантом по повышению производительности графовых запросов. Обычно выход был в том, чтобы сменить графовую базу данных на какую-нибудь другую. Она рассказала мне об одном таком проекте: для ускорения запросов к графам она оставила одно вычисление в неизменном виде, а всё остальное переписала как процедуры MapReduce. «Получилось гораздо сложнее для понимания, — сказала она, — но работа реально выполнялась за ночь».
Всё это означает: если вам требуется решать задачи, связанные с обработкой графов, то вы должны очень детально контролировать специфику вашего представления данных и алгоритм. Пренебрегать производительностью просто недопустимо.
Единодушно сошлись на следующем
Вот почему отсутствует широкая поддержка графов:
Существует множество различных разновидностей графов
Существует множество разных представлений для каждой разновидности графа
Есть много разных графовых алгоритмов
Производительность графового алгоритма очень сильно зависит от представления графа и деталей его реализации
Приходится выполнять очень дорогостоящие алгоритмы на очень больших графах.
Вот почему графы не поддерживаются в языках программирования на уровне стандартных библиотек: слишком много решений приходится принимать при проектировании, идти на множество компромиссов, а поддержка графов очень обременительна. Бывает, что именно поэтому программисты стараются не прибегать к сторонним графовым библиотекам: зачастую библиотеки или слишком ограниченные, или слишком медленные. Кроме того, именно поэтому программист не любит размышлять о задаче на языке графов, кроме как в крайних случаях; с графами банально слишком сложно работать.
С тех пор, как я занялся этим исследованиям, уже на работе мне довелось столкнуться с несколькими новыми проблемами, касающимися графов. Я по-прежнему люблю оценивать системы как графы, но реализовывать графы боюсь. Теперь же вы знаете, почему их все боятся. Спасибо, что дочитали, осталось приложение.
Приложение: языки с графовыми типами
Графовые языки запросов
Графовые языки запросов (GQL) соотносятся с графовыми базами данных так же, как SQL с реляционными базами данных. Не путайте их с языком GQL, который позиционируется как стандарт для таких взаимосвязей и сейчас находится в разработке. В настоящее время распространённого стандарта такого рода не существует, а два из наиболее популярных — это SPARQL для запрашивания RDF-троек и cypher для работы с Neo4j. Забавно, что GraphQL не является графовым языком запросов, а лишь называется так из-за того, что связан с графовым поиском Facebook. На мой взгляд, графовые базы данных в основном отличаются от графов, применяемых в языках программирования, но соответствующие таким базам языки запросов демонстрируют, как графы могут работать в рамках языка программирования.
Основное отличие между всеми GQL и SQL заключается в том, что «объединения» (отношения) являются сущностями первого класса. Представьте себе датасет, единицами которого являются фильмы и люди, где люди действуют так: режиссируют, продюсируют фильмы или играют в них. На SQL каждое из этих отношений можно было бы реализовать в виде отношений «многие ко многим». Поэтому легко сформулировать запрос вида «кто играл в фильме X», но сложно — «у кого была любая роль в фильме Y, и что это была за роль». В SPARQL все отношения представлены в виде рёбер, поэтому такой же запрос сделать легко.
PREFIX mv: <your_movie_ontology_URL>
SELECT ?person ?role
WHERE {
?person ?role mv:casablanca.
}В Cypher есть похожая конструкция. GQL также могут оперировать рёбрами: обращать их, сочетать, делать транзитивное замыкание и т.д. Если бы мы хотели найти актёров, отстоящих на некоторое количество связей от Кевина Бэкона, то могли бы написать:
PREFIX mv: <your_movie_ontology_URL>
SELECT ?a
WHERE {
mv:kbacon (:acted_in/^:acted_in)+ ?a.
# a/b = объединение двух операций поиска
# ^a = обратное a
# a+ = транзитивное замыкание
}В SPARQL невозможно ни указать длину пути, ни выполнить вычисление, следуя по пути. Например, не получится собрать цепочку фильмов, объединяющих двух актёров. GQL, поддерживающие такие возможности, устроены значительно сложнее.
Основной вывод, который я сделал, познакомившись с GQL — там есть полезные примитивы для обхода, которые должен был бы предоставлять язык программирования с поддержкой графов. Интересно, что язык для формальных спецификаций Alloy предоставляет все эти примитивы для своего типа данных «отношение» (relation). Именно поэтому мне гораздо проще работать с графовыми представлениями на Alloy, чем на полноценном языке программирования. При этом все такие языки работают с размеченными рёбрами и могут быть неприменимы с другими графовыми представлениями.
Мейнстримовые языки, в стандартных библиотеках которых содержатся графы
В Python в 2020 году была добавлена библиотека graphlib. Судя по дискуссии, выложенной здесь, дело было в том, что топологическая сортировка является «фундаментальным алгоритмом» и будет полезна для «реализаций логики MRO (порядок разрешения методов) на чистом Python». В Graphlib нет иных методов кроме TopologicalSorter, который всего лишь принимает графы, представляемые в виде словарей узлов. Здесь необычно, что словарь узлов строится в обратном направлении: граф a -> b представляется как {b: [a]}.
По состоянию на 2023 год, нигде в CPython не используется graphlib, и на неё ссылаются менее 900 файлов на Github. Для сравнения, в 2020 году в Python был добавлен ещё один пакет, zoneinfo, который фигурирует более чем в 6 000 файлах. Причём термин def topological_sort( фигурирует в 4 000 файлах. Правда, предположу, что многие из них появились до 2020 года. Если посмотреть по диагонали, то создаётся впечатление, что все эти специализированные сортировки принимают иные графовые представления, чем graphlib, поэтому, несмотря ни на что, они не поддаются конвертации. Очень важно, как представлен граф.
Я нашёл графовые типы ещё в двух языках: Erlang и SWI-Prolog. Обоих этих языков я не знаю и не могу сказать, когда были добавлены эти типы. В Erlang, как минимум, это точно произошло ранее 2008 года. Я обратился к одному человеку, входящему в комитет разработки ядра языка Erlang, но ответа от него не дождался.
Графовые языки
Есть языки программирования, в которых «всё граф» в том же смысле, как в bash «всё строка», а в lisp «всё список». Пара примеров такого рода — GP2 и Grape. Я немного переписывался с людьми, работающими в этой сфере, и на момент подготовки оригинала статьи она остаётся крайне академической.
Математические языки программирования
В Mathematica, MATLAB, Maple и им подобных языках в той или иной форме присутствуют графовые библиотеки. Но я не готов купить лицензии на их использование за несколько тысяч долларов, только лишь чтобы их подробнее изучить.
Некоторые комментарии к оригиналу этого поста собраны здесь.