Creating list of neighbors from edgelist (Python: accessing tuples with first value specified)

Question

Using NetworkX, I have acquired a list of tuples describing edges (pairs of vertices) in a graph:

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)]

Using this list, I want to loop over each vertex, and find each neighboring vertex, but I want to do this in order. So what I would like to get is for instance a nested list with the ith sublist containing each of the neighbors for vertex 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]]

, but it could also be another sorted data structure.

However, since my graph could potentially contain a million edges and vertices, I want to achieve a routine that will not loop over the whole list for every vertex, since I want to keep the runtime low.

Are there any ways to achieve this? Any help is very much appreciated.

Do you know how many vertices there are without iterating over the whole list? — apnorton, Apr 20 '17 at 00:10

Psidom · Accepted Answer · 2017-04-20T00:19:43.497

You can use a defaultdict as follows:

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}})

You can convert the dictionary to a list:

[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]]

This works! Thanks a ton. Could you perhaps explain the difference between a normal dictionary and defauldict? — falidoro, Apr 20 '17 at 09:16

score 1 · Answer 2 · answered Apr 20 '17 at 00:42

If you have access to the original graph g, you can iterate through the original edge list (if not, you can construct g from 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], ...]

You can omit list() if you are ok with dict_keys, which is simply a read-only version of a list:

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

Creating list of neighbors from edgelist (Python: accessing tuples with first value specified)

2 Answers2