Numpy -在数组中表示节点网络的排序数字

Question

假设我有一个表示节点网络的数组，其连接节点被描述为“从节点”和“到节点”：

a = array([(1, 2), (2, 3), (3, 4), (4, 5), (2, 6), (6, 7), (7, 8), (2, 9),
       (9, 10), (10, 11), (2, 12), (12, 13), (13, 14), (13, 15), (14, 16)], 
      dtype=[('fnode', '<i4'), ('tnode', '<i4')])

a['fnode']
array([ 1,  2,  3,  4,  2,  6,  7,  2,  9, 10,  2, 12, 13, 13, 14])
a['tnode']
array([ 2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16])

如何最好地将“to节点”组合成列表，使它们共享相同的“from节点”？

我所追求的是这种形式：

#from-node  to-nodes
1             [2]
2             [3,6,9,12]
3             [4]
4             [5]
5             []
6             [7]
7             [8]
8             []
9             [10]
10            [11]
11            []
12            [13]
13            [14,15]
14            [16]
15            []
16            []

编辑

为了明确起见，我希望没有“到节点”(例如节点8)的“从节点”与空列表相关联。

Answer 1

使用collections.defaultdict：

d = defaultdict(list)
map( lambda (k,v) : d[k].append(v), a)
print d
>> Out[40]: defaultdict(<type 'list'>, {1: [2], 2: [3, 6, 9, 12], 3: [4]
: [7], 7: [8], 9: [10], 10: [11], 12: [13], 13: [14, 15], 14: [16]})

Answer 2

如果您已经使用了NumPy而不是lists，我认为您的目标是加快速度。在这种情况下，我建议使用Pandas库。

>>> pd.DataFrame(a).groupby('fnode').apply(lambda x: x['tnode'].values)
fnode
1                  [2]
2        [3, 6, 9, 12]
3                  [4]
4                  [5]
6                  [7]
7                  [8]
9                 [10]
10                [11]
12                [13]
13            [14, 15]
14                [16]
dtype: object

大型数组上的定时信息：

In [32]: a = array([(1, 2), (2, 3), (3, 4), (4, 5), (2, 6), (6, 7), (7, 8),
                    (2, 9), (9, 10), (10, 11), (2, 12), (12, 13), (13, 14),
                    (13, 15), (14, 16)] * 100000, 
                    dtype=[('fnode', '<i4'), ('tnode', '<i4')])
In [33]: %%timeit
         pd.DataFrame(a).groupby('fnode').apply(lambda x: x['tnode'].values)
10 loops, best of 3: 102 ms per loop

In [34]: %%timeit
         d = defaultdict(list)
         map( lambda (k,v) : d[k].append(v), a)
1 loops, best of 3: 5.76 s per loop
In [35]: %%timeit
         [(k, list(v)) for k,v in groupby(a, lambda (x, y): x)]
1 loops, best of 3: 9.02 s per loop

Answer 3

您可以使用itertools.groupby。

定义数组：

A = np.array([(1, 2), (2, 3), (3, 4), (4, 5), (2, 6), (6, 7), (7, 8), (2, 9),
   (9, 10), (10, 11), (2, 12), (12, 13), (13, 14), (13, 15), (14, 16)], 
  dtype=[('fnode', '<i4'), ('tnode', '<i4')])

分类：

A = sorted(A, key=lambda (a,b): a)

然后将其分组(我在这里将生成器转换为一个列表，以便您可以看到其结果)：

In [18]: [(k, list(v)) for k,v in groupby(A, lambda (a,b): a)]
Out[18]: 
[(1, [(1, 2)]),
 (2, [(2, 3), (2, 6), (2, 9), (2, 12)]),
 (3, [(3, 4)]),
 (4, [(4, 5)]),
 (6, [(6, 7)]),
 (7, [(7, 8)]),
 (9, [(9, 10)]),
 (10, [(10, 11)]),
 (12, [(12, 13)]),
 (13, [(13, 14), (13, 15)]),
 (14, [(14, 16)])]

然后你可以做任何你需要的后处理。

例如，在本例中，您需要更多类似于[(k, map(lambda (a,b): b, v)) for k,v ...的内容。

(注意，对数组进行排序很重要。groupby的操作方式与POSIX uniq相同，因为它只合并相邻的元素。若要组合所有元素，请按分组时的相同键进行排序。)