Преобразование графика в словарную форму - PullRequest
Новая
       8

Преобразование графика в словарную форму

0 голосов
/ 01 мая 2018

В настоящее время я пишу программу для моделирования алгоритма Дейкстры, однако у меня возникли некоторые проблемы с графиком в его текущей форме: 

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'],
     [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) ,
      ({'b', 'f'}, 9), ({'c', 'f'}, 2), ({'d', 'g'}, 7), ({'d', 'h'}, 1) ,
      ({'e', 'i'}, 2), ({'e', 'j'}, 7), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]

Я хочу получить график в виде, указанном ниже 

{ 'a': {'b': 4, 'c': 6, 'd': 8},
    'b': {'a': 4, 'e': 1, 'f': 9}, etc

Возможно ли это?

Ответы [ 2 ]

0 голосов
/ 01 мая 2018

Вот компактный способ использования списка: 

d = {k: dict((list(v[0] ^ {k})[0], v[1]) for v in G[1] if k in v[0]) for k in G[0]}
print(d)
#{'a': {'b': 4, 'c': 6, 'd': 8},
# 'b': {'a': 4, 'e': 1, 'f': 9},
# 'c': {'a': 6, 'f': 2},
# 'd': {'a': 8, 'g': 7, 'h': 1},
# 'e': {'b': 1, 'i': 2, 'j': 7},
# 'f': {'b': 9, 'c': 2},
# 'g': {'d': 7, 'h': 2},
# 'h': {'d': 1, 'g': 2},
# 'i': {'e': 2, 'j': 4},
# 'j': {'e': 7, 'i': 4}}

Разбить это:

  • {k: ... for k in G[0]} выполняет итерацию по первому элементу G, чтобы получить ключи выходного словаря.
  • {k: (... for v in G[1] if k in v[0]) ... } - это выражение-генератор для второго элемента в G, которое даст значение, если ключ k содержится в наборе.
  • v[0] ^ {k} - симметричная разница набора с ключом - это удаляет ключ из набора.
  • list(v[0] ^ {k})[0] преобразует набор в список и получает первый элемент. Это предполагает, что в наборе всегда будет только 2 элемента, один из которых является ключевым.
  • (list(v[0] ^ {k})[0], v[1]) создает кортеж, где вторым значением является число.
  • dict([(list(v[0] ^ {k})[0], v[1]) ... вызывает конструктор dict в этом списке кортежей.

Возможно, немного более дружественная версия, использующая более разумные имена переменных вместо индексации кортежей и set.pop() вместо индексации списков: 

d = {edge: dict(((pair ^ {edge}).pop(), value) for pair, value in G[1] if edge in pair) 
     for edge in G[0]}
0 голосов
/ 01 мая 2018

Для этого вы можете использовать collections.defaultdict.

Код: 

from collections import defaultdict

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'],
     [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) ,
      ({'b', 'f'}, 9), ({'c', 'f'}, 2), ({'d', 'g'}, 7), ({'d', 'h'}, 1) ,
      ({'e', 'i'}, 2), ({'e', 'j'}, 7), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]

result = defaultdict(dict)
for edge in G[1]:
    v1, v2 = edge[0]
    result[v1][v2] = edge[1]
    result[v2][v1] = edge[1]

print(result)

Выход: 

defaultdict(<class 'dict'>,
            {'a': {'b': 4, 'c': 6, 'd': 8},
             'b': {'a': 4, 'e': 1, 'f': 9},
             'c': {'a': 6, 'f': 2},
             'd': {'a': 8, 'g': 7, 'h': 1},
             'e': {'b': 1, 'i': 2, 'j': 7},
             'f': {'b': 9, 'c': 2},
             'g': {'d': 7, 'h': 2},
             'h': {'d': 1, 'g': 2},
             'i': {'e': 2, 'j': 4},
             'j': {'e': 7, 'i': 4}})
...