Создание списка соседей из списка краев (Python: доступ к кортежам с указанным первым значением)

Используя NetworkX, я получил список кортежей, описывающих ребра (пары вершин) в графе:

G = [(1, 2), (1, 3), (1, 4), (2, 4), (3, 8), (4, 5), (8, 15), (5, 6), (5, 7), (6, 17), (7, 11), (7, 15), (7, 16), (17, 12), (11, 12), (11, 13), (15, 9), (15, 10), (16, 9), (9, 18), (18, 13), (18, 14), (10, 14)]

Используя этот список, я хочу перебрать каждую вершину и найти каждую соседнюю вершину, но я хочу сделать это по порядку. Так что я хотел бы получить, например, вложенный список с подсписком ith, содержащим каждого из соседей для вершины i.

Neighbors = [[2, 3, 4], [1, 4], [1, 8], [1, 2, 5], [4, 6, 7], [5, 17], [5, 11, 15, 16], [3, 15], [15, 16, 18], [14, 15], [7, 12, 13], [11, 17], [11, 18], [10, 18], [7, 8, 9, 10], [7, 9], [6, 12], [9, 13, 14]]

, но это может быть и другая отсортированная структура данных.

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

Есть ли способы добиться этого? Любая помощь очень ценится.


python loops graph networkx metis
person falidoro    schedule 20.04.2017    source источник
comment
Знаете ли вы, сколько есть вершин, не перебирая весь список?   -  person apnorton    schedule 20.04.2017

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете использовать defaultdict следующим образом:

from collections import defaultdict
d = defaultdict(set)

for x, y in G:
    d[x].add(y)
    d[y].add(x)

d
defaultdict(set,
            {1: {2, 3, 4},
             2: {1, 4},
             3: {1, 8},
             4: {1, 2, 5},
             5: {4, 6, 7},
             6: {5, 17},
             7: {5, 11, 15, 16},
             8: {3, 15},
             9: {15, 16, 18},
             10: {14, 15},
             11: {7, 12, 13},
             12: {11, 17},
             13: {11, 18},
             14: {10, 18},
             15: {7, 8, 9, 10},
             16: {7, 9},
             17: {6, 12},
             18: {9, 13, 14}})

Вы можете преобразовать словарь в список:

[sorted(d[k]) for k in range(1, max(d.keys())+1)]
[[2, 3, 4],
 [1, 4],
 [1, 8],
 [1, 2, 5],
 [4, 6, 7],
 [5, 17],
 [5, 11, 15, 16],
 [3, 15],
 [15, 16, 18],
 [14, 15],
 [7, 12, 13],
 [11, 17],
 [11, 18],
 [10, 18],
 [7, 8, 9, 10],
 [7, 9],
 [6, 12],
 [9, 13, 14]]
person Psidom    schedule 20.04.2017
comment
Это работает! Благодаря тонну. Не могли бы вы объяснить разницу между обычным словарем и словарем по умолчанию? - person falidoro; 20.04.2017

arrow_upward
1
arrow_downward

Если у вас есть доступ к исходному графу g, вы можете выполнить итерацию по исходному списку ребер (если нет, вы можете построить g из G):

[list(v.keys()) for _,e in g.edge.items()]
#[[2, 3, 4], [1, 4], [8, 1], [1, 2, 5], [4, 6, 7], [17, 5], [16, 11, 5, 15], ...]

Вы можете опустить list(), если вы согласны с dict_keys, который является просто версией списка только для чтения:

[v.keys() for _,e in g.edge.items()]
#[dict_keys([2, 3, 4]), dict_keys([1, 4]), dict_keys([8, 1]), ...]
person DYZ    schedule 20.04.2017