创建环图的两种方法

Question

假设我们有一个具有以下属性的图：

• 节点排列成圆形
• 每个节点都连接到其k下一个邻居

我有两个函数可以使图形变大：

def ring_graph1(n, k):
   graph = nx.Graph()

   sources = np.arange(n)
   for i in range(1, k + 1):
       targets = np.roll(sources, i)
       graph.add_edges_from(zip(sources, targets))

   return graph

def ring_graph2(n, k):
   graph = nx.Graph()

   for i in range(n):
      sources = [i] * k
      targets = range(i + 1, i + k + 1)
      targets = [node % n for node in targets]
      graph.add_edges_from(zip(sources, targets))

   return graph

我天真地认为第一个会更快，因为它处理np.array，并且一次性分配更少的内存，而且因为k<；n它分配的内存更少

但测量结果表明：

times1 = []
times2 = []

for k in [2, 10, 50, 100, 200, 500]:
   t = %timeit -o ring_graph1(1000, k)
   times1.append(t.average)
   t = %timeit -o ring_graph2(1000, k)
   times2.append(t.average)

第二种方法执行速度大约快1.5倍。为什么会这样？

Answer 1

听起来瓶颈似乎是内置的add_edges_from，而不是边缘生成。这可能是意料之中的，因为networkx设计用于处理更复杂的情况，例如边缘属性。事实上，有一个内置的方法可以让你构造环图，例如

nx.circulant_graph(1000, range(1, 501))

相当于

ring_graph2(1000, 500)

但是内置版本实际上比您的版本慢

回到边缘生成，考虑以下实现：

def get_edges(n, k):
  modmap = np.tile(np.arange(n), 2)
  a, b = np.meshgrid(range(n), range(k))
  return zip(a.T.ravel().tolist(), modmap[(a+b+1).T.ravel()].tolist())


assert set(get_edges(1000, 500)) == set(ring_graph5(1000, 500))

%timeit get_edges(1000, 500)   # 10 loops, best of 3: 32 ms per loop
%timeit ring_graph5(1000, 500) # 10 loops, best of 3: 61 ms per loop


def graph_from_edge_generator(f, n, k):
  g = nx.Graph()
  g.add_edges_from(f(n, k))
  return g

%timeit graph_from_edge_generator(get_edges, 1000, 500)   # 1 loop, best of 3: 772 ms per loop
%timeit graph_from_edge_generator(ring_graph5, 1000, 500) # 1 loop, best of 3: 783 ms per loop

在这两种情况下，边缘生成占用的运行时间都少于10%

Answer 2

不管它值多少钱

def ring_graph3(n, k):
    edges = set()
    node_ids = list(range(n)) * 2

    for i in range(n):
        sources = [i] * k
        targets = node_ids[i + 1 : i + k + 1]
        edges.update(set(zip(sources, targets)))

    return edges

在不必进行模传递的情况下，传递速度更快（n=1000，k=500）：

ring_graph1: 2.64 ops/s (1 loops in 0.379351074)
ring_graph2: 5.29 ops/s (2 loops in 0.378035934)
ring_graph3: 5.75 ops/s (2 loops in 0.34760668299999997)

Numpy魔术编辑

经过一点工作后，将以更快的速度返回同一组边对：

def ring_graph5(n, k):
    nxk = np.arange(0, n).repeat(k)
    src = nxk.reshape(n, k)
    dst = np.mod(np.tile(np.arange(0, k), n) + (nxk + 1), n).reshape((n, k))
    flat_pairs = np.dstack((src, dst)).flatten().tolist()
    return zip(flat_pairs[::2], flat_pairs[1::2])

ring_graph1: 2.92 ops/s (1 loops in 0.3422120950000007)
ring_graph2: 5.77 ops/s (2 loops in 0.34680103699999876)
ring_graph3: 6.93 ops/s (2 loops in 0.28863287499999934)
ring_graph4: 6.03 ops/s (2 loops in 0.3317746049999979)
ring_graph5: 19.43 ops/s (5 loops in 0.25736287700000204)