Более элегантный способ создания матрицы смежности из списка кортежей - PullRequest
Новая
       28

Более элегантный способ создания матрицы смежности из списка кортежей

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

Предположим, мы начинаем с графика "дружбы", представленного списком кортежей, 

friendships = [(0, 1), (0, 2), (1, 2), (1, 3), (2,
3), (3, 4),(4, 5), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9)]

где элемент 0 является другом 1 (и, следовательно, 1 является другом 0).

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

У меня есть следующий (отталкивающий) код Python: 

def make_matrix(num_rows,num_cols,entry_fn):
    return [[entry_fn(i,j)
             for j in range(num_cols)]
            for i in range(num_rows)]
def adjacency(connections):
    new=connections+[(x[1],x[0]) for x in connections]
    elements=list(set([x[0] for x in connections]+ [x[1] for x in connections]))
    def test(i,j):
        if (elements[i],elements[j]) in new:
            return 1
        else: return 0
    return make_matrix(len(elements),len(elements),test)

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

[[0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 1, 1, 0, 0, 0, 0, 0, 0],
 [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
 [0, 1, 1, 0, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 1, 1, 0, 0],
 [0, 0, 0, 0, 0, 1, 0, 0, 1, 0],
 [0, 0, 0, 0, 0, 1, 0, 0, 1, 0],
 [0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]]

Обновление: согласно одному из ответов, у меня есть следующее возможное решение, хотя я не знаю, лучше ли это 

def adj(connections):
    ##step 1
    temp=(set(elem[0] for elem in connections).union(
        set(elem[1] for elem in connections)))
    n=max(temp)+1
    ans=[]
    ##step 2
    for i,_ in enumerate(temp):
        ans.append([])
        for j,_ in enumerate(temp):
            ans[i].append(0)
    ##step 3
    for pair in connections:
        ans[pair[0]][pair[1]]=1
        ans[pair[1]][pair[0]]=1
    return ans

Ответы [ 4 ]

5 голосов
/ 14 мая 2019

Мой алгоритм будет выглядеть примерно так:

  1. Найти максимальный идентификатор вершины. Назовите это n.
  2. Создать массив n+1 на n+1 нулей. Назовите это M.
  3. Для каждой пары x, y в списке ввода установите M[x][y] = 1

Чтобы придумать это решение, я сначала подумал о шаге 3. С учетом данного ввода это кажется наиболее простым способом заполнения матрицы смежности. Однако для этого требуется двумерный массив фиксированного размера. Так что проблема в том, как мне выяснить n для шага 2. Оттуда не нужно много думать, чтобы выяснить, шаг 1 - это то, что нужно.

Подробности оставлены в качестве упражнения для читателя.

1 голос
/ 14 мая 2019

Я не большой программист на Python, но что-то вроде ... 

def to_adjacency_matrix(pairs):
  size = 1 + max(map(max, pairs))
  a = [[0 for j in range(size)] for i in range(size)]
  for i, j in pairs:
    a[i][j] = a[j][i] = 1
  return a
0 голосов
/ 14 мая 2019

Я бы сделал: 

import numpy as np

def adjacency(connections):
    n_people = max(sum(connections, ())) + 1
    mat = np.zeros((n_people, n_people), dtype='int')
    for friend1, friend2 in connections:
        mat[friend1, friend2] = 1
        mat[friend2, friend1] = 1
    return mat

, и если под словом "с нуля" вы подразумеваете, что не хотите использовать numpy: 

def adjacency(connections):
    n_people = max(sum(connections, ())) + 1
    mat = [[0 for _ in range(n_people)] for _ in range(n_people)]
    for friend1, friend2 in connections:
        mat[friend1][friend2] = 1
        mat[friend2][friend1] = 1
    return mat
0 голосов
/ 14 мая 2019

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

import networkx as nx
G = nx.Graph()
G.add_edges_from(friendships)
nx.to_numpy_matrix(G)

, который будет возвращать пустую матрицу: 

matrix([[0., 1., 1., 0., 0., 0., 0., 0., 0., 0.],
        [1., 0., 1., 1., 0., 0., 0., 0., 0., 0.],
        [1., 1., 0., 1., 0., 0., 0., 0., 0., 0.],
        [0., 1., 1., 0., 1., 0., 0., 0., 0., 0.],
        [0., 0., 0., 1., 0., 1., 0., 0., 0., 0.],
        [0., 0., 0., 0., 1., 0., 1., 1., 0., 0.],
        [0., 0., 0., 0., 0., 1., 0., 0., 1., 0.],
        [0., 0., 0., 0., 0., 1., 0., 0., 1., 0.],
        [0., 0., 0., 0., 0., 0., 1., 1., 0., 1.],
        [0., 0., 0., 0., 0., 0., 0., 0., 1., 0.]])

или

nx.adjacency_matrix(G)

, который вернет скудную разреженную матрицу: 

<10x10 sparse matrix of type '<class 'numpy.int64'>'
    with 24 stored elements in Compressed Sparse Row format>
...