Граф с узлами в словаре, расстояниями во вложенном словаре и кратчайшими расстояниями в другом вложенном словаре - PullRequest
Новая
       13

Граф с узлами в словаре, расстояниями во вложенном словаре и кратчайшими расстояниями в другом вложенном словаре

0 голосов
/ 06 ноября 2018

Я смотрю следующий учебник (http://tryalgo.org/en/graphs/2018/04/06/graphs_in_python/) и создал словарь G. Сейчас я пытаюсь создать словарь weights, о котором говорит автор, но на самом деле этого не делает. Кто-нибудь может подтвердить, правильно ли я это сделал. Кстати, веса случайные. 

G = { "Alice":  ["Bob", "Claire", "Frank"],
      "Bob":    ["Alice"],
      "Claire": ["Alice", "Dennis", "Esther", "Frank"],
      "Dennis": ["Claire", "Esther", "George"],
      "Esther": ["Claire", "Dennis"],
      "Frank":  ["Alice", "Claire", "George"],
      "George": ["Dennis", "Frank"]}

w = {G["Alice"][0]:3, G["Alice"][1]:4, G["Alice"][2]:2,
     G["Bob"][0]:3,
     G["Claire"][0]:3, G["Claire"][1]:3, G["Claire"][2]:3, G["Claire"[3]:3,
     G["Dennis"][0]:3, G["Dennis"][1]:3, G["Dennis"][2]:3,
     G["Esther"][0]:3, G["Esther"][1]:3,
     G["Frank"][0]:3, G["Frank"][1]:3, G["Frank"][2]:3,
     G["George"][0]:3, G["George"][1]:3}

Кроме того, я создаю словарь под названием shorttest_distance, который содержит кратчайшее расстояние между каждым узлом и всеми остальными узлами. 

shortest_distance = {"Alice":{"Bob":5, "Claire":2, "Frank":4},
        "Bob":{"Alice":3}, 
        .
        .
        "George":{"Dennis":2, "Frank":4}}

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

Ответы [ 2 ]

0 голосов
/ 06 ноября 2018

Вес ребер должен храниться в отдельной структуре, так чтобы вес [v] [u] был весом ребра (v, u). Такая структура была бы просто словарем словарей.

Ваш словарь весов W это не словарь словарей. Это простой словарь, в котором вы продолжаете перезаписывать значения: {'Alice':5, 'Bob': 3, 'Alice':1, 'Charlie':1}.
W['Alice']['Bob'] должен возвращать вес ребра от Алисы Бобу, поэтому W должен иметь ключ 'Alice', который сопоставляется со словарем, в котором есть ключ 'Bob', который сопоставляется с весом ребра:
W = {'Alice': {G["Alice"][0]:3} или просто W = {'Alice':{'Bob':3}}

0 голосов
/ 06 ноября 2018

Чтобы создать график G путем преобразования каждого имени в целое число, вы можете выполнить итерацию по структуре, чтобы создать сопоставление каждого имени с текущим счетчиком. Затем можно зациклить словарь, а затем найти числовое значение для каждого имени в предыдущей структуре: 

mapping = {a:i for i, a in enumerate(G)}
_G = [[mapping[c] for c in i] for i in G.values()]

Выход: 

[[1, 2, 5], 
 [0], 
 [0, 3, 4, 5], 
 [2, 4, 6], 
 [2, 3], 
 [0, 2, 6], 
 [3, 5]]

Обратите внимание, что правильный листинг для выходных данных будет получен только при упорядочении исходной структуры G, что для словарей может быть достигнуто только с Python 3.6 и выше. Если вы используете версию Python менее 3,6, рассмотрите возможность использования collections.OrderedDict или вложенных списков.

...