Как преобразовать список пар в словарь с каждым элементом в качестве ключа к списку парных значений?

Question

Я делаю курсовую работу, которая включает графики. У меня есть списки ребер E = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c') и т. Д.] И Я хочу, чтобы функция конвертировала их в матрицы смежности в виде словарей {'a': ['b', 'c', 'd'], 'b': ['a' и т. Д.}, Чтобы я может использовать функцию, которая вводит только эти словари.

Моя главная проблема в том, что я не могу понять, как использовать цикл для добавления ключей: значений, не перезаписывая списки. Предыдущая версия моей функции выводила бы [] как все значения, потому что у 'f' нет соединений.

Я пробовал это:

V = ['a','b','c','d','e','f']
E=[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

def EdgeListtoAdjMat(V,E):
    GA={}
    conneclist=[]
    for v in V:
        for i in range(len(V)):
            conneclist.append([])
            if (v,V[i]) in E:
                conneclist[i].append(V[i])
    for i in range(len(V)):
        GA[V[i]]=conneclist[i]
    return(GA)

EdgeListtoAdjMat (V, E) выводит:

{'a': [], 'b': ['b'], 'c': ['c', 'c'], 'd': ['d', 'd', 'd'], 'e': [], 'f': []}

тогда как он должен вывести:

{'a':['b','c','d'],
'b':['a','c','d'],
'c':['a','b','d'],
'd':['a','b','c'],
'e':[],
'f':[]
}

Answer 1

Вы можете преобразовать список границ в карту, используя itertools.groupby

from itertools import groupby
from operator import itemgetter

V = ['a','b','c','d','e','f']
E = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

# add edge in the other direction. E.g., for a -> b, add b -> a
nondirected_edges = E + [tuple(reversed(pair)) for pair in E]

# extract start and end vertices from an edge
v_start = itemgetter(0)
v_end = itemgetter(1)

# group edges by their starting vertex
groups = groupby(sorted(nondirected_edges), key=v_start)
# make a map from each vertex -> adjacent vertices
mapping = {vertex: list(map(v_end, edges)) for vertex, edges in groups}

# if you don't need all the vertices to be present
# and just want to be able to lookup the connected
# list of vertices to a given vertex at some point
# you can use a defaultdict:
from collections import defaultdict
adj_matrix = defaultdict(list, mapping)

# if you need all vertices present immediately:
adj_matrix = dict(mapping)
adj_matrix.update({vertex: [] for vertex in V if vertex not in mapping})

Answer 2

Если вы планируете использовать библиотеку, networkx предназначен для таких сетевых проблем:

import networkx as nx 

V = ['a','b','c','d','e','f']
E = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

G=nx.Graph(E)
G.add_nodes_from(V)
GA = nx.to_dict_of_lists(G)

print(GA)

# {'a': ['c', 'b', 'd'], 'c': ['a', 'b', 'd'], 'b': ['a', 'c', 'd'], 'e': [], 'd': ['a', 'c', 'b'], 'f': []}

Answer 3

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

def EdgeListToAdjMat(V, E):
    AdjMat = np.zeros((len(V), len(V)))  # the shape of Adjancy Matrix
    connectlist = {
        # Mapping each character to its index
        x: idx for idx, x in enumerate(V)
    }
    for e in E:
        v1, v2 = e
        idx_1, idx_2 = connectlist[v1], connectlist[v2]
        AdjMat[idx_1, idx_2] = 1     
        AdjMat[idx_2, idx_1] = 1

    return AdjMat

Answer 4

Поскольку у вас уже есть список вершин в V, легко подготовить словарь с пустым списком соединений.Затем просто просмотрите список ребер и добавьте к массиву с каждой стороны:

V = ['a','b','c','d','e','f']
E = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

GA = {v:[] for v in V}
for v1,v2 in E:
    GA[v1].append(v2)
    GA[v2].append(v1)

Answer 5

Более эффективный подход состоит в том, чтобы выполнять итерацию по краям и добавлять к выходному диктату списков вершин в обоих направлениях.Используйте dict.setdefault для инициализации каждого нового ключа списком.И когда итерации по краям заканчиваются, итерируйте по остальным вершинам, которых еще нет в выходных данных, и назначьте им пустые списки:

def EdgeListtoAdjMat(V,E):
    GA = {}
    for a, b in E:
        GA.setdefault(a, []).append(b)
        GA.setdefault(b, []).append(a)
    for v in V:
        if v not in GA:
            GA[v] = []
    return GA

так, чтобы получилось:

V = ['a', 'b', 'c', 'd', 'e', 'f']
E = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

EdgeListtoAdjMat(V, E)) вернется:

{'a': ['b', 'c', 'd'], 'b': ['a', 'c', 'd'], 'c': ['a', 'b', 'd'], 'd': ['a', 'b', 'c'], 'e': [], 'f': []}

Answer 6

Логика того, чего вы пытаетесь достичь, на самом деле довольно проста:

V = ['a','b','c','d','e','f']
E=[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

result = {}
for elem in V:
     tempList = []
     for item in E:
          if elem in item:
               if elem == item[0]:
                    tempList.append(item[1])
               else:
                    tempList.append(item[0])
     result[elem] = tempList
     tempList = []

print(result)

Результат:

{'a': ['b', 'c', 'd'], 'b': ['a', 'c', 'd'], 'c': ['a', 'b', 'd'], 'd': ['a', 'b', 'c'], 'e': [], 'f': []}

Для каждого элемента в V выполните проверку дляпосмотрите, существует ли этот элемент в любом кортеже в E.Если он существует, тогда возьмите элемент, который вместе образует пару в этом кортеже, и добавьте его во временный список.После проверки каждого элемента в E, обновите словарь result и переходите к следующему элементу V до тех пор, пока не закончите.

Чтобы вернуться к своему коду, вам нужно изменить его какследующее:

def EdgeListtoAdjMat(V,E):
    GA={}
    conneclist=[]
    for i in range(len(V)):
        for j in range(len(V)):
            # Checking if a pair of two different elements exists in either format inside E. 
            if not i==j and ((V[i],V[j]) in E or (V[j],V[i]) in E):
                conneclist.append(V[j])
        GA[V[i]]=conneclist
        conneclist = []
    return(GA)