two ways to create a ring graph

For what it’s worth,

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

where you don’t have to do the modulus pass is even faster (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 magic edit!

After a bit of work, this returns the same set of edge pairs much, much faster:

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)

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top