Как преобразовать список смежности в матрицу смежности в Python

У меня есть список смежности, подобный этому:

0 1 4 5
1 0 2 6
2 1 3 7
3 2 4 8
4 0 3 9
5 0 7 8
6 1 8 9
7 2 5 9
8 3 5 6
9 4 6 7

Где первая строка говорит, что 0 находится рядом с 1, 4 и 5; во второй строке говорится, что 1 находится рядом с 0, 2 и 6; третья строка говорит, что 2 находится рядом с 1, 3 и 7, ...

Как я могу преобразовать его в матрицу смежности?

0 1 0 0 1 1 0 0 0 0
1 0 1 0 0 0 1 0 0 0
0 1 0 1 0 0 0 1 0 0
0 0 1 0 1 0 0 0 1 0
1 0 0 1 0 0 0 0 0 1
1 0 0 0 0 0 0 1 1 0
0 1 0 0 0 0 0 0 1 1
0 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 1 0 0 0
0 0 0 0 1 0 1 1 0 0

python-3.x python adjacency-list adjacency-matrix
person Stina V    schedule 09.03.2021    source источник
comment
Вы используете numpy? a = np.zeros((10,10)) / a[0,[1,4,5]] = 1 сделают это.   -  person Tim Roberts    schedule 09.03.2021
comment
Привет, @tim, спасибо за быстрый ответ, я попробовал твой метод, и вместо этого он дал мне эту матрицу: [[0. 1. 0. 0. 1. 1. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]][[0. 1. 0. 0. 1. 1. 0. 0. 0. 0.]   -  person Stina V    schedule 09.03.2021
comment
* эта матрица повторяется несколько раз, я неправильно набрал? Я предположил, что вы / имели в виду пропуск строки   -  person Stina V    schedule 09.03.2021
comment
Я показывал вам пример для первой строки, предполагая, что вы можете расширить его до цикла, который обрабатывает все это. Я опубликую ответ, показывающий, что я имею в виду.   -  person Tim Roberts    schedule 10.03.2021

Ответы (2)


arrow_upward
0
arrow_downward

Как насчет создания списков позиционированных 0 и 1 одинаковой длины внутри фрейма данных, а затем их извлечения в виде серий.

# the lists will all be this length
maxlen = df.max().max()

df = pd.DataFrame([
    [0, 1, 4, 5],
    [1, 0, 2, 6],
    [2, 1, 3, 7],
    [3, 2, 4, 8],
    [4, 0, 3, 9],
    [5, 0, 7, 8],
    [6, 1, 8, 9],
    [7, 2, 5, 9],
    [8, 3, 5, 6],
    [9, 4, 6, 7]])

# the function used to create the lists
def createlist(x):
    arr=(maxlen+1)*[0]
    arr[x]=1
    return arr

# create the list for each cell, then concatenate the lists per row vertically, sum them, giving each final row
df2 = df.applymap(createlist).apply(lambda x: pd.concat([pd.Series(x[i]) for i in range(len(df.columns))], axis=1).sum(axis=1),axis=1)


df2

    0   1   2   3   4   5   6   7   8   9
0   1   1   0   0   1   1   0   0   0   0
1   1   1   1   0   0   0   1   0   0   0
2   0   1   1   1   0   0   0   1   0   0
3   0   0   1   1   1   0   0   0   1   0
4   1   0   0   1   1   0   0   0   0   1
5   1   0   0   0   0   1   0   1   1   0
6   0   1   0   0   0   0   1   0   1   1
7   0   0   1   0   0   1   0   1   0   1
8   0   0   0   1   0   1   1   0   1   0
9   0   0   0   0   1   0   1   1   0   1

Чтобы установить диагональ на нули, сделайте что-то вроде:

df3 = df2.values

np.fill_diagonal(df3, 0)
person forgetso    schedule 09.03.2021
comment
Спасибо @forgetso, не думал о преобразовании его в фрейм данных pandas, так намного проще манипулировать. Быстрый вопрос, как бы вы передавали 0 вместо 1 при ссылке на себя? например 0 должен показывать 0 в первой ячейке (не считая индекса) вместо 1, 1 должен показывать 0 во 2-м столбце, 2-й строке вместо 1 и т. д. Кроме того, есть ли способ удалить столбцы и индекс строки? - person Stina V; 10.03.2021
comment
Вы можете использовать df3 = df2.values, а затем заполнить диагональ np.fill_diagonal(df3, 0). Вы также можете применить это к ответу @Tim Roberts. Это выглядит намного проще. - person forgetso; 10.03.2021

arrow_upward
0
arrow_downward 

import numpy as np
adj_dict = {}
path_to_list = '../adj_list.txt'
# Replace with zero if vertices are connected to themselves
empty_digonal = 1
with open(path_to_list) as f:
    adj_dict = {int(line.split()[0]):[int(x) for x in line.split()[empty_diagonal:]] for line in f.read().strip('\n').splitlines()}
adj_mx = np.zeros([len(adj_dict),len(adj_dict)])
for i in adj_dict:
        adj_mx[i,adj_dict[i]] = 1
assert sum(sum(adj_mx - adj_mx.T)) == 0, 'The matrix is not symmetric'

Возможно, это не оптимальное решение, но оно работает

person lotrus28    schedule 09.03.2021
comment
Спасибо @lotrus28, я получаю сообщение об ошибке трассировки: Файл /tmp/source.py, строка 10, в ‹module› adj_mx[i,j] = 1 IndexError: индекс 1 выходит за пределы оси 1 с размером 1 Мой код : for line in sys.stdin: adj_dict = {} adj_dict = {int(line.split()[0]):[int(x) for x in line.split()[0:]] for line in line.strip('\n').splitlines()} adj_mx = np.zeros([len(adj_dict),len(adj_dict)]) for i in adj_dict: for j in adj_dict[i]: adj_mx[i,j] = 1 assert sum(sum(adj_mx - adj_mx.T)) == 0, print(adj_dict, end="") - person Stina V; 09.03.2021
comment
@SilentP Это означает, что вы пытаетесь использовать j==1, когда максимально допустимое значение j равно 0. У вас плоская матрица. Вы уверены, что ввод не является одной строкой? - person lotrus28; 09.03.2021