Какая структура данных графа наиболее эффективна в Python? [закрыто]

Мне нужно уметь манипулировать большим (10 ^ 7 узлов) графом в Python. Данные, соответствующие каждому узлу / ребру, минимальны, скажем, небольшое количество строк. Каков наиболее эффективный с точки зрения памяти и скорости способ сделать это?

Диктовка диктов является более гибкой и простой в реализации, но я интуитивно ожидаю, что список списков будет быстрее. Опция list также потребует, чтобы я держал данные отдельно от структуры, в то время как dicts допускает что-то в этом роде:

graph[I][J]["Property"]="value"

Что ты предлагаешь?


Да, мне следовало бы прояснить, что я имею в виду под эффективностью. В данном конкретном случае я имею в виду поиск с произвольным доступом.

Загрузка данных в память не является большой проблемой. Это сделано раз и навсегда. Часть времени занимает посещение узлов, поэтому я могу извлечь информацию и измерить интересующие меня метрики.

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

Было бы здорово, если бы этот чрезвычайно популярный и полезный вопрос не был закрыт, потому что теперь мы застряли в устаревшей информации 2016 года.
OrangeSherbet 19 5.02.2019 20:45:33
На этот вопрос следует ответить, поскольку он требует конкретной вещи: «самый эффективный, с точки зрения памяти и скорости» способ манипулирования большим графом в Python.
fjsj 27.06.2019 18:49:42
Не согласен. Это не конкретный вопрос, потому что «манипулировать» в основном не означает ничего конкретного. Он не требует решения конкретной проблемы, и поэтому большинство ответов, которые он получил, являются просто рекомендациями библиотеки. Предположительно, если он будет открыт, будут рекомендованы новые библиотеки. Я бы предпочел удалить этот вопрос, если текущие ответы устарели.
Blorgbeard отсутствует 27.06.2019 22:43:27
Этот вопрос имеет значение для меня в 2019 году, но, к сожалению, закрыт только с networkxдействительно рекомендованным. Отличная работа, чтобы быть уверенным. Но это не numpyграфы.
Josh.F 3.07.2019 04:20:26
7 ОТВЕТОВ
РЕШЕНИЕ

Я настоятельно рекомендую вам взглянуть на NetworkX . Это боевой конь, испытанный в бою, и первый инструмент, доступный большинству «исследовательских» типов для анализа сетевых данных. Я без проблем манипулировал графиками с сотнями тысяч ребер на ноутбуке. Его функция богата и очень проста в использовании. Вы обнаружите, что сосредоточены больше на проблеме, а не на деталях базовой реализации.

Пример генерации и анализа случайного графа Эрдеша-Реньи


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

Визуализации также просты:

введите описание изображения здесь

Дополнительная визуализация: http://jonschull.blogspot.com/2008/08/graph-visualization.html

52
1.02.2013 14:56:19
NetworkX великолепен, но, к сожалению, у него есть проблемы с обработкой 10 ^ 7 узлов. Я обычно использую 16 ГБ ОЗУ с 2M узлами и 15M ребрами, а также с некоторыми атрибутами int. Забудьте о том, чтобы получить что-то более необычное, чем это
Синт 14.12.2012 11:45:36
Note NetworkX uses dicts to store the nodes and neighbors in a graph. Кажется неэффективным? Является ли docs.scipy.org/doc/scipy/reference/sparse.csgraph.html альтернативой?
эндолит 21.12.2018 02:16:27

Хотя этот вопрос сейчас довольно старый, я думаю, что стоит упомянуть мой собственный модуль Python для манипулирования графами, называемый graph-tool . Это очень эффективно, поскольку структуры данных и алгоритмы реализованы на C ++ с метапрограммированием шаблонов с использованием библиотеки графов ускорения. Следовательно, его производительность (как в использовании памяти, так и во время выполнения) сравнима с чистой библиотекой C ++ и может быть на несколько порядков лучше, чем в обычном коде Python, без ущерба для простоты использования. Я использую его постоянно для работы с очень большими графиками.

13
10.04.2012 08:59:11
Недавним конкурентом Graph-Tool является networkIt , также поддерживаемый c ++.
drevicko 27.03.2015 05:23:30
К сожалению, варианты установки / реализации графического инструмента - это кроличья нора.
Камбиз 3.03.2020 04:08:56

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

6
27.08.2008 10:01:21

Словарь может также содержать накладные расходы, в зависимости от фактической реализации. Хеш-таблица обычно для начала содержит некоторое простое число доступных узлов, даже если вы можете использовать только пару узлов.

Судя по вашему примеру «Недвижимость», вам лучше использовать классовый подход для финального уровня и реальных свойств? Или имена свойств сильно меняются от узла к узлу?

Я бы сказал, что то, что означает «эффективный», зависит от многих вещей, таких как:

  • скорость обновления (вставка, обновление, удаление)
  • скорость поиска в произвольном доступе
  • скорость последовательного поиска
  • используемая память

Я думаю, вы обнаружите, что структура данных, которая является быстрой, обычно потребляет больше памяти, чем медленная. Это не всегда так, но большинство структур данных, похоже, следуют этому.

Словарь может быть простым в использовании и дать вам относительно равномерный быстрый доступ, он, скорее всего, будет использовать больше памяти, чем, как вы предлагаете, списки. Однако списки, как правило, содержат больше служебных данных при вставке в них данных, если только они предварительно не выделяют узлы X, в которых они снова будут использовать больше памяти.

В общем, я бы предложил просто использовать метод, который кажется вам наиболее естественным, а затем провести «стресс-тест» системы, добавив к ней значительное количество данных и посмотреть, не станет ли это проблемой.

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

4
4.08.2008 12:09:55

Насколько я понимаю, произвольный доступ осуществляется в постоянном времени как для диктовок, так и для списков Python, разница в том, что вы можете осуществлять произвольный доступ только к целочисленным индексам со списками. Я предполагаю, что вам нужно искать узел по его метке, так что вы хотите, чтобы диктовалось.

Тем не менее, с точки зрения производительности загрузка его в память может не быть проблемой, но если вы используете слишком много, вы в конечном итоге перейдете на диск, что снизит производительность даже высокоэффективных диктов Python. Постарайтесь максимально сократить использование памяти. Кроме того, оперативная память сейчас удивительно дешева; если вы много делаете такого рода вещи, нет причин не иметь по крайней мере 4 ГБ.

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

3
6.08.2008 05:37:33

Создание структуры на основе классов, вероятно, будет иметь больше накладных расходов, чем структура на основе dict, поскольку в классах python фактически используются dicts, когда они реализуются.

2
4.08.2008 12:41:15
... за исключением случаев, когда вы используете __slots__, что вы, вероятно, хотели бы сделать здесь.
Даниэль Приден 15.12.2009 06:58:24

Без сомнения, NetworkX - лучшая структура данных для графа. Он поставляется с такими утилитами, как вспомогательные функции, структуры данных и алгоритмы, генераторы случайных последовательностей, декораторы, упорядочивание Кутхилла-Макки, контекстные менеджеры.

NetworkX великолепен, потому что он хорош для графиков, орграфов и мультиграфов. Он может написать график несколькими способами: Список смежности, Многострочный список смежности, Список границ, GEXF, GML. Работает с Pickle, GraphML, JSON, SparseGraph6 и т. Д.

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

1
18.01.2016 09:08:03