Эффективная структура данных графика Python

Question

У меня есть структура данных взвешенного графика, используемая в алгоритме машинного обучения, который требует частых изменений (вставки, удаления вершин и ребер).В настоящее время я использую матрицу смежности, реализованную с помощью массива двумерных массивов с записями

G[i, j] = W{i, j} if ij (is an edge) else 0

. Это хорошо работает для ребер | V |<1500, но очень медленно работает с операциями поиска, вставки и удаления.</p>

Так как я использую векторизованную оптимизацию встраивания графа на основе весов, мне нужно использовать массивы numpy, поэтому в этом случае использование списков невозможно.

Есть ли эффективные реализации графов, которые я могу использовать для хранения, и операции над графами, написанными на Python, которые можно использовать?

Answer 1

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

Некоторые из возможных решений вашей проблемы могут быть:

• Использовать структуры списка смежности для других операций и при необходимости преобразовывать в двумерные массивы (возможно, неэффективный)

• Использовать разреженную матрицу : попытаться использовать разреженную матрицу, чтобы вы могли выполнять матричные операции без преобразования назад и вперед.Вы можете прочитать больше о них в этом блоге .Обратите внимание, что вам придется заменить некоторые из простых операций на их эквиваленты scipy.sparse в вашем коде, если вы выберете это решение.

Answer 2

Попробуйте использовать библиотеку NetworkX, которая является одной из лучших для обработки Graph структур данных.