benchmark_bfs.py

import timeit
import random
import networkx as nx

# from https://networkx.org/documentation/stable/_modules/networkx/algorithms/components/connected.html#connected_components
def _plain_bfs(G, source):
    """A fast BFS node generator"""
    G_adj = G.adj
    seen = set()
    nextlevel = {source}
    while nextlevel:
        thislevel = nextlevel
        nextlevel = set()
        for v in thislevel:
            if v not in seen:
                seen.add(v)
                nextlevel.update(G_adj[v])
    return seen

def bfs(G, node):
    seen = {node}
    next = {node}
    while next:
        v = next.pop()
        for n in G.neighbors(v):
            if n not in seen:
                seen.add(n)
                next.add(n)
    return seen

if __name__ == '__main__':
    for _ in range(0,10):
        G = nx.gnm_random_graph(random.randint(1,1000), random.randint(1,1000))
        t = {}
        t['bfs'] = timeit.timeit('bfs(G, 1)', number=1000, globals=globals())
        t['bfs_tree'] = timeit.timeit('set(nx.bfs_tree(G, 1).nodes)', number=1000, globals=globals())
        t['plain_bfs'] = timeit.timeit('_plain_bfs(G, 1)', number=1000, globals=globals())
        print({k: '{:.4f}'.format(v) for k, v in sorted(t.items(), key=lambda item: item[1])})