Каков оптимальный способ создания графа с помощью метода add_edge_list ()? - PullRequest
Новая
       66

Каков оптимальный способ создания графа с помощью метода add_edge_list ()?

4 голосов
/ 08 мая 2019

Я пытаюсь создать большой граф с помощью библиотеки graph-tool (около 10 ^ 6 - 10 ^ 7 вершин) и заполнить свойство вершины именем вершины или использовать имена вместо индексов вершин. У меня есть:

  1. список имен: 

    ['50', '56', '568']

  2. набор ребер, но вместо индексов вершин он состоит из их имен: 

    edge_list = {frozenset({'568', '56'}), frozenset({'56', '50'}), frozenset({'50', '568'})}

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

Вот код моей программы: 

g = grt.Graph(directed=False)
edge_list = {frozenset({'568', '56'}), frozenset({'56', '50'}), frozenset({'50', '568'})}
ids = ['50', '56', '568']
g.add_edge_list(edge_list, hashed=True, string_vals=True)
print(g.vertex('50'))

Сообщение об ошибке print(g.vertex('50')): 

ValueError: Invalid vertex index: 50

Я хочу создать график:

  1. Использование только edge_list;
  2. Наличие быстрого доступа к вершине по ее имени;
  3. Оптимально по времени (и ОЗУ, если возможно).

Есть ли хороший способ сделать это?

EDIT: Текущий код: 

g = grt.Graph(directed=False)
g.add_vertex(len(ids))
vprop = g.new_vertex_property("string", vals=ids)
g.vp.user_id = vprop  
for vert1, vert2 in edges_list:
    g.add_edge(g.vertex(ids_dict[vert1]), g.vertex(ids_dict[vert2]))

1 Ответ

2 голосов
/ 08 мая 2019

Если у вас плотный граф с 10 ^ 6 - 10 ^ 7 вершинами (это какие-то медицинские данные или социальный граф? Он может изменить все) , вы не должны использовать networkx, потому что это написан на чистом Python, поэтому он в ~ 10-100 раз медленнее, чем graph-tool или igraph. В вашем случае я рекомендую вам использовать graph-tool. Это самая быстрая (~ как igraph) библиотека обработки графов Python.

graph-tool поведение отличается от networkx. Когда вы создаете узел networkx, его идентификатор - это то, что вы написали в конструкторе узла, поэтому вы можете получить узел по его идентификатору. В графическом инструменте каждый идентификатор вершины является целым числом от 1 до GRAPH_SIZE:

Каждая вершина в графе имеет уникальный индекс, который всегда находится между 0 и N − 1, где N - количество вершин. Этот индекс можно получить с помощью атрибута графа vertex_index (который является картой свойств, см. Карты свойств) или путем преобразования дескриптора вершины в тип int.

Каждая дополнительная информация о графе, вершинах или ребрах хранится в картах свойств . И когда вы используете .add_edge_list() с hashed=True, новая карта свойств возвращается как результат .add_edge_list(). Так что в вашем случае вы должны обрабатывать свои вершины следующим образом: 

# Create graph
g = grt.Graph(directed=False)

# Create edge list
# Why frozensets? You don't really need them. You can use ordinary sets or tuples
edge_list = {
    frozenset({'568', '56'}),
    frozenset({'56', '50'}),
    frozenset({'50', '568'})
}

# Write returned PropertyMap to a variable!
vertex_ids = g.add_edge_list(edge_list, hashed=True, string_vals=True)

g.vertex(1)

Out [...]: <Vertex object with index '1' at 0x7f3b5edde4b0>

vertex_ids[1]

Out [...]: '56'

Если вы хотите получить вершину в соответствии с идентификатором, вы должны создать отображение dict вручную (ну, я не гуру graph-tool, но я не могу найти простое решение):

very_important_mapping_dict = {vertex_ids[i]: i for i in range(g.num_vertices())}

Таким образом, вы можете легко получить индекс вершины: 

very_important_mapping_dict['568']

Out [...]: 0

vertex_ids[0]

Out [...]: '568'
...