benchmark_flow.py

import time
from random import randrange, choice, shuffle

import numpy as np
import networkx as nx
from networkx.algorithms import flow
from networkx.utils import create_degree_sequence, powerlaw_sequence

flow_funcs = dict(
    bkolmogorov = flow.boykov_kolmogorov,
    dinitz_algo = flow.dinitz,
    edmonds_karp = flow.edmonds_karp,
    preflow_push = flow.preflow_push,
    shortest_ap = flow.shortest_augmenting_path,
)

def add_capacity(G, random=False):
    size = G.size()
    if random:
        capacity = {(u, v): randrange(1, 100) for (u, v) in G.edges()}
        nx.set_edge_attributes(G, 'capacity', capacity)
    else:
        nx.set_edge_attributes(G, 'capacity', 1)
    return G

def non_connected_node_pairs(G, n=100):
    pairs = set()
    nodes = list(G)
    shuffle(nodes)
    for i in range(n):
        u = nodes.pop()
        v = choice(nodes)
        while v in G[u]:
            v = choice(nodes)
        pairs.add((u, v))
    return pairs
        
def time_pairs_flow(G, pairs, flow_func):
    times = []
    for pair in pairs:
        start = time.time()
        f = flow_func(G, pair[0], pair[1])
        times.append(time.time() - start)
    return np.mean(times), np.std(times)

def build_power_law(n):
    deg_seq = create_degree_sequence(n, powerlaw_sequence, 100)
    G = nx.Graph(nx.configuration_model(deg_seq))
    G.remove_edges_from(G.selfloop_edges())
    G = max(nx.connected_component_subgraphs(G), key=len)
    G.name = 'Power law configuration model: {0}'.format(n)
    return G

def get_test_graphs():
    # Build test graphs
    Gnp_sparse = nx.fast_gnp_random_graph(1000, 0.02)
    Gnp_denser = nx.fast_gnp_random_graph(200, 0.2)
    Gnp_dense = nx.fast_gnp_random_graph(100, 0.8)
    Gconf0 = build_power_law(1000)
    Gconf1 = build_power_law(2000)
    Gconf2 = build_power_law(3000)
    test_graphs = [
        ('Gnp_1000_0.02', Gnp_sparse), 
        ('Gnp_300_0.2', Gnp_denser),
        ('Gnp_200_0.5', Gnp_dense),
        ('pl_1000', Gconf0),
        ('pl_2000', Gconf1),
        ('pl_3000', Gconf2),
    ]
    return test_graphs

def benchmark_flow_funcs(npairs=50):
    for gname, G in get_test_graphs():
        print(nx.info(G))
        print("Mean and std of computing the maximum flow among {} pairs of nodes".format(npairs))
        pairs = non_connected_node_pairs(G, n=npairs)
        for kind in [False, True]:
            print("  Kind of capacity: {}".format('random ints' if kind else 'unit'))
            H = add_capacity(G, random=kind)
            for name, flow_func in sorted(flow_funcs.items()):
                t = time_pairs_flow(G, pairs, flow_func)
                print("    {0}:\t{1:.3f} ({2:.4f}) seconds".format(name, t[0], t[1]))
        print("Time computing node connectivity")
        for name, flow_func in sorted(flow_funcs.items()):
            start = time.time()
            K = nx.node_connectivity(G, flow_func=flow_func)
            end = time.time() - start
            print("    {0}:\t{1:.2f} seconds (kappa={2})".format(name, end, K))
        print("Time computing edge connectivity")
        for name, flow_func in sorted(flow_funcs.items()):
            start = time.time()
            K = nx.edge_connectivity(G, flow_func=flow_func)
            end = time.time() - start
            print("    {0}:\t{1:.2f} seconds (lambda={2})".format(name, end, K))
        print('')
    

if __name__ == '__main__':
    result = benchmark_flow_funcs(npairs=50)