Что является наиболее эффективной структурой графа данных в Python?

голоса
63

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

ДИКТ из dicts является более гибкой и проще в реализации, но я интуитивно ожидаем список списков быстрее. Вариант списка будет также требовать, чтобы я сохранить данные отдельно от структуры, в то время как dicts позволило бы что-то в этом роде:

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

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


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

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

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

Задан 04/08/2008 в 13:00
источник пользователем
На других языках...                            


7 ответов

голоса
51

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

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


"""
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

Ответил 26/08/2008 d 18:43
источник пользователем

голоса
12

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

Ответил 27/11/2010 d 15:10
источник пользователем

голоса
6

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

Ответил 27/08/2008 d 11:01
источник пользователем

голоса
4

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

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

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

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

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

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

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

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

Ответил 04/08/2008 d 13:09
источник пользователем

голоса
3

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

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

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

Ответил 06/08/2008 d 06:37
источник пользователем

голоса
2

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

Ответил 04/08/2008 d 13:41
источник пользователем

голоса
1

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

NetworkX является большим, потому что wowrs для графов, орграфов, мультиграфов. Он может написать граф с несколькими способами: Примыкание List, Multiline Список смежности, Список Край, GEXF, GML. Он работает с соленья, GraphML, JSON, SparseGraph6 и т.д.

Он имеет implimentation различных radimade алгоритмов, включая: Сближение, двудольные, границы, Сосредоточенность, Clique, кластеризация, Раскраска, компоненты, Связь, циклы, направленный ациклический граф, Distance мер, Доминирующие множества, эйлеровых, Изоморфизм, Link Analysis, Link Prediction, Matching , минимальное Spanning Tree, Rich Club, кратчайший путь, Traversal, Дерево.

Ответил 18/01/2016 d 09:08
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more