Создайте взвешенный граф из матрицы смежности в графе инструмент, интерфейс Python

Как мне создать граф, используя graph-tool в python, из матрицы смежности? Предположим, у нас есть adj матрица как матрица смежности.

Что я делаю сейчас так:

        g = graph_tool.Graph(directed = False)
        g.add_vertex(len(adj))
        edge_weights = g.new_edge_property('double')
        for i in range(adj.shape[0]):
            for j in range(adj.shape[1]):
                if i > j and adj[i,j] != 0:
                    e = g.add_edge(i, j)
                    edge_weights[e] = adj[i,j]

Но это не правильно, у нас есть лучшее решение для этого?

(и я думаю, что правильный тег для этого будет graph-tool, но я не могу добавить это, какой-нибудь добрый человек с достаточными правами может сделать тег?)

Источник

5 ответов

Решение

Graph-tool теперь включает функцию добавления списка ребер к графику. Теперь вы можете сделать, например:

adj = numpy.random.randint(0, 2, (100, 100)) # a random directed graph
g = Graph()
g.add_edge_list(transpose(adj.nonzero()))
Источник

Это расширение ответа Тиаго для взвешенного графика:

adj = numpy.random.randint(0, 10, (100, 100)) # a random directed graph
idx = adj.nonzero()
weights = adj[idx]
g = Graph()
g.add_edge_list(transpose(idx)))

#add weights as an edge propetyMap
ew = g.new_edge_property("double")
ew.a = weights 
g.ep['edge_weight'] = ew
Источник

grap-tool не предоставляет прямой способ построения графа из матрицы смежности. AFAIK, он использует представление графа списков смежности из библиотеки Boost Graph, что может быть причиной для этого (хотя, возможно, автор предоставит реализацию для него в будущем).

Мне приходилось работать с графическим инструментом для построения графа из матрицы смежности, и мой код выглядел очень похожим на ваш - и он не чувствовал себя так плохо. Если матрица смежности является результатом некоторых предыдущих вычислений, я не думаю, что вы можете найти более красивое решение. Однако, если он читается из файла, вы можете рассмотреть возможность использования этого кода один раз, чтобы прочитать график и сохранить его в каком-либо формате, который принимает графический инструмент (см. save(),load() а также load_graph()в документации по Graph_tool и в разделе быстрого ввода / вывода Graph).

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

g = graph_tool.Graph(directed = False)
g.add_vertex(len(adj))
edge_weights = g.new_edge_property('double')
num_vertices = adj.shape[0]
for i in range(num_vertices - 1):
    for j in range(i + 1, num_vertices):
        if adj[i,j] != 0:
            e = g.add_edge(i, j)
            edge_weights[e] = adj[i,j]
Источник

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

Для последней версии (2.26) graph_tool Я полагаю, что там отсутствует транспонирование. i,j элемент матрицы смежности обозначает вес ребра, идущего от вершины j к вершине iтак и должно быть

g.add_edge_list(transpose(transpose(adj).nonzero()))
Источник 
      import numpy as np
import graph_tool.all as gt

g = gt.Graph(directed=False)
adj = np.tril(adj)
g.add_edge_list(np.transpose(adj.nonzero()))

Безnp.trilматрица смежности будет содержать записи с 2 вместо одной 1, потому что каждое ребро считается дважды. Вещи какgt.num_edges()тоже будет неверным.

Источник
Другие вопросы по тегам